프로그래머스 - 예상 대진표(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

토너먼트로 서로가 무조건 이기면서 올라간다고 했을 때, 몇번째에 상대방과 만나게 되는가?

 

[접근 방법]

토너먼트를 그림으로 그려보면 완전 이진트리를 이루는 걸 알 수 있다.

자료구조 시간에 이진트리를 배울 때 배열로 구현하는 경우

(자식 노드/2) == 부모의 인덱스가 된다.

따라서, 부모의 노드를 계속 구하다가 같은 부모를 만나게 되는 순간이 상대방을 만나게 되는 순간이다.

시간복잡도는 O(logN)

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        // n명 참가.
        // 완전 이진트리.
        var aLoc = a - 1 + n
        var bLoc = b - 1 + n
        var cntOfOperation = 0

        while (aLoc != bLoc) {
            cntOfOperation++
            aLoc /= 2
            bLoc /= 2
        }

        return cntOfOperation
    }
}