[백준] 1316번: 그룹 단어 체커 - 파이썬/python

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

1316번: 그룹 단어 체커

접근 방식

- 단어별로 알파벳 순서대로 검사할 수 있는 방식 고민

- 경우의 수 분류 (처음 나온 알파벳, 이미 나온 알파벳) 및 count 시점 고민

 

코드 풀이

n = int(input())
cnt = 0 # 그룹 단어가 아닌 단어

for _ in range(n):
    abc = [] # 알파벳 집합
    word = input()
    now = 0 # 현재 탐색중인 단어
    for w in word:
        if now != w and w not in abc: # 처음 마주한 알파벳인 경우
            now = w
            abc.append(w)
        elif now == w: # 알파벳이 이어진 경우 (그룹 형성중)
            pass
        else: # 이미 탐색한 단어인 경우 (now != w and w in abc)
            cnt += 1
            break
            
print(n-cnt) # 전체 단어 수 - 그룹단어가 아닌 단어 = 그룹 단어의 수

 

그룹 단어가 아닌 경우를 count하여 전체 주어진 단어 수에서 빼주는 방식으로 코드를 작성하였습니다. 단어의 알파벳을 앞에서부터 순차적으로 검사한다면, 처음 알파벳이 나온 경우, 알파벳이 이어지는 경우, 이미 나왔던 알파벳이 다른 알파벳이 나온 후에 다시 나오는 경우 이 세 가지가 존재하게 됩니다. 마지막 경우의 수에 해당한다면 그룹 단어가 아니게 됩니다. 이 경우에 해당하는 즉시 count해주고 for 문 밖으로 나가 다음 단어로 넘어가야 합니다.

 

오답 이유

예를 들어 abaaa와 같은 단어가 주어진다면, a 알파벳이 앞에 나왔기 때문에 뒤쪽 aaa가 등장하면서 그룹 단어가 아니게 됩니다. 알파벳 하나하나 검사하는 과정에서 뒤쪽 aaa를 중복 count해주어 3개의 그룹 단어가 아닌 단어인 것처럼 고려되었기 때문에 오답이 발생하였습니다.

 

메모

break를 통해 for loop 밖으로 나갈 수 있습니다.