Trie 기본문제로 감잡아보기 -전화번호 목록, 게임 닉네임-

1. 문제1

 

5052번: 전화번호 목록 (acmicpc.net)

5052번: 전화번호 목록

 

2. 풀이1

 

한 번호가 다른 번호의 접두어인 경우가 없어야한다

 

번호를 트라이에 순차적으로 저장하다가, 마지막을 나타내는 플래그 '*'을 만난다면, 

 

지금 저장하려는 번호는 다른 번호의 접두어가 될 것이다

 

class Trie:
    
    def __init__(self):
        
        self.head = {}
    
    def add(self,word):
        
        current_node = self.head
        
        #문자열의 문자를 하나씩 차례대로 순회하면서 저장하다가..
        for char in word:
            
            #현재 노드에 '*'이 존재한다면..
            if '*' in current_node:
                
                #다른 번호의 접두어가 된다
                return False
            
            #'*'이 없거나, 현재 문자가 없으면 저장하면 된다
            if char not in current_node:
                
                current_node[char] = {}
            
            current_node = current_node[char]
        
        #마지막 까지 돌았는데, 현재 노드가 빈 노드가 아니라면..
        if current_node != {}:
            
            #다른 번호의 접두어가 될거고
            return False
        
        else: #현재 노드가 비어있다면..
            
            #마지막 플래그를 저장하고
            current_node['*'] = True
            
            #이 번호는 다른 번호의 접두어가 아니다
            return True

 

add함수만 조금 수정하면 될 것이다

 

현재 번호를 한 문자씩 노드에 저장해나가다가, '*'을 만나면 다른 번호의 접두어가 되므로 False를 return하고

 

마지막까지 왔는데, 비어있지 않다면 역시 다른 번호의 접두어가 되는거고

 

비어있다면... 마지막 플래그 '*'을 저장하고 다른 번호의 접두어가 아니라는, 성공적으로 저장했다는 True를 return

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())

    trie = Trie()

    flag = True

    for _ in range(n):

        phone = stdin.readline().rstrip()

        if flag == False:
            
            continue

        flag = trie.add(phone)
    
    if flag:
        
        print('YES')
    
    else:
        
        print('NO')

 

번호를 input으로 받으면서 trie에 add하다가 flag 값을 구해본다

 

False가 나오면 그 뒤로는 input만 받고 add할 필요는 없으니까 continue로 넘겨준다

 

 

3. 풀이2

 

근데 Trie를 사용하지 않는게 정해라고 한다

 

문자열 리스트를 정렬하고 인접한 문자열끼리 비교해보면 된다

 

근데 이제 함정?이라 하기도 실력이 부족해서 그런거겠지만

 

처음에 in연산을 사용하다가 틀렸는데

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())

    phone_list = []

    for _ in range(n):
        
        phone = stdin.readline().rstrip()

        phone_list.append(phone)
    
    phone_list.sort()

    no = False

    for i in range(n-1):
        
        if phone_list[i] in phone_list[i+1]:
            
            print('NO')
            no = True
            break
    
    if no == False:
        
        print('YES')

 

in연산을 사용한다는 것은 예를 들어

 

'1234' in '51234'하면 이건 True인가 False인가??

 

당연히 True다.. '1234'는 '51234'에 포함되어 있으니까..

 

그러니까 in연산은 접미어더라고 True로 본다는 뜻

 

그러면 이제 문자열리스트를 정렬한다는 것은 어떻게 정렬이 되는가?

 

길이랑 상관없이 맨 앞에 숫자가 작을수록 앞에 온다

 

a = ['323','1234']

a.sort()

print(a)
['1234', '323']

 

그러면 '1234' in '323'하면 True인가 False인가?

 

당연히 False다.. 길이가 더 기니까

 

그래서 in연산을 사용하면 오답이다

 

그래서 전화번호 문자열을 받아서 정렬을 하면 길이랑 상관없이 앞에 있는 숫자 기준으로 오름차순 정렬이 될 것이다

 

그러면 0~n-2까지 순회해서 i번 문자열과 i+1번 문자열의 길이를 비교한 다음에

 

더 작은 길이까지 i번 문자열과 i+1번 문자열을 indexing한다음에 ==으로 서로 동일한지 아닌지를 비교해준다

 

만약에 서로 같다면 한 번호는 다른 번호의 접두어가 될 것이다

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())

    phone_list = []

    for _ in range(n):
        
        phone = stdin.readline().rstrip()

        phone_list.append(phone)
    
    phone_list.sort()

    no = False

    for i in range(n-1):
        
        compare = min(len(phone_list[i]),len(phone_list[i+1]))
        
        if phone_list[i][:compare] == phone_list[i+1][:compare]:
            
            print('NO')
            no = True
            break
    
    if no == False:
        
        print('YES')

 

 

4. 문제2

 

16934번: 게임 닉네임 (acmicpc.net)

16934번: 게임 닉네임

 

 

5. 풀이

 

baekjoon
startlink
bakejoon
beakjoon
baekjoon

 

예시를 보면.. baekjoon이 들어오면 'b'

 

startlink가 들어오면 's'

 

bakejoon이 들어오면... ba까지는 baekjoon에 존재하잖아

 

그런데 k가 붙으면... 더 이상 없으니까 'bak'

 

그리고 beakjoon이 들어오면.. b까지는 baekjoon, bakejoon에 있는데.. e가 붙으면 없으니까 'be'

 

다시 baekjoon이 들어오면.. baekjoon이 이미 있으니까 baekjoon2가 될거고

 

규칙을 파악했다면...

 

위의 문제랑 비슷한 느낌으로 add함수만 수정하면 풀 수 있을 것 같다

 

주어진 문자열을 Trie에 순차적으로 저장을 시킨다

 

문자열의 문자를 하나씩 돌아보면서 Trie에 저장을 시킬건데...

 

만약에 현재 문자가 노드에 존재하지 않는 문자라면...

 

별칭 리스트에 현재 문자를 넣어주고 더 이상 넣지 않겠다는 end 플래그를 True로

 

현재 문자가 노드에 존재하는 문자라면.. 계속해서 별칭 리스트에 문자를 넣어줘야하므로 end 플래그는 세우지 않는다

 

그리고 당연히 end = True인 상태라면.. 더 이상 문자를 별칭 리스트에 넣어줄 필요는 없고 Trie에 저장만 하면 될 것이다

 

문자를 모두 돌아서 Trie에 저장을 끝냈으면.. 필요한건 별칭이니까 별칭리스트를 문자열로 바꿔서 return시킨다

 

from sys import stdin

class Trie:
    
    def __init__(self):
        
        self.head = {}
    
    def add(self,word):
        
        current_node = self.head

        name = []
        end = False

        for char in word:
            
            #현재 문자가 노드에 존재하지 않는다면...
            if char not in current_node:
                
                current_node[char] = {}
                
                #end 플래그가 True가 아닌 경우 별칭 리스트에 넣고
                #더 이상 넣어주면 안되니까 end=True로 바꾼다
                if end == False:

                    name.append(char)
                    end = True

            current_node = current_node[char]
            
            #이미 노드에 문자가 존재하는 경우였다면...
            #별칭 리스트에 문자를 계속 넣어줘야한다
            if end == False:
                
                name.append(char)
        
        current_node['*'] = True
        
        #문자열을 Trie에 저장했다면 별칭을 문자열로 바꿔서 return
        return ''.join(name)

 

근데 중복되는 이름은 개수를 세서 옆에 숫자를 붙여줘야하니까.

 

dict를 이용해서 name을 받을때마다 dict에 그 개수를 저장시켜준다

 

그리고 Trie에 저장을 시도하는데... 현재 name의 개수에 따라 그 개수가 1개라면 숫자를 안붙여줄거고

 

2개 이상이라면 숫자를 붙여줘야겠지

 

n = int(stdin.readline())

nicknames = []
count_dict = {}

trie = Trie()

for _ in range(n):
    
    name = stdin.readline().rstrip()

    nicknames.append(name)
    count_dict[name] = count_dict.get(name,0) + 1

    if count_dict[name] == 1:

        print(trie.add(name))
    
    else:
        
        print(trie.add(name)+str(count_dict[name]))