[프로그래머스]영어 끝말잇기

[35] 영어 끝말잇기

책 구매하기

문제 정보

• 분류: 집합
• 정답률: 70%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 집합, 중복 검사, 번호 계산, 탈락 시점
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12981

문제를 읽을 때 체크할 포인트

끝말잇기 규칙 위반 조건은 두 가지뿐이다. 이미 나온 단어를 다시 말했거나, 이전 단어의 마지막 글자와 현재 단어의 첫 글자가 다르면 된다.

연결 여부를 다시 계산하면 비효율이 커진다. 이미 같은 편인지 아닌지를 빠르게 확인할 수 있어야 하고, 그 지점에서 유니온 파인드가 바로 떠올라야 한다.

풀이 흐름

1. 첫 단어부터 순서대로 보면서 집합에 넣는다.
2. 현재 단어가 이미 나왔는지, 이전 단어와 이어지는지 검사한다.
3. 처음 위반한 위치를 사람 번호와 차례로 바꿔 반환한다.

구현할 때 놓치기 쉬운 부분

이미 나온 단어인지, 바로 직전 단어의 마지막 문자와 이어지는지를 동시에 확인해야 한다. 둘 중 하나만 검사하면 규칙 위반을 놓치게 된다.

파이썬 정답 코드

def solution(n, words):
  # 첫 단어부터 순서대로 보면서 집합에 넣는다.
  used = {words[0]}

  # 현재 단어가 이미 나왔는지, 이전 단어와 이어지는지 검사한다.
  for i in range(1, len(words)):
    # 처음 위반한 위치를 사람 번호와 차례로 바꿔 반환한다.
    if words[i] in used or words[i - 1][-1] != words[i][0]:
      person = i % n + 1
      turn = i // n + 1
      return [person, turn]
    used.add(words[i])

  return [0, 0]

시간 복잡도

N은 words의 길이이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.