백준 1316 - 그룹 단어 체커 (파이썬)

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

풀이

문제 이해

• 주어진 단어가 그룹 단어인지 판별하는 문제
• 그룹 단어란, 단어에서 연속적으로 나타나는 문자만 허용되는 단어
  • 예시) aabb → O
  • 예시) ababa → X (b가 다시 등장)

알고리즘 동작

1. count 변수를 선언하여 그룹 단어 개수를 저장
2. arr의 각 단어에 대해 아래 과정 수행
   1. check 리스트를 통해서 알파벳 26개의 방문 여부를 저장한다.
   2. prev 변수를 사용해서 이전 문자를 저장하여 비교
3. 각 문자 w를 순회하며, prev가 w가 다르면 이미 나온 문자면 그룹 단어가 아님
   1. 아니라면, check 배열에 방문을 표시하고, prev 값을 현재 문자로 업데이트 진행한다.
4. 중간에 break 없이 끝까지 검사되면 그룹 단어이다.

시간 복잡도 분석

1. 각 단어를 O(L) 만큼 탐색
2. 전체 과정은 O(NL)
3. 최악의 경우 O(100 * 100) = O(10,000) 번 연산이므로 충분히 빠름.

코드

# 백준 1316 - 그룹 단어 체커
# 분류 : 문자열
N = int(input())
arr = [input() for _ in range(N)]

count = 0
for word in arr :
    check = [False] * 26
    prev = ''
    for w in word :
        if prev != w :
            if check[ord(w) - 97] :
                break
            check[ord(w) - 97] = True
        prev = w
    else :
        count += 1

print(count)