[programmers] 예상 대진표

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

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

 

 

접근 방법

n은 2의 지수승이니까 n/2를 기준으로 a와 b가 왼쪽이냐 오른쪽이냐 구하고,
다른 쪽에 있다면 그 번호가 몇 번이든 2**answer == n 인 answer만큼 무조건 비교해야 한다고 생각.

 

예를 들어, n=16이고 a가 1~8이고, b가 9~16 사이의 값이라면 무조건 4번은 비교.

마찬가지로, n=16이고 a가 1~4, b가 5~8이면, 9~16은 어차피 상관없으니까 무시하고 n=n//2해서 n=8일때 비교하는 것과 결국 같아진다. -> 재귀 함수로 처리

 

첫 코드

def solution(n,a,b):
    answer = 0
    if a>b :    #a를 작은 수로 만들기
        a,b = b,a

	if a <= n//2 and b > n//2:
		for i in range(1,n//2+1):
			if 2**i == n:
				return i
	else:
		return solution(n//2,a,b)

위 코드는 [16, 9, 12] ->2 반례를 고려하지 못 한다.

즉, 단순히 a와 b가 서로 다른 쪽에 있을 때와 그렇지 않을 경우만 조건을 나누어 처리하는데, 9,12와 같이 같은 그룹이지만 두 수가 모두 n//2보다 클 때, 런타임 에러로 실패한다. 

 

 

정답 코드

def solution(n,a,b):
    answer = 0
    if a>b :    #a를 작은 수로 만들기
        a,b = b,a
    
    if a <= n//2 and b > n//2:
        for i in range(1,n//2+1):
            if 2**i == n:
                return i
    elif a > n//2 and b> n//2:
        return solution(n//2,a-n//2,b-n//2)
    else:
        return solution(n//2,a,b)

조건을 세분화해서 처리해주면 되는데, a와b가 모두 n//2보다 클 때는 재귀함수 호출 시, n=n//2의 값을 전달하므로, a와 b도 n//2만큼 뺀 값을 새로 전달해주면 된다.