프로그래머스 / 구현 / 영어 끝말잇기

문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

 

입출력

---

 

해설

---

 

끝말잇기를 영어로 하는 버전이라고 생각하면 된다.

 

일단 끝말잇기를 한다고 하면 다음의 규칙을 지켜야 한다.

 

1. 끝에 말한 영어단어를 이어서 말해야 한다.

2. 이전에 말했던 단어는 절대로 말해서는 안된다.

 

그러면 위에 2가지를 지키기 위해서 해시맵, char 변수 하나씩 필요할 것이다.

 

해시맵으로는 이전에 말했던 단어를 저장하여 O(1)에 빠르게 검색할 수 있도록 한다.

다음 char변수는 바로 이전에 말했던 마지막 단어를 저장하여 현재 말한 단어와 이어지는 지 확인한다.

 

나머지는 now_round를 통해서 현재 몇 라운드인지 확인하기 위해서 사용했다.

정답코드

---

'''
'25. 08. 17

1. 1부터 n까지 번호가 붙어있는 N명의 사람이 영어 끝말잇기를 하고 있다.
2. 끝말잇기처럼 앞서 말한 단어를 다시 말할 수 없다.

1. N명이서 하기 때문에 N명이 지나면 새로운 라운드가 진행된다.
2. 앞서 말한 것은 dict or set으로 관리하고
3. 라운드는 현재 라운드로 관리하면 된다.
'''
def solution(n, words):
    answer = [0, 0]

    now_round = 1
    pre_words = set()#단어 나온 것들
    last_word = words[0][0]#마지막 사용한 단어
    while 1:
        is_out = 0
        who = -1
        i = 0
        while i != n and (now_round - 1) * n + i != len(words):
            if words[(now_round - 1) * n + i] in pre_words or last_word != words[(now_round - 1) * n + i][0]:
                is_out = 1
                who = i + 1
                break
            pre_words.add(words[(now_round - 1) * n + i])
            #print(words[(now_round - 1) * n + i])
            last_word = words[(now_round - 1) * n + i][-1]
            i += 1
        if (now_round - 1) * n + i == len(words):break
        if is_out:
            answer = [who, now_round]
            break
        now_round += 1
            
        
    return answer

 

깃허브 : https://buly.kr/2JoeH6S

유튜브 : https://youtu.be/PUF3VRebFbg