프로그래머스 - 12985번: 예상 대진표 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    static int answer = 0;
    private static void subdivision(int a, int b, int left, int right, int cnt) {
        if(left == right) return;
        int mid = (left + right) / 2;
        
        boolean[] check = new boolean[2];
        if(left <= a && mid >= a) check[0] = true;
        if(mid + 1 <= b && right >= b) check[1] = true;
        
        if(check[0] && check[1]) {
            answer = cnt;
            return;
        }
        else if(check[0])
            subdivision(a, b, left, mid, cnt - 1);
        else
            subdivision(a, b, mid + 1, right, cnt - 1);
    }
    
    public static int solution(int n, int a, int b) {
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            if((int)Math.pow(2, i) == n) {
                cnt = i;
                break;
            }
        }
        
        subdivision(Math.min(a, b), Math.max(a,b), 1, n, cnt);
        return answer;
    }
}

2. 설명

public static int solution(int n, int a, int b) {
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if((int)Math.pow(2, i) == n) {
            cnt = i;
            break;
        }
    }

    subdivision(Math.min(a, b), Math.max(a,b), 1, n, cnt);
    return answer;
}

cnt는 정답의 최대 수입니다. 대진표의 result의 값으로 가장 큰 값은 n이 8일 경우 2^3 = 8이기에 3입니다. 즉, 2의 몇 제곱으로 되는지 알면 result의 최대값을 구할 수 있습니다.

테스트 케이스 중에서 a가 b보다 큰 경우가 있기에 그것을 통일하기위해 작은 값은 a로 큰 값은 b로 지정합니다.

static int answer = 0;
private static void subdivision(int a, int b, int left, int right, int cnt) {
    if(left == right) return;
    int mid = (left + right) / 2;

    boolean[] check = new boolean[2];
    if(left <= a && mid >= a) check[0] = true;
    if(mid + 1 <= b && right >= b) check[1] = true;

    if(check[0] && check[1]) {
        answer = cnt;
        return;
    }
    else if(check[0])
        subdivision(a, b, left, mid, cnt - 1);
    else
        subdivision(a, b, mid + 1, right, cnt - 1);
}

subdivision은 수를 절반으로 나누는 작업을 재귀 형태로 진행합니다. a가 작은 값이며 b는 큰 값이기에 left와 right을 기준으로 반으로 나누었을 때 a가 왼쪽에 속한다면 check[0]을 true, b가 오른쪽에 속한다면 check[1]을 true로 변환합니다.

만약 왼쪽과 오른쪽에 각각 a와 b가 존재한다면 answer에 현재 cnt의 값을 저장 후 함수를 종료합니다.

만약 a가 왼쪽에 존재하는데 b가 오른쪽에 존재하지 않으면 왼쪽에 a와 b가 존재한다는 것을 의미하기에 right의 값을 mid로 지정하여 왼쪽 부분만 분리하여 진행합니다.

만약 오른쪽에만 b가 존재하고 왼쪽에 a가 존재하지 않는다면 오른쪽에 a와 b 모두 존재하기에 left의 값을 mid + 1로 지정하여 오른쪽만 다시 분리하며 진행합니다.

3. 정리

1. 분할 정복 알고리즘에서 분할을 이용하여 문제를 해결하는 것이 적합하다고 판단하여 Top-Down 형식으로 진행
2. 다른 사람의 풀이를 보면 압도적으로 간단해지는데 해당 방식은 제가 스스로 떠올릴 수 있는 것이 아니지만 참고 바람

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges