1.문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : tank, wheel, mother
• 2번 사람 : kick, land, robot
• 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, recognize, gather
• 2번 사람 : observe, encourage, refer
• 3번 사람 : effect, ensure, reference
• 4번 사람 : take, establish, estimate
• 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, even, now, draw
• 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

2.풀이과정

"끝말잇기" 라는 문제의 제목부터가 아주 맘에 들었어요!
뭔가 향수를 자극하는 느낌이랄까..! 뭔가 흥미가 가면 더 잘 풀고 싶어지잖아요!

음, 이번 문제는 문제를 읽었을 때부터, 저의 고질적인 습관에 정면으로 맞서 싸워보려고 더욱 노력했답니다. 제가 현재 시점에서, 스스로 생각하기에 가장 큰 문제점은 다음과 같았죠.

• 문제를 어떻게든 해결하려는 데에 과하게 집중되어 있다.
  급한 마음으로 갖는 이러한 태도는, "정해(正解)"에 이르는 사고를 방해한다
• 생각한 로직을 가능한한 머리 속에서 구체화해야 한다.
  의사코드를 작성하는 건 이에 관련한 좋은 습관일 수 있지만, 그보다 더 구체화된 사고와 검증이 수반되는 것이 좋다.
• 한번 접근한 방식과 로직을 폭넓게 검토하고 수정해야 한다. 물 새는 곳만 대충 막으면 된다는 방식의 코딩은 정말 좋지 않다.

진중하게 나의 습관을 성찰해서, 스스로의 문제점을 정리한 것이지만,적어놓고 나니.. 현타가 온다..

뭐 어쩌겠어!
문제점은 해결할 수밖에 없는걸요! 🏃🏻

하나하나 효과적으로, 분할정복 하는 수밖에 없다!
이렇게 문제점을 나름 돌아볼 수 있는것만 해도 다행이라고 생각하겠어요! (근거없는 세상긍정)

일단 2가지 기능 정도는 필수적으로 있어야겠네요.

1. 배열에 주어진 각 단어들의 끝을 효과적으로 검사하여, 끝말잇기가 성립이 되는지 검사

2. 이미 사용된 단어 리스트에 지금 넣으려는 값이 존재하는지 검사하고, 있다면 실패 처리

음! 2번의 경우, 모든 사용된 단어리스트의 값들을 검사해보아야 하는데! 배열의 길이가 매우 길 경우에 해당 로직이 너무 효율성이 떨어질까봐 걱정이에요!

dict의 중복 Key불허용 오류를 이용하여,
사용된 단어를 key로 하는 dict를 이용해서 Try-catch로 잡아보아도 재미있을거 같은데..! 정답으로 제출된 배열을 다 순회하지 않아도 될거 같구요.

뭐, 일단은 초기 방향으로 짜보자구요!

의사코드 가봅시다!

• 주어진 배열을 순회하며, 스택에 개별 값을 순서대로 push
• push 시의 조건은 2가지인데,
  -1. 지금 넣을 값의 첫 캐피탈이 스택의 맨 뒤 캐피탈
  -2. 지금 넣으려는 원소가 스택 안에 존재하지 않을 것
• 만약 어떤 값이든 위의 2 조건을 충족시기지 못할 경우 그 원소의 인덱스를 갖고 정답 산정
• 정답은 [n - 인덱스 / n 의 나머지 , 인덱스 / n + (나머지가 0 아닌경우는 1 추가) ]
• 모든 값이 스택에 다 들어갔을 경우엔 [0,0] 리턴

각 원소의 마지막 원소만 참조하면 끝말잇기 가능여부를 알 수 있으니, "스택" 자료형을 활용하면 top의 원소참조 방식으로 쉽게 이를 알아낼 수 있다고 생각했답니다.
idx의 연산으로 답을 알아내는 저 부분이 다소 헷갈리지만,
일단 큰 틀 기준에서는 사소하고 소사한 부분 🤸
큰 Flow가 잘 흐르는지 보고, 디테일은 이따 고쳐보자구요!

좀 더 구체화된 로직을 머리에 담기 위해, 의사코드 또한 한층 더 구체화해서 작성!

인덱스 = -1
워드의 길이만큼 각 원소를 순회:
   만약 스택이 비어잇거나 / 스택의 TOP값의 끝 캐피탈이 원소의 첫 캐피탈이면서, 원소가 스택안에 없으면:
        스택에 PUSH
    아니라면:
        인덱스 = 현재 원소의 인덱스
        루프탈출
만약 인덱스가 -1 이면:
    [0,0] 리턴
아니라면:
    TMP = 인덱스 % N
    IF TMP != 0:
        [N - TMP, 인덱스 / N + 1]
    아니라면:
            [N - TMP, 인덱스 / N]

의사코드이면서, 계획될 코드의 블루프린트? 와 같은 수준으로 만들어 보았답니다!

케비넷 대여 서비스를 개발하면서 FE 개발을 진행할 때에도 느꼈었지만,

"코드란 짜는 것보다, 지그시 바라보면서 기획하고 숙고하는게 더 중요하다 ☕️"

(심지어 그게 더 빠르다)

라는 사실이, 코딩테스트에도 통하는 것일지도 모른다는 생각이 듭니다.

마음 급해봤자 되는게 없다는 깨달음!

실제로 이 정도까지 기획을 하고 나니, 블루 프린트를 기준으로 코딩을 하는 시간 자체는 정말 얼마 안 걸리더라구요! 🤡

def solution(n, words):
    answer= []
    idx = -1
    
    for i in range(len(words)):
        if len(answer) == 0 or (answer[-1][-1] == words[i][0] and words[i] not in answer):
            answer.append(words[i])
        else:
            idx = i + 1
            break
            
    if idx == -1:
        return [0,0]
    else:
        tmp = idx % n
        if tmp != 0:
            return [tmp, idx // n + 1]
        else:
            return [n, idx // n]

c를 시작으로 한 개발자이다보니.. 여전히 코드가 파이써닉 하지는 않지만..! 그래도 동작성은 좋은 느낌!
(아 물론, 마지막에 idx를 기준으로 정답을 산출하는 부분에 조금 수정이 가해졌답니다. 블루프린트가 있으니 오류 포지셔닝도 더 수월했어요!)

갈길이 먼 것은 여전하지만, 그래도,

"높은 산을 오를 때라도, 능선을 타면 조금은 편하네!"

라는 깨달음을 얻은 초보 등산가의 기분이 든달까요.

얼른 늠름한 프로 산악인이 되고 싶습니다 🏔