길이가 n인 문자열 S가 주어졌다고 가정해 보겠습니다. 원 위에 n개의 숫자가 원형으로 배치되어 있지만, 우리는 이 숫자들의 실제 값을 알 수 없습니다. 대신 문자열 S가 숫자들 간의 관계를 알려줍니다.
문자열의 각 문자는 다음과 같은 의미를 가집니다.
- S[i] = 'E' : i번째 숫자와 (i+1)번째 숫자가 서로 같음
- S[i] = 'N' : i번째 숫자와 (i+1)번째 숫자가 서로 다름
이때 문자열 S에 담긴 정보만으로 실제 숫자 시퀀스를 재구성할 수 있는지 판별해야 합니다.
예를 들어 입력이 S = "ENNEENE"라면 출력은 True입니다. [15, 15, 4, 20, 20, 20, 15]처럼 값을 배정하면 문자열의 모든 조건을 만족할 수 있기 때문입니다.
풀이 접근 방식
이 문제의 핵심 아이디어는 매우 간단합니다. 문자열 S에 포함된 'N'의 개수를 세는 것입니다.
- 'N'이 정확히 하나만 존재하면 → false 반환
- 'N'이 없거나 두 개 이상이면 → true 반환
왜 이 방법이 작동할까?
숫자들이 원형으로 배치되어 있기 때문입니다. 만약 'N'이 단 하나뿐이라면, 나머지 모든 인접 관계는 'E'(같음)여야 합니다. 즉, 한 지점을 제외한 모든 숫자가 서로 같은 값이어야 하는데, 원을 한 바퀴 돌아 마지막 숫자와 첫 번째 숫자의 관계까지 따져보면 모순이 발생합니다.
반면 'N'이 전혀 없다면 모든 숫자를 같은 값으로 설정하면 되고, 'N'이 두 개 이상이라면 각 구간별로 서로 다른 값을 교대로 배정하여 항상 조건을 충족시킬 수 있습니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
bool solve(string S){
if (count(S.begin(), S.end(), 'N') == 1)
return false;
return true;
}
int main(){
string S = "ENNEENE";
cout << solve(S) << endl;
}입력
"ENNEENE"
출력
1
출력값 1(true)은 문자열 "ENNEENE"의 정보만으로도 유효한 숫자 시퀀스를 만들 수 있음을 의미합니다. 이 풀이의 시간 복잡도는 O(n)으로, 문자열을 한 번만 순회하면 되므로 매우 효율적입니다.