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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

A와 B가 다음라운드로 이동했을 때 몇 번으로 번호가 바뀌는지를 파악하고 그 둘의 번호가 같은지를 체크해야한다.

 

번호가 몇번으로 바뀌는지 체크하는 것은 간단하다.

1과 2의 승자는 다음 라운드에서 1이 되고 3과 4의 승자는 다음 라운드에서 2가 된다.

 

일반화하면 N-1과 N이 만나면 그 라운드의 승자는 N/2가 된다.

이를 조금 다르게 생각하면 각 번호에서 1을 더한 값을 2로 나눈 몫이 다음 라운드에서의 번호가 된다.

 

 

이렇게 해서 A, B 다음 라운드에서의 번호를 구하고 그 두 번호가 같은지만 체크하면 된다.

코드로 보도록하자.

3. 내 코드

---

class Solution
{
    public int solution(int n, int a, int b)
    {
        int round = 0;
        while(a != b) {
            round++;
            
            a = (a + 1) / 2;
            b = (b + 1) / 2;
        }
        
        return round;
    }
}

시간 복잡도

• O(logN)
  

최악의 경우는 하나가 1이고 다른 하나가 N인 경우인데 이 경우에도 logN만큼의 연산이 발생하게 된다.

따라서 시간복잡도는 O(logN)이 된다.