프로그래머스 Level2 예상 대진표

예상 대진표

출처: 프로그래머스

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

프로그래머스

광고 게시가 없는 비영리, 비상업적 포스트입니다.

 

풀이

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var cnt = 1
        var a = a-1
        var b = b-1
        while(a/2 != b/2) {
            a /= 2
            b /= 2
            cnt++
        }
        return cnt
    }
}

 

예시를 보고 설명드리겠습니다.

n = 8 , a = 4 , b = 7 

 

현재 총 8명이 있습니다. a는 4번 b는 7번 입니다.

한 경기를 진행하면 a는 2번이 되고 b는 4번이 됩니다.

왜냐하면 1 2 3 4 5 6 7 8 이렇게 경기를 했을 때앞에 1 2 에서 1번이 나오고 3 4 에서 2번 5 6 에서 3번 7 8에서 4번 선수가 결정됩니다.그러므로  1,2,3,4,5,6,7,8번의 선수가 1경기를 하게 되면 결과로 1 2 3 4 명의 선수가 나오고 1번에는 1,2중 한 명 2번에는 3,4중에 한 명 이런식인거죠. 이해가 되시나요??

 

한 번 더 경기를 하면, 1 2 번 두 명의 선수가 결과로 나오게 되고 1번에 a가 2번에 b가 있게 됩니다. 무조건 이기고 올라오니까요.

 

하나씩 보면 a=4 -> 2 -> 1 , b = 7 -> 4 -> 2 이렇게 번호가 변경됩니다.마지막에 1번, 2번에서 둘은 대결을 하게 됩니다.

 

슬쩍 보니 /2씩 하면 어떨까요???/2를 해서 그 몫이 다음 경기의 번호가 되면 될 것 같아 보이는데...그런데 홀수는 좀 이상해보이네 이걸 어떻게 해야할까요?? 1 2 3 4 5 6 7 8 모두 /2를 하면 0 1 1 2 2 3 3 4 이렇게 바뀌게 됩니다.하나씩 밀려서 두 개가 이루어져있네요??? 그렇다면 1 2 3 4 5 6 7 8 에서 -1을 한다면??

 

0 1 2 3 4 5 6 7 을 /2 를 하면0 0 1 1 2 2 3 3 이 됩니다.

 

만약에, a = 3, b = 4에 있어서 첫 경기부터 서로 경기를 한다면 어떻게 확인해야할까요?? a = 3-1 = 2 -> 2/2 = 1b = 4-1 = 3 -> 3/2 = 11 1로 몫이 같습니다.서로 다음 라운드에 갈 수 있는 번호가 같다는 소리가 되고 다음 라운드에서 같은 번호를 받는다는 건 무조건 서로 경기를 했다는 소리이므로 확인이 가능합니다.

 

반복문을 통해 /2를 했을 때 다음 라운드가 같다면 둘은 경기를 했다고 할 수 있으므로 이에 맞게 코드를 작성해주면 됩니다. 경기를 할 때마다 각자의 번호를 /2로 줄이고 cnt를 늘리면 답을 구할 수 있습니다.