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

class Solution {
    public int solution(int n, int a, int b) {
        int answer = 0;
        int divideNum = n / 2;
        int middleNum = n / 2;
        
        while(divideNum > 1) {
            //한쪽에 몰려 있다면?
            if(middleNum < a && middleNum < b){
                divideNum /= 2;
                middleNum = middleNum + divideNum;
            } 
            else if (middleNum + 1 > a && middleNum + 1 > b) {
                divideNum /= 2;
                middleNum = middleNum - divideNum;
            }
            //한쪽에 몰려 있지 않다면?
            else {
                answer = (int) (Math.log(divideNum * 2) / Math.log(2));
                break;
            }
        }
        
        if(divideNum == 1) {
            answer = 1;
        }

        return answer;
    }
    
}

 

풀게된 의식의 흐름

1. list pair로 계속 한칸씩 비교? 비효율적이여보임
2. 일단 반은 갈라봤는데 반을 갈라놨을 때 무조건 나눠진 곳의 끝에 도달해야 마주침
3. 그러면 반을 갈라놓은 동일한 곳에 있을 때는 어떻게?
4. 확인해보니 해당 곳에서도 또 반을 가를 수 있는 패턴이 보임
5. 해당 패턴을 공식화

한 쪽에 쏠릴때마다 마추질 곳의 위치는 n / 2

중앙의 위치는 n / 2 +- (n/2)/2

divide +- divide / 2

 

느낀점

확실히 규칙을 파악하고 천천히 그 조건들을 적어가면서 푸니까 비효율적인 방식에 대한 생각을 덜하게 되는 것 같다. 그런데 다른 사람이 비트연산으로 O(1)로 풀은 것을 보고 대단하다고 느꼈고 어떤 원리인지 찾아봤는데 신기했다. 2진법에 대한 생각도 많이 해봐야겠다.

 

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

프로그래머스