[Programmers] English Word Chain

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

Solution

One of the problem’s constraints says:

words is an array containing the words used in the word chain game, in order.

From this, we can see that extracting elements from words in order lets us replay the word chain.

This leads to the following algorithm:

1. Iterate through words in order, checking whether the chain continues.
2. If the chain breaks, compute the answer.

Since simply iterating through words in order is enough to simulate the game, the answer can be derived from the index $i$ and the number of players $n$:

• Which player’s turn it is:
  • $i \mod n$
  • Add +1 since counting starts from 1
• Which round it is:
  • $[ i \div n ]$
  • Add +1 since the first round counts as 1

You can compute the quotient and remainder as shown above, or use Python’s built-in divmod:

1
q, r = divmod(a, b)

Code

1
def solution(n, words):
2
    answer = [0,0]
3
    stack = [words[0]]
4
    for i in range(1, len(words)):
5
        # If the last character of the top word in the stack matches the first character of the i-th word
6
        # and the i-th word is not already in the stack
7
        if stack[-1][-1] == words[i][0] \
8
            and words[i] not in stack:
9
            stack.append(words[i])
10
        # If it can't be added to the stack, update the answer
11
        else:
12
            answer[0] = (i % n) + 1
13
            answer[1] = i // n + 1
14
            break
15
    return answer