[백준] 1316번 - 그룹 단어 체커 파이썬(Python)

 

백준 1316번 문제: 그룹 단어 체커

---

문제 설명

1. 그룹 단어란, 단어에 포함된 문자들이 각각 연속해서 나타나는 경우를 말합니다.
   • 예: happy, new, year는 그룹 단어.
   • 예: abc, aab는 그룹 단어.
   • 예: aabbcc, abca는 그룹 단어가 아님 (abca에서 a가 떨어져 다시 등장).
2. 입력으로 주어진 단어들이 그룹 단어인지 판단하고, 그룹 단어의 개수를 출력합니다.

---

문제 해결 전략

1. 문자 등장 순서 추적:
   • 단어를 한 글자씩 순회하며, 이미 등장한 문자와 현재 문자가 연속적인지 확인합니다.
   • 이전 문자와 같으면 계속 진행.
   • 이전 문자와 다르지만 이미 등장했던 문자라면 그룹 단어가 아님.
2. 각 단어를 독립적으로 처리:
   • 주어진 단어마다 독립적으로 판단.
   • 결과적으로 그룹 단어인 단어의 개수를 세면 됩니다.

---

코드 구현

def is_group_word(word):
    seen = set()  # 등장한 문자를 저장할 집합
    prev_char = None  # 이전 문자를 저장

    for char in word:
        if char != prev_char:  # 이전 문자와 다를 때
            if char in seen:  # 이미 등장했던 문자면 그룹 단어 아님
                return False
            seen.add(char)  # 새로운 문자를 추가
        prev_char = char  # 이전 문자를 갱신

    return True  # 모든 문자가 조건을 만족하면 그룹 단어

# 입력 처리
n = int(input())  # 단어 개수
count = 0

for _ in range(n):
    word = input()
    if is_group_word(word):  # 그룹 단어라면 카운트 증가
        count += 1

print(count)

---

코드 설명

1. is_group_word 함수:
   • seen 집합:
     • 등장했던 문자를 저장합니다.
   • prev_char 변수:
     • 현재 문자와 이전 문자가 연속인지 판단하는 데 사용합니다.
   • 문자 순회 중:
     • 이전 문자와 다르고, 이미 등장한 문자라면 그룹 단어가 아님.
     • 새로운 문자는 seen 집합에 추가합니다.
2. 단어 입력 및 판별:
   • 주어진 n개의 단어를 하나씩 판별.
   • 그룹 단어라면 count를 증가시킵니다.
3. 결과 출력:
   • 그룹 단어의 총 개수를 출력합니다.

---

입출력 예시

입력:

3
happy
new
year

출력:

3

---

입력:

4
aba
abab
abcabc
a

출력:

1

 

풀이 과정:

1. aba: a → b → a (떨어진 a가 다시 등장 → 그룹 단어 아님).
2. abab: a → b → a (떨어진 a가 다시 등장 → 그룹 단어 아님).
3. abcabc: a → b → c → 다시 a 등장 (그룹 단어 아님).
4. a: 한 글자이므로 그룹 단어.

---

시간 복잡도

• 단어 개수: n
• 단어의 평균 길이: m
• 각 단어를 순회하므로 전체 시간 복잡도는 O(n⋅m)

---

자주 하는 실수

1. 이미 등장한 문자를 확인하지 않음:
   • 떨어진 문자가 다시 등장할 경우를 확인하지 않으면 틀린 결과가 나옵니다.
2. 이전 문자와 연속된 경우를 놓침:
   • 이전 문자와 연속된 경우는 문제없으므로 조건을 명확히 처리해야 합니다.