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

문제 풀이

 

예전엔 안 풀리던 문제가 이제는 '음~ 너무 쉽고~' 정도로 풀리는 것 같아서 기분이 좋다.

이 문제는 저렇게 말할 정도로 쉬웠기 때문에 설명을 생략할까 하다가 적어본다.

(아니 사실은 쉽게 풀어서 기분좋게 글쓴다.)

문제 조건에 써있듯이 부전승이 없다. 게다가 2^n 승의 참가자가 존재한다 = 그럼 무조건 어디선가 만난다.

그림으로 보자.

 

우리가 주의 깊게 봐야하는건 left와 right를 나누는 저 경계선이다.

저 경계선을 기준으로 left / right 나뉜다면 무조건 n번 경기를 한다.

만약 선수 a,b가 경계보다 작거나, 클경우엔?

경계선을 다시 그려준 뒤, 해당 경계에서 left / right인지 검사, 나뉜다면 n-1번 경기 아니면 다시 경계선 그리기...

이렇게 반복하는 걸 우린 어디선가 본적이 있다.

binary search와 비슷하다.

 

주의 점이 있다.

나는 a,b를 처음부터 a < b로 가정하고 풀었었다. 그래서 시간초과.

문제 조건을 보면 a≠b라고만 되어 있지 누가 큰지에 대해서는 나와 있지 않다. 이것만 조심하면 바로 문제 해결!

 

코드

def solution(n,a,b):
    answer = 0
    
    count = 0
    max_num = int(n)
    while(n != 1):
        n //= 2
        count += 1
        
    if a > b:
        a,b = b,a
    
    min_num = 1
    mid_num = max_num // 2
    while True:
        if (a <= mid_num and mid_num < b): # 경계선 기준으로 left, right로 나눠진다면
            answer = count # 답반환
            break
        else: # 안나눠진다면? 경계선(mid) 다시그리기
            if a <= mid_num and b <= mid_num:
                max_num = int(mid_num)
                mid_num = (min_num+max_num)//2
                count-=1
            else:
                min_num = int(mid_num)
                mid_num = (min_num+max_num)//2
                count-=1
    return answer

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12985#

코딩테스트 연습 - 예상 대진표