[프로그래머스]예상 대진표

[28] 예상 대진표

책 구매하기

문제 정보

• 분류: 트리
• 정답률: 68%
• 권장 시간 복잡도: O(log N)
• 핵심 키워드: 토너먼트, 반복, 짝수/홀수, 라운드 계산
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12985

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

대진표를 직접 만들 필요는 없다. 각 라운드가 끝날 때마다 번호가 (번호+1)//2로 줄어든다는 사실만 이용하면 두 사람이 만나는 라운드를 바로 셀 수 있다.

대진표를 한 칸씩 그려가며 따라갈 필요는 없다. 매 라운드가 끝날 때마다 참가자 번호가 다음 라운드 번호로 압축된다고 보면 되고, 두 번호가 같아지는 순간이 만나는 라운드이다.

풀이 흐름

1. 두 참가자 번호가 같아질 때까지 반복한다.
2. 매 반복마다 a와 b를 각각 (x+1)//2로 갱신한다.
3. 반복 횟수를 세면 정답이다.

구현할 때 놓치기 쉬운 부분

대진표를 직접 만들 필요는 없지만 번호를 다음 라운드 번호로 바꾸는 과정에서 홀수와 짝수 처리를 정확히 해야 한다. (x + 1) // 2를 끝까지 일관되게 써야 오프바이원 실수를 막을 수 있다.

파이썬 정답 코드

def solution(n, a, b):
  # 두 참가자 번호가 같아질 때까지 반복한다.
  round_count = 0

  # 매 반복마다 a와 b를 각각 (x+1)//2로 갱신한다.
  while a != b:
    # 반복 횟수를 세면 정답이다.
    a = (a + 1) // 2
    b = (b + 1) // 2
    round_count += 1

  return round_count

시간 복잡도

N은 전체 참가자 수이고, 실제 반복 횟수는 라운드 수에 비례한다.

반복 한 번이 끝날 때마다 대상 크기가 절반 가까이 줄어드는 구조이다. 그래서 전체 반복 횟수는 N이 아니라 라운드 수에 해당하는 log N만큼만 필요한다.

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

해시태그

#프로그래머스 #코딩테스트 #알고리즘 #파이썬 #자료구조 #시간복잡도 #트리 #예상대진표 #코딩테스트합격자되기 #박경록