문제
0, 1, e, o 로 구성된 문자열을 처리하는 문제다. e는 이전까지 등장한 1의 개수가 짝수이면 0, 홀수이면 1로 치환하고, o는 그 반대로 치환한다. #을 만나면 입력을 종료한다.
입력
- 한 줄에 문자열 하나씩 주어진다.
- 문자열은
0,1,e,o로만 구성되며,#이 입력되면 종료한다.
출력
- 각 문자열에 대해
e와o를 규칙에 따라0또는1로 치환한 결과를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1e | 11 |
0o | 01 |
1oe | 101 |
# | (종료) |
풀이
문자열을 순회하며 1의 등장 횟수를 추적하고, e/o 위치에서 패리티를 판단해 치환한다.
- 문자열 입력 시
#이면 루프 종료 - 문자를 순서대로 순회하며
1이면 카운트 증가 후 출력 e이면1의 개수가 짝수일 때0, 홀수일 때1출력o이면1의 개수가 홀수일 때0, 짝수일 때1출력- 그 외 문자는 그대로 출력
핵심 아이디어: e(even)와 o(odd)는 현재까지의 1 개수 패리티를 기반으로 패리티 비트를 결정하는 특수 문자다.
코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
while (1)
{
cin >> str;
if (str[0] == '#')
break;
int cnt = 0;
for (char e : str)
{
if (e == '1')
{
cnt++;
cout << e;
}
else if (e == 'e')
{
if (cnt % 2 == 0)
cout << '0';
else
cout << '1';
}
else if (e == 'o')
{
if (cnt % 2 == 0)
cout << '1';
else
cout << '0';
}
else
{
cout << e;
}
}
cout << '\n';
}
return 0;
}복잡도
- 시간: O(N) — 문자열 전체를 한 번 순회
- 공간: O(N) — 입력 문자열 저장