백준 1316번 - 그룹 단어 체커

그룹 단어 체커

 

오늘은 백준 1316번 "그룹 단어 체커" 문제를 풀면서, 코드 개선 과정까지 함께 살펴보겠습니다.

문제 파악

• 주어진 단어가 그룹 단어인지 판별
• 그룹 단어란, 같은 알파벳이 연속해서 나타나기만 하는 단어
• i.g 1) "happy" -> p가 연속해서 나오므로 그룹단어
• i.g 2) "aba" -> a가 떨어져서 나오므로 그룹단어가 아님

접근 방법

단어를 한 글자씩 확인하며 그룹 단어 여부를 판단

• 등장한 문자를 저장할 자료구조 활용
• 현재 문자와 이전 문자를 비교하여 연속 여부 확인
• 이미 나온 문자가 다시 나오면 그룹 단어가 아님

첫 번째 풀이

• dict를 활용하여 문자의 등장 여부를 체크하는 방식

mport sys

fast_input = sys.stdin.readline

N = int(fast_input())
cnt = 0

for _ in range(N):
    word = fast_input().rstrip()
    visited = {}  # 등장한 문자를 저장할 딕셔너리
    prev_char = ""

    is_group_word = True
    for char in word:
        if char != prev_char:  # 이전 문자와 다르면 체크
            if visited.get(char):  # 이미 등장했던 문자라면 그룹 단어 아님
                is_group_word = False
                break
            visited[char] = True  # 새로운 문자 저장
        prev_char = char

    if is_group_word:
        cnt += 1

print(cnt)

 

첫 번째 풀이의 문제점

• 딕셔너리 사용으로 인한 메모리 낭비
• 불필요한 조건문이 많아 가독성이 떨어진다

 

두 번째 풀이

- dict 자료구조 대신, set 자료구조를 활용하여 메모리를 절약

- 여러 조건문을 all을 활용하여 간결한 코드 유지

 

import sys

fast_input = sys.stdin.readline

N = int(fast_input())
cnt = 0

for _ in range(N):
    word = fast_input().strip()
    seen = set()  # 등장한 문자 저장
    prev_char = None

    if all(char == prev_char or char not in seen and not seen.add(char) for char in word):
        cnt += 1

print(cnt)

 

이번 문제는 그룹 단어 판별이라는 간단한 문제여씨만, 해시 테이블을 사용하는 딕셔너리 대신

메모리 사용량이 더 적은 집합 자료구조를 활용하여 더 효율적인 코드를 작성할 수 있었고, 메모리 성능 최적화를 고려해 볼 수 있는 문제였습니다.