[백준] 놀라운 문자열 [해설 + 풀이 코드 + 왜 오래 걸렸을까]

구현 & 완전탐색

https://www.acmicpc.net/problem/1972

1972번: 놀라운 문자열

 

코드

import sys

while True:
	string = input().strip()
	if string == '*':
		break

	flag = True
	for i in range(len(string)-1):

		check = []
		answer = 0
		for j in range(len(string)-(i+1)):
			for k in range(i+j+1, (i+j+1)+1):

				word = string[j], string[k]
				# word = string[j] + string[k]
                
				if word not in check:
					check.append(word)
				else:

					answer += 1
					break

		if answer != 0:
			print(f'{string} is NOT surprising.')
			flag = False
			break

	if flag:
		print(f'{string} is surprising.')

 

설명

 이번 문제는 완전 탐색 유형의 문제를 풀어 봤다. 생각보다 for문의 범위 지정하는 부분에서 시간을 많이 소비하여 손으로 써가면서 범위를 도출했다. 완전 탐색 같은 경우 범위를 정하는 게 참 어려운 것 같아서 자연스럽게 머릿속에서 그려질 때까지 연습이 매우 필요로 되는 영역이라고 생각한다. 

 

 해당 문제의 가장 중요한 점은 ' 놀라운 문자열 ' 이라고 정의되어 있는 부분이다. 이 부분의 정의를 보자면 ' D-쌍 ' 두 문자를 순서대로 나열한 것을 ' D-쌍 '이라고 한다. 이때 총 N-2 쌍까지 만들 수 있으며 만약 문자열의 길이가 4라고 한다면 4-2 = 2까지 쌍을 만들어 낼 수 있다. 이때 0쌍, 1쌍, 2쌍이라고 정의하고 있으며 이때마다 만들 수 있는 문자가 전부 달라진다. 따라서 아래와 같다.

 

 

이 문자열의 0-쌍은 ZG, GB, BG가 되고, 이 문자열의 1-쌍은 ZB, GG가 되며, 이 문자열의 2-쌍은 ZG가 된다. 

 

 

 가장 중요한 건 저렇게 만들 수 있는 방법이 무엇이냐가 정의되어야 하며, 정의 했다면 해당 문자를 어떻게 만들 수 있는지를 정의해야 한다. 따라서 해당 문자처럼 만들기 위해 우리는 ' 완전 탐색 '을 해보면 문자가 만들어진다는 걸 감으로나마 알 수 있다. 하지만 범위를 어떻게 지정을 해야 하는가. 1쌍부터 보면 ZB를 만들려면 0번 인덱스와 2번 인덱스를 통해서 만들어진 것을 확인해 볼 수 있다. 또한 0쌍, 1쌍, 2쌍 모두 시작은 가장 처음부터 시작하게 된다. 그렇다면 아래와 같이 정의해 볼 수 있다.

 

 

# 0쌍
i = 0, j = 0, k = 1
i = 0, j = 1, k = 2
i = 0, j = 2, k = 3

# 1쌍
i = 1, j = 0, k = 2
i = 1, j = 1, k = 3

# 2쌍
i = 2, j = 0, k = 3

 

 

 i 는 ' 몇 쌍 ' 인지 나타내는 것이며, j는 그때의 단어의 시작 위치, k는 j와 쌍을 이룰 단어의 인덱스라고 정의해 볼 수 있다. 이제 위 규칙을 토대로 범위를 지정해야 하는데 가장 처음부터 먼저 살펴보면 i는 몇 쌍 인지를 나타내고 있기 때문에 몇 쌍을 만들 수 있는 조건은 문제에서도 설명하듯이 N-2만큼 즉 문자열의 길이 - 2 만큼 만들 수 있다고 나와 있기 때문에 범위 자체는 문자열의 길이 - 2 만큼 첫 번째 for문이 돌아가게 된다면 0쌍, 1쌍, 2쌍... N-2쌍만큼 만들어낼 수 있다. (이해가 가지 않는다면 손으로 작성해 보면 이해가 빠르다.) 그다음 j 같은 경우 문자의 시작 위치다 앞서 기술했듯이 항상 0번 인덱스부터 시작을 하고 있고 그것을 토대로 항상 0부터 시작해야 된다는 힌트를 얻을 수 있다. 그럼 j 같은 경우 0쌍일 때는 3번, 1쌍 일 때 2번, 2쌍 일 때 1번만 돌고 있다 그렇다는 건 전체에서 - 쌍을 나타내는 것만큼 돈다는 것이다. 그럼 이를 적용해 보면 문자열의 길이를 4라고 했을 때 4-(i) 돌게 되는 것이다. 하지만 우리는 인덱스가 0부터 시작하기 때문에 이를 맞추기 위해 4-(i+1)로 보정하여 위와 같이 for문을 구성할 수 있다. 다음으로 k번째가 가장 까다로웠는데 이는 마지막 지점을 기술하는 방법이 자꾸 꼬였기 때문이었다. 우선 0쌍의 k부터 살펴보면 k=1,2,3으로 1씩 증가하고 있고, 1쌍에서는 2,3 하나씩 증가하고 있다.

다시 0쌍으로 돌아와 k를 만들려면 어떻게 해야할까를 생각해 보자. k는 i+j+1 한 만큼 증가하고 있다. 이를 쉽게 알기 위해서 방정식을 통해 구해보면 이해가 빠르다. i+j+x = k 되는 수를 찾아보면 x는 모두 1로 동일해진다는 걸 알 수 있다. 따라서 모든 쌍에 대해 모든 문자의 시작+ 쌍 + 1을 하면 k가 나온다는 사실을 알았으며 우리는 마지막에서도 k가 문자열 끝까지 도는 걸 원하지 않는다. 왜냐하면 해당 문자까지만 단어를 만들어 내야 하기 때문이다. (두 단어이면서 거리가 D인 곳과 쌍을 맺기 때문에) 그럼 그 문자까지만 출력하려면 어떻게 해야 할까? 생각보다 간단했다. 이는 해당 문자열 다음 인덱스까지만 범위로 잡아주면 해당 문자의 인덱스까지만 단어를 만들고 for문을 종료한다. 이러한 과정을 통해 for문의 범위와 단어 구성 규칙을 보고 완전 탐색을 할 준비를 마쳤다.

 

 이제 해당 단어는 j + k 인덱스의 조합으로 만들 수 있으며 ' 놀라운 문자열 ' 이라는 건 어떤 쌍에서도 중복되는 게 없는 문자열을 말하고 있기 때문에 쌍마다 중복이 되는지 되지 않는지를 체크해 보며 만약 하나라도 어떠한 쌍에서 중복이 생기게 된다면 그건 놀라운 문자열이 아니다. 왜냐하면 어떤 쌍에서도 중복이 되지 않아야 하기 때문이다. 그렇기 때문에 그러한 쌍이 존재한다면 NOT surprising을 출력하게 만들어둔다. flag함수를 통해 모든 쌍에서 중복이 없을 때만 is surprising. 을 출력하게 해 주면 AC를 받게 된다.

 

 추가적으로 위에서 word = string[j], string [k]라고 만하고 단어 자체를 검사하고 있지는 않다. 다만 위처럼 작성할 경우 튜플로 묶이게 되며 (j, k) 튜플로 들어가게 되어 위에 처럼 작성해도 정답은 받으나 단어를 만들었다는 느낌을 받기 쉽지 않을 것 같다는 생각에 + 연산자로 단어를 만들어 주는 게 위 코드 의도대로라면 더 나은 코드라고 볼 수 있을 것 같다.