[Codeforces][Round #732][Div.2] B : AquaMoon and Stolen String

https://codeforces.com/contest/1546/problem/B

Problem - B - Codeforces

 

 

[난이도] Div.2
[유형] 수학

[풀이]
몇번 연산이 일어나든 같은 index 위치의 문자들끼리만 교환이 일어나므로
연산 후의 특정 index에 존재하는 a~z의 각 개수는 동일해야합니다.
이것을 이용하면 어떤 문자열이 사라졌는지 찾을 수 있습니다.

1. check[100001][26] 배열을 선언해 0~N-1 번째 위치에 a~z (0~25) 가 각 몇개씩 있는지를 저장해놓습니다.
(만약 i번 위치에 'c'가 있다면 check[i]['c'-'a]++ 를 통해 c 1개가 추가되었다는 것을 기록합니다.)
2. 그 다음에 주어지는 연산이 완료된 N-1개의 문자에 대해 i번 위치에 어떤 문자가 있으면 check[i]['문자'-'a']-- 연산을 통해 연산 뒤에도 해당 문자가 남아있음을 체크합니다.

3. 사라진 문자열의 i번 문자는 check[i][j] (j:0~25 (a~z index)) 중에 1인 문자가 됩니다.

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,M;
int check[100001][26];

void solve(){
    memset(check,0,sizeof(check));

    string s,ret;
    for(int i=0;i<N;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']++;
        }
    }

    for(int i=0;i<N-1;i++){
        cin >> s;
        for(int j=0;j<M;j++){
            check[j][s[j]-'a']--;
        }
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<26;j++){
            if(check[i][j]>0){
                ret.push_back(j+'a');
            }
        }
    }
    cout << ret << '\n';
    cout << flush;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> tc;
    while(tc--){
        cin >> N >> M;
        solve();
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round732-Div.2/B.cpp