SW Expert Academy 14557_카드 제거 문제풀이 in C++
문제 URL
문제 요구사항
- N개의 똑같은 카드가 일렬로 놓여 있다.
- 이 중 i (1 ≤ i ≤ N)번 카드는 좌표 i에 놓여 있다.
- 각각의 카드는 앞면이 위를 향하거나 뒷면이 위를 향하도록 놓여 있다.
- 당신의 목표는 아래 규칙에 따라 모든 카드를 제거하는 것이다.
- 어떤 카드를 제거하려면 그 카드는 앞면이 위를 향하도록 놓여 있어야 한다.
- i번 카드를 제거할 때에는, i-1 번 카드와 i+1 번 카드를 동시에 뒤집는다. 단, 해당 번호의 카드가 존재하지 않거나 이미 제거되었다면 뒤집지 않는다.
■ 카드의 앞면이 위를 향해 있었다면, 카드를 뒤집은 이후에는 뒷면이 위를 향하게 된다. 반대의 경우도 마찬가지이다.
- 초기 카드 배치가 주어졌을 때, 모든 카드를 제거할 수 있는지를 판단하는 프로그램을 작성하라.
[입력]
- 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
- 각 테스트 케이스는 한 개의 줄로 이루어지며, 각 줄에는 길이가 1 이상 100,000 이하인 문자열 S가 주어진다.
- N은 문자열 S의 길이이며, 모든 1 ≤ i ≤ N 에 대해 S[i]가 ‘1’이라면 i 번 카드는 앞면이 위를 향하도록 놓여 있고, ‘0’이라면 i 번 카드는 뒷면이 위를 향하도록 놓여 있다.
[출력]
- 각 테스트 케이스마다, 모든 카드를 제거할 수 있다면 ‘yes’, 제거할 수 없다면 ‘no’를 출력한다.
접근 방법
- 문제에서 요구하는 게임 방식으로 코딩하면, 당연히 10만이라는 size의 문자열을 탐색하고 재배열하고, 또 탐색하는 이 과정에서 런타임 에러가 뜬다.
- 다른 문제들과 비슷하게 Trick이 있을 거 같았고, 문제에서 주어진 test_case를 살펴보면 홀 수 있 때 모든 카드가 제거 된다는 것을 알 수 있다.
풀이 순서
- TC를 입력 받고, 해당 TC만큼 반복한다.
- 문자열 S를 입력 받아 해당 문자열 length()만큼 for문을 반복해 ‘1’의 개수를 구한다.
- 1의 개수가 홀수면 yes를, 아니라면 no를 출력한다.
소스코드
#include <iostream>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
for (int test_case = 1; test_case <= TC; test_case++) {
string S;
cin >> S;
int checked = 0;
for (int i = 0; i < S.length(); i++) {
if (S[i] == '1')
checked++;
}
if (checked % 2 != 0)
cout << "#" << test_case << " yes\n";
else
cout << "#" << test_case << " no\n";
}
return 0;
}
문제 풀이 결과
