[BOJ:1316] 그룹 단어 체커

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

Note

첫 번째 풀이는 스택을 이용해서 풀이했다. 입력 된 문자를 선형 탐색하면서 연속적으로 같은 값이 나오면 스택에 넣어주고 다른 값이 나올 때 기존 스택을 비워주고 다시 스택에 넣는다. 이때 스택에 넣을 때 선형탐색에서 최초 등장 문자의 경우 등장여부를 체크한다. 그리고 다시 선형탐색하는데 이번 문자가 기존에 나왔던 문자라면 그룹단어가 아니다.

두 번째 풀이는 슬라이싱을 활용해서 풀이했다. 첫 번째와 마찬가지고 선형탐색하는데 현재 인덱스를 i라고 할 때 i번째 문자와 i+1번째 문자를 비교한다. 비교하면서 두 문자가 서로 다를 경우 i번 째 인덱스가 이후의 또 등장하는지 체크해서 등장하면 그룹문자가 아니다.

Code

import sys
input = sys.stdin.readline

N = int(input())
group_word = 0
for _ in range(N):
    word = input().rstrip()
    alphabet = [False]*(26)
    stack = []
    for ch in word:
        if len(stack) != 0:
            if stack[-1] == ch:
                stack.append(ch)
            else:
                if alphabet[ord(ch)-97]:
                    break
                else:
                    stack = [ch]
                    alphabet[ord(ch)-97] = True
        else:
            if alphabet[ord(ch)-97]:
                break
            else:
                stack.append(ch)
                alphabet[ord(ch)-97] = True
    else:
        group_word += 1
print(group_word)

import sys

n = int(input())

group_word = 0
for _ in range(n):
    word = input()
    flag = True
    for index in range(len(word)-1):
        if word[index] != word[index+1]:
            if word[index] in word[index+1:]:
                flag = False
                break
    if flag:
        group_word+= 1

print(group_word)

다른 사람 풀이

for _ in range(n):
    word = input()
    a = list(word)
    b = sorted(word, key=word.find)
    group_word +=  a==b
print(group_word)

sorted(word, key=word.find) 문자열에 대해서 key=word.find 를 기준으로 정렬하면 문자에서 처음 등장하는 문자들을 기준으로 정렬된다. 예를 들면 'xcabx'라는 문자가 있었을 때 정렬 기준은 x부터 'xx' 그 다음 c 'xxc' 그 다음 a 'xxca' 그 다음은 b, 'xxcab' 이렇게 정렬된다. 이 함수를 잘 이용하면 쉽게 풀 수 있는데, sorted의 첫 번째 parameter로 문자열을 넣어주고 key=word.find를 넣어주면 문자열의 순서를 기준으로 정렬이 되고 반환 값은 list이다. 기존 문자열도 list로 만들어 주고 두 리스트를 비교하여 같으면 그룹단어이고, 다르면 그룹단어가 아니다.