[백준] 1316: 그룹 단어 체커 (Python)

그룹 단어 체커

• https://www.acmicpc.net/problem/1316

1316번: 그룹 단어 체커

 

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

 

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

 

입출력 예제

입력	출력
3 happy new year	3
4 aba abab abcabc a	1
5 ab aa aca ba bb	4
2 yzyzy zyzyz	0
1 z	1
9 aaa aaazbz babb aazz azbz aabbaa abacc aba zzaz	2

 

풀이

처음 고안한 풀이는 다음과 같다.

1. dic에 현재까지 만난 단어와 그 개수를 저장 / 직전에 검사한 문자를 변수에 저장 / 그룹 단어의 개수는 n으로 초기화
2. 현재 체크하는 문자가 dic에 있는지 검사 - 만약 없다면 추가하고, 있다면 직전 문자와 같은지 비교 - 만약 직전 문자와 같다면 해당 문자의 카운트를 증가시키고, 다르다면 연속하지 않은 것으로 간주해 그룹 단어 아닌 것으로 처리 (그룹 단어 개수 하나 감소)

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = {}
	before = ''
	for i in word: # 해당 문자가 처음 등장
		if i not in alphabet:
			alphabet[i] = 1
		else:
			if i == before: # 같은 문자가 연속해서 등장
				alphabet[i] += 1
			else: # 이전에 등장했던 문자가 연속하지 않게 다시 등장 - 그룹 단어 아님 
				cnt -= 1
				break
		before = i
print(cnt)

메모리: 31256 KB / 시간: 40 ms

 

위 코드의 if-else문이 지저분해 보여서 개선 방법을 고민해 보았다. for i in range(len(word))으로 순회하면 직전 단어를 따로 저장할 필요 없이 작성할 수 있다. if문도 if-elif-else로 수정해 보았다.

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = {word[0]: 1}
	for i in range(1, len(word)): 
		if word[i] not in alphabet:
			alphabet[word[i]] = 1
		elif word[i] in alphabet and word[i] != word[i-1]:
			cnt -= 1
			break
		else:
			alphabet[word[i]] += 1
print(cnt)

메모리: 31256 KB / 시간: 44 ms

 

여전히 조건문이 지저분해서 다른 방법을 고민했다. dictionary를 사용하기 때문에 이전에 없는 문자를 추가할 경우 새로 할당해주는 문장이 필요하므로 지저분해진 것 같아 이번에는 개수를 저장하는 리스트를 사용해 보았다.

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = [0] * 26
	alphabet[ord(word[0])-ord('a')] = 1
	for i in range(1, len(word)): 
		if word[i] != word[i-1] and alphabet[ord(word[i])-ord('a')] > 0:
			cnt -= 1
			break
		else:
			alphabet[ord(word[i])-ord('a')] += 1
print(cnt)

메모리: 31388 KB / 시간: 40ms

if문은 깔끔해졌지만 고정 크기 리스트를 사용하므로 메모리 사용량이 늘어났다.

 

생각해보니 리스트에 굳이 개수를 저장할 필요 없이 이전에 등장했나 안했나 여부만 저장하면 되므로 int 대신 t/f를 저장하면 된다.

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = [False] * 26
	alphabet[ord(word[0])-ord('a')] = True
	for i in range(1, len(word)): 
		if word[i] != word[i-1] and alphabet[ord(word[i])-ord('a')]:
			cnt -= 1
			break
		alphabet[ord(word[i])-ord('a')] = True
print(cnt)

메모리: 31256 KB / 시간: 40 ms

 

결론

그룹 단어 체크를 개수 딕셔너리로 하든 등장 여부 T/F 리스트로 하든 성능은 똑같으니 더 간결한 코드를 쓸 수 있는 방향으로 하면 되겠다.

(복잡한 if-elif-else문을 사용하면 처리 시간이 늘어나고, 개수 리스트를 사용하면 메모리 사용량이 늘어난다)

 

최종 코드

1. 개수 딕셔너리로 순회

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = {word[0]: 1}
	for i in range(1, len(word)): # 해당 문자가 처음 등장
		if word[i] not in alphabet:
			alphabet[word[i]] = 1
		else:
			if word[i] == word[i-1]: # 같은 문자가 연속해서 등장
				alphabet[word[i]] += 1
			else: # 이전에 등장했던 문자가 연속하지 않게 다시 등장 - 그룹 단어 아님 
				cnt -= 1
				break
		before = i
print(cnt)

메모리: 31256 KB / 시간: 40 ms

 

2. 등장 여부 T/F 리스트로 순회

import sys
input = sys.stdin.readline
n = int(input())
cnt = n
for _ in range(n):
	word = input().rstrip()
	alphabet = [False] * 26
	alphabet[ord(word[0])-ord('a')] = True
	for i in range(1, len(word)): 
		if word[i] != word[i-1] and alphabet[ord(word[i])-ord('a')]:
			cnt -= 1
			break
		alphabet[ord(word[i])-ord('a')] = True
print(cnt)

메모리: 31256 KB / 시간: 40 ms