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

1. 문제

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

프로그래머스

 

2. 접근

1. 틀렸던 나의 풀이 [ 3번째 ] 를 보자

- 2 ** 최대횟수 = n이라는 것을 이용했다 [ math.log2(n) == 최대횟수 ]

- 나는 a,b 사이에서 누가 더 큰지는 관심 없었고,n // 2 값을 기준으로 둘다 한방향 안에 있는가 없는가를 체크했다

- 한뱡향에 있다면 a,b 가 홀수 짝수 인지 판별하고, a,b,n 값을 조정했는데, test case에서 반타작,,,,,,

 

2. 다른 사람 풀이[ 2번째 풀이 ]를 보니까 나는 최대횟수에서 깍아 내리고, n의 값을 변경하는데 중점을 뒀는데, 그게 아니라 애초에 a,b의 값에대해서만 중점을 두어서 a != b 면 같아질때까지 그냥 while문을 돌렸다.. [ 난 생각도 못했던 방법이다.. ]

 

3. 첫번째 풀이는 a,b에 대한 우위를 가른다.

- 둘 중의 작은값은 마지막에 홀수가 될 수 밖에 없다. 그래서 최대횟수 동안을 for문의 범위로 두고, if문이 저래 나오는거다

[ 왜 홀수가 되냐하면, 예시로 1 ~ 2, 3 ~ 4, .. n-1 ~ n 보면 n-1은 항상 홀수이니까~~ ]

 

3. 풀이

# 1개의 방법
import math
def solution(n,a,b):
    a, b = min(a,b), max(a,b)
    for k in range(1, int(math.log2(n))+1):
        if a%2 != 0 and a+1 == b: 
            return k
        else:
            n, a, b = n/2, math.ceil(a/2), math.ceil(b/2)

# 2번째 방법
import math

def solution(n,a,b):
    ans = 0 
    while True:
        
        if a == b:
            break
        
        ans += 1
        a,b = (a+1)//2, (b+1)//2
        
    return ans

# 틀렸던 내 방법
import math

def solution(n,a,b):
    maxCnt = int(math.log2(n))
    
    while abs(a-b) > 1:
            
        if (a <= (n //2) and b <= (n//2)) or (a > (n //2) and b > (n//2)): # n//2 기준으로 왼쪽 혹은 오른쪽 어느쪽에 분포된지 확인하기 위함
            maxCnt -= 1
            if a % 2 == 1: 
                a += 1
            if b % 2 == 1:
                b += 1
            a //= 2
            b //= 2

        else:
            break
            
        n //= 2 
        
        
    return maxCnt