프로그래머스 알고리즘 문제 - 예상대진표(python)

문제보러가기

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

문제접근 & 로직 

1. 무시할 부분 : 대진표가 중요한게 아니다. 

2. 무시하면 보이는 핵심 : 두 숫자를 2로 나눠갈 때, 언제 몫이 같아지느냐를 묻는 문제다.

3. 주어진 두 숫자를 2로 나누어서 나오는 몫이 같아질 때까지 반복한 횟수 = 대진표에서 만나게 되는 라운드 수

4. 두 숫자에서 1을 빼준 수에서 시작한다. 왜냐면 2의 제곱수의 경우에는 그대로 계산하면 만나는데 걸리는 횟수가 늘어나 버리는 문제가 생기는걸 방지하기 위해서다. 예를들어 7과 2의 제곱수인 8의 경우에는 다음과 같은 문제가 생긴다.

# 2로 나누어서 나오는 몫의 행진
8 -> 4 -> 2 -> 1 -> 0  # 0까지 가는데 4회 계산이 필요
7 -> 3 -> 1 -> 0
# 같은 몫이 되는건 몫이 0이 되었을 때.

7과 8은 서로 첫 라운드에서 붙기 때문에 1번째 라운드에서 붙는게 맞지만, 위의 계산처럼이라면 몫이 0이 되었을 때 만나므로 4번째 라운드에서 붙는다. 이는 2의 제곱수의 경우 몫 계산이 예상했던 것보다 더 크게 계산이 되기 시작하기 때문이다. 이럴 땐 두 숫자 모두 1을 빼주면 (ex : 7, 8  -> 6, 7)

# 8은 7로, 7은 6으로 계산
7 -> 3 -> 1 -> 0
6 -> 3 ...

이렇게 되면 2로 나누었을때 1번만에 바로 몫이 같아지므로, 1라운드에서 바로 만난다. 그러므로 로직대로  계산이 시작하기 전에 두 숫자에 1씩 빼주고 시작해야 한다.

코드

def solution(n, a, b):
    count = 0  # count == 나누는 횟수

    # 2의 제곱수의 경우는 몫이 크게 계산 되는 문제가 있음
    # 그래서 두 수에 1을 빼준다.
    a, b = a - 1, b - 1 

    # 두 수가 같아질 때까지 각각 2의 몫을 구하는 연산 계속
    while a != b: 
      count += 1
      a = a // 2 
      b = b // 2
    return count

# 사실 n은 필요없음.

case1 = solution(8, 1, 2)
print(case1) # 답: 1