[BOJ][C++] 백준 1972번 놀라운 문자열
Updated:
1972번 놀라운 문자열
1. 문제 정보
백준 온라인 저지 [1972번 놀라운 문자열] 문제의 링크입니다.
문제
대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문자열의 D-쌍이라고 한다. 예를 들어 문자열이 ZGBG라고 하자. 이 문자열의 0-쌍은 ZG, GB, BG가 되고, 이 문자열의 1-쌍은 ZB, GG가 되며, 이 문자열의 2-쌍은 ZG가 된다. 문자열의 길이가 N이라고 할 때, 0-쌍부터 (N-2)-쌍까지가 정의됨을 알 수 있다.
만일 정의되는 D에 대해, 어떤 문자열의 모든 D-쌍들이 서로 다를 때, 이 문자열을 D-유일하다고 한다. 위의 예를 보면, 0-쌍들은 ZG, GB, BG로 모두 다르다. 따라서 이 문자열은 0-유일하며, 마찬가지로 1-유일하고, 2-유일하다. 하지만 만일 문자열이 AAA라고 하자. 이 문자열은 0-유일하지 않으며, 다만 1-유일하다.
만일 어떤 문자열이 정의되는 모든 D에 대해 D-유일하면, 이 문자열을 정말이지 ‘놀라운 문자열’이라고 한다. 문자열이 주어질 때, 이 문자열이 놀라운 문자열인지 아닌지를 구하는 프로그램을 작성하시오.
입력
입력의 각 줄에는 알파벳 대문자로만 구성된 문자열이 주어진다. 모든 문자열의 길이는 80을 넘지 않으며, 입력의 마지막 줄에는 마지막을 나타내는 *가 주어진다. 입력은 마지막 줄을 포함해서 101줄을 넘지 않는다.
출력
각 줄에 이 문자열이 놀라운(surprising) 문자열인지 아닌지를 아래의 예제와 같이 출력한다.
예제 입력1
ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*
예제 출력1
ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.
시간 / 메모리 제한
2초 / 128MB
2. 생각
-
놀라운 문자열을 구분하기 위해 입력받은 문자열을 부분 문자열로 쪼갠 뒤에 d-쌍에서 중복이 있는지 체크한 후 중복이 있다면 즉시 멈추고 중복이 발견되지 않는다면 d를 늘리며 다시 검사합니다.
-
d-쌍을 구하기 위한 반복분에 문자열에서 부분 문자열을 구하기 위한 반복문을 중첩하여 구현하였습니다. flag를 두어 중복이 발견되면 “(입력문자열) is NOT surpring.”을 출력하고 즉시 빠져나오고 flag값의 변화 없이 두개의 반복문을 탈출했다면 “(입력문자열) is surpring.”을 출력합니다.
- 첫 번째 반복문의 i는 d-쌍을 나타내고 i가 1일 때는 0-쌍, 2일 때는 1-쌍입니다.
두 번째 반복문의 j와 k는 문자열의 인덱스를 부분 문자열로 나타내 tmp에 저장합니다.s 배열
0 1 2 3 Z G B G d_pair 배열
d_pair 0 1 2 0-쌍 tmp = s[0]+s[1] ZG tmp = s[1]+s[2] GB tmp = s[2]+s[3] BG 1-쌍 tmp = s[0]+s[2] ZB tmp = s[1]+s[3] GG 2-쌍 tmp = s[0]+s[3] ZG -
중복을 체크할 때는 STL vector 대신 find함수를 사용하기 위해 set을 사용했습니다. STL set 은 배열처럼 사용할 수 있고, 이진트리 구조로 정렬되어 저장되기 때문에 이진탐색(Binary Search) 방법으로 빠르게(O(logN)) 검색이 가능합니다.
- set의 내장함수인 find는 중복 데이터를 찾고 중복데이터의 인덱스를 반환합니다. 만약 중복이 없다면 배열의 끝을 가리킵니다.
따라서 d_pair.find(tmp) != d_pair.end() 라면 중복이 있는지 체크하는 구문입니다.
3. 소스코드 (C++)
