https://www.acmicpc.net/problem/2596
문제
> A, B, C, D, E, F, G, H로 비밀편지를 보내는데 각 문자마다 0과 1로 규칙을 정해 암호화해서 보낸다.
> 암호화된 수열을 받았을 때 잘못된 수열을 보내도 각각의 암호와 비교해 1자리만 다르다면 알아들을 수 있지만 모든 문자와 두자리 이상 다르면 알 수 없다.
> 비밀편지를 받았을때 원래편지가 뭔지 출력하고 알 수 없다면 알 수 없는 문자의 시작 위치를 출력해라.규칙
A - 000000
B - 001111
C - 010011
D - 011100
E - 100110
F - 101001
G - 110101
H - 111010
접근
입력으로 자릿수와 수열이 들어온다. 문자는 6자리의 수열로 각각 이루어지므로 수열을 6개씩 나눠 각 자리번호로 저장한다.
미리 규칙에 정한 문자와 비교하며 동일하면 해당 문자를 출력하고 한 자만 틀려도 해당문자, 두 자 이상이면 해당 문자의 번호를 출력한다.
문제해결
> 규칙을 먼저 정의해주고 입력을 모두 받아준다.
> 입력으로 들어온 수열을 6개씩 나눠 비교하기위해 str벡터에 넣어준다.
> str벡터에 있는 문자열과 규칙을 하나씩 전부 비교한다.
만약 같은문자(cnt == 0)가 있다면 바로 다음 문자로 넘어간다.
> 한 글자만 다른경우는 유추해 찾을 수 있으므로 cnt가 1인 경우를 map으로 기억해놓는다. 또 1이 들어오면 유추가 불가능 하므로 해당 자리수를 출력하고 끝낸다.
> 최종적으로 한 글자만 다른경우가 하나면 기억해놨던 그 글자를 결과에 누적한다. 만약 전부 cnt가 2 이상이면 똑같이 유추못하므로 해당 자리수를 출력하고 끝낸다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
map<int, int> comp;
vector<string> secret =
{
"000000",
"001111",
"010011",
"011100",
"100110",
"101001",
"110101",
"111010"
};
int n;
string s;
cin >> n;
cin >> s;
vector<char>result;
vector<string> str;
for (int i = 0; i < s.length(); i += 6) str.push_back(s.substr(i, 6));
for(int t = 0; t < n; t++)
{
comp.clear();
bool valid = true;
for (int i = 0; i < secret.size(); i++)
{
int cnt = 0;
for (int j = 0; j < 6; j++)
{
if (str[t][j] != secret[i][j]) cnt++;
}
if (cnt == 0)
{
char tmp = i + 'A';
result.push_back(tmp);
valid = false;
break;
}
else
{
if (cnt == 1)
{
if (comp.count(cnt) != 0)
{
cout << t + 1 << '\n';
return 0;
}
comp[cnt] = i;
}
}
}
if (valid)
{
if (comp.count(1))
{
char tmp = comp[1] + 'A';
result.push_back(tmp);
}
else
{
cout << t + 1 << '\n';
return 0;
}
}
}
for(auto& c : result) cout << c;
}
후기
흐름은 잘 생각했는데 구현이 어려웠다.
반복문에서의 각각의 인덱스, 비교대상 매칭해주는것도 복잡했지만 할만했다.
문자 조건이 까다로웠는데 다른게 1이나 2가 나오면 일단 기억해놓고 나중에 끌고와서 결과 만드는게 복잡했다. 예외도 생기고 결과 오류도 많이 나서 쉽지않았다.
