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

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

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

---

-풀이-

대진표의 구조이다. 1번과 2번은 한 라운드가 끝나면 승자는 1번이되고, 3번과 4번은 2번, 5번과 6번은 3번, 7번과 8번은 4번이 된다. 다음라운드에서 1번과 2번중 승자는 1번이되고, 3번과 4번은 2번이된다.

 

여기서 규칙이있다.

1) 각 라운드가 끝나고 승자는 (자신의 번호 + 1) / 2가 된다.

2) 다음 라운드에서 붙게될 대상은 홀수 vs 짝수가 되고, 짝수-홀수 = 1이 된다.

 

따라서 라운드를 지나가면서 큰수-작은수=1 이면서 큰수%2==0 이고, 작은수 %2==1 이 되는 지점을 찾아서 break를 해준 뒤, 값을 return 해주면 된다.

 

-시간복잡도-

N의 최댓값은 2^20 이므로 , 최대 높이는 Log(N) = 20이 된다. 따라서 최악의 경우 모든 높이를 거슬러 올라가야하므로, 시간복잡도는 O(1)이 된다.

 

-코드-

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    if(a>b){
        int temp=a;
        a=b;
        b=temp;
    }
    
    while(true){
        answer++;
        
        if(b-a==1&&a%2==1&&b%2==0){
            break;
        }
        
        else{
            a=(a+1)/2;
            b=(b+1)/2;
        }
    }
    return answer;
}