[2017 팁스타운 / 프로그래머스] 12985번 : 예상 대전

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

 

Lv2 문제이고, 스스로 푼 문제다!

 

문제 이해 

a와 b 선수가 계속 이기다가 둘이 붙게되는 라운드 숫자를 반환한다 

처음에는 일일이 순서를 저장하고 두 숫자가 만날 때 라운드를 반환해야 하나 싶었지만 그렇게 하면 시간이 너무 오래 걸리고 구현도 번거로울 것 같아서 다른 방법을 생각해봤다 

 

그래서 생각한게 a 와 b의 숫자로 정답을 구할 수 있지 않을까 싶었다 

a와 b는 계속 이기니까 결국 (각각의 번호 + 1 // 2)가 해당 라운드에서 각 선수들의 순서인 것을 찾았다 

위 식은 예제에서 알아냈는데, 2라운드에서 4번은 두번째, 7번은 4번째이므로 (4 + 1) // 2 == 2, (7 + 1) // 2 == 4임을 알 수 있다

 

이렇게 했을 때 90퍼센트만 맞았는데 틀린 거를 생각해보니 

a, b = 2, 3인 경우 둘의 차이는 1이지만 실제로 둘이 마주치는 라운드는 2라운드이다. 

그래서 정답을 반환하는 경우는 차이가 1이면서 가장 작은 수가 홀수인 경우라고 생각해 코드를 작성하니 정답이 떴다 

 

- 정답 풀이 : 

def solution(n,a,b):
    x, y = min(a, b), max(a, b)
    current = 1
    
    while True: 
        if abs(x - y) == 1 and (x % 2 == 1):
            return current
        x = (x + 1) // 2
        y = (y + 1) // 2
        current += 1
        
    return current

 

- 시도해본 풀이 : 

 

2 3 인 경우 차이는 1이지만, 2라운드에서 붙는다 

하지만 이 풀이라면 3 -2 == 1이므로 1을 출력한다 

 

 둘 중 최솟값이 홀수이고, 두 수의 차이가 1일 때 같은 라운드에서 붙는다고 생각해 코드를 정답 풀이와 같이 수정했고, 정답이 떴다 

def solution(n,a,b):
    x, y = min(a, b), max(a, b)
    current = 1
    
    while True: 
        if abs(x - y) == 1:
            return current
        x = (x + 1) // 2
        y = (y + 1) // 2
        current += 1
        
    return current