[백준/Python] 1316 그룹 단어 체커

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

 

 

사용 알고리즘: 없음 -> 구현

 

 

ccazzzzbb -> 그룹단어 o

kin -> 그룹단어 o

aabbbccb -> 그룹단어 x

 

문자열이 1개 이상 연속해서 나타나고, 나타났던 문자가 따로 떨어져서 나타나면 그룹 단어가 아님!

 

 

어떤식으로 나타났던 문자의 중복 체크를 해줘야할까 하다가 딕셔너리를 떠올렸다. (왜인지는 나도 모름)

단어를 입력받고 { key : value } 를 각 문자를 순서대로 { 문자 : 인덱스 } 로 저장하면 문자의 마지막 등장 인덱스가 저장되는데, 이를 이용해서 그룹 단어인지 체크하면 된다. 

 

예를 들어 happy 라는 그룹 단어를 입력 받았다면 아래와 같이 딕셔너리에 저장된다. 

dic = {'h': 0, 'a': 1, 'p': 3, 'y': 4}

 

반면 aba 라는 그룹 단어가 아닌 문자열을 입력 받았다면, 아래와 같이 딕셔너리가 저장된다. 

{'a': 2, 'b': 1}

 

 

그룹 단어의 경우에는 인덱스가 증가하지만, 그룹 단어가 아닌 경우에는 증가하지 않는다. 

 

순서대로 딕셔너리에 값을 넣었기 때문에

1. 제일 먼저 만난 a 의 인덱스를 넣음

2. b 를 만나서 b 의 인덱스를 넣음

3. b 다음에 다시 나온 a 를 만나서 a 의 인덱스를 넣음

 

그러므로 증가하지 않는 인덱스를 가지는 문자열은 그룹 단어가 아니다!

 

 

전체 코드

N = int(input())

check = []
cnt = 0

for i in range(N):
    dic = {}
    word = list(input())
    for j in range(len(word)):
        dic[word[j]] = j
    for k in range(1, len(word)):
        if dic[word[k-1]] > dic[word[k]]:
            cnt += 1
            break
print(N-cnt)

 

 

풀고 나서 좀 지저분한가 싶어서 문제 젤 잘 풀 것 같은 챗 지피티한테 문제 주고 풀어보라함. 역시 직관적이고 깔끔..

def is_group_word(word):
    seen = set()  # 지금까지 등장한 문자를 저장하는 집합
    current_char = word[0]  # 첫 번째 문자를 현재 문자로 설정
    seen.add(current_char)
    
    for char in word[1:]:
        if char != current_char:
            if char in seen:
                return False
            seen.add(char)
            current_char = char
    
    return True

def count_group_words(words):
    count = 0
    for word in words:
        if is_group_word(word):
            count += 1
    return count

# 입력
n = int(input())
words = [input().strip() for _ in range(n)]

# 결과 출력
print(count_group_words(words))