[브루트포스/자바] 코드트리 NM. 가장 작은 x 찾기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 해석

* 양의 정수 x에 2를 곱하는 연산을 n번 반복
1. 2를 곱할 때마다 매번 현재 숫자의 범위에 대한 단서 제공
2. 가능한 x값 중 최솟값 구하는 프로그램 작성

-> n이 10 이하의 양의 정수이므로 완탐 로직 중 브루트포스로도 충분히 풀 수 있다.

 

풀이 로직

n loop 아래에 주어지는 두 개의 수를 입력
두 수를 2의 거듭제곱으로 나눠서 x의 범위를 추산

해당 범위의 숫자를 모두 트리맵에 등록하고, count.

for loop 끝나면 tm의 키를 순회하며 value 중에서 모든 조건을 충족한(count == n) key 중 가장 작은 key 출력(첫번째 key)

package 코드트리.시뮬레이션.공간칠하기;

import java.io.*;
import java.util.*;

public class 가장작은X찾기 {
    /*
    * 문제:
    * 양의 정수 x에 2를 곱하는 연산을 n번 반복
    * 1. 2를 곱할 때마다 매번 현재 숫자의 범위에 대한 단서 제공
    * 2. 가능한 x값 중 최솟값 구하는 프로그램 작성
    * */

    /*
    * 풀이:
    * n loop 아래에 주어지는 두 개의 수를 입력
    * 두 수를 2의 i제곱만큼 나누고 그 사이의 숫자를 ts과 비교하여, 중복되는 숫자들만 체크
    * 중복되는 숫자로만 다시 구성.
    * for loop 끝나면 ts.first() 출력
    * */
    private static int n;
    private static TreeMap<Integer, Integer> tm = new TreeMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            Double a = Double.parseDouble(st.nextToken());
            Double b = Double.parseDouble(st.nextToken());
            int num = (int) Math.pow(2, i);
            int resA = (int) Math.ceil(a / num);
            int resB = (int) (b / num);
            for (int j = resA; j <= resB; j++) {
                tm.putIfAbsent(j, 0);
                tm.put(j, tm.get(j) + 1);
            }
        }
        for (Integer key : tm.keySet()) {
            if (tm.get(key) == n) {
                System.out.println(key);
                break;
            }
        }
    }
}

트리맵을 이용하여 "가장 작은 key 찾기"를 해결하였다.

 

사실 간단하고 단순한 완탐 문제인데, 이전에 실패했던 제출 이력이 있길래 한번 확인해 봤다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int n = Integer.parseInt(br.readLine());
    int a, b;
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 1; i <= n; i++) {
        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        for (int x = 1; x <= 5000; x++) {
            if (inRange(a, b, (int) (x * (Math.pow(2, i))))) {
                set.add(x);
            } else {
                set.remove(x);
            }
        }
    }
    System.out.println(set.first());
}

    public static boolean inRange(int a, int b, int x) {
        return x >= a && x <= b;
	}
}

위 로직을 보면 트리맵이 아니라 트리셋을 활용하였고, 의도했던 로직은 가상의 x를 설정하여 냅다 매번 주어지는 범위 내에 있는지 계산하고, 범위 내의 x라면 treeset에 대입하는 로직을 생각하였다. (여기서 x가 5,000까지인 이유는 주어지는 a,b의 범위가 최대 10,000이기 때문이며, 그렇다면 x는 최대 5000부터 시작하면 b가 첫번째에 10,000이 주어져도 범위에 들어올 수 있기 때문이다.)

 

이는 정말 문제 그대로 옮긴 것으로, 가장 단순하게 떠올릴 수 있는 로직인 것 같다. 이 로직의 가장 큰 맹점은, 매번 그 때마다 딱 한번만 조건을 통과하면 set에 x가 저장된다는 것이다. 과거의 나는 이를 인지하지 못했던 것 같다. 즉, 이전 조건을 만족하지 못했어도, 나중에 만족하면 set에 해당 숫자가 추가된다. 지워지는 부분은 x를 완탐하기 때문에 이전 조건을 만족했으나 지금은 만족 못하면 지워지지만, 현재만 만족하면 지난 시간에 어떻게 했든 set에 추가되어 정답 후보로 올라가게 되는 것이다...

 

그리고 사실 지금와서 생각하는거지만, x를 계속 1부터 5000까지 훑는다는 발상을 한 과거의 내가 신기하다... 뭔가 무식한 로직이라 꺼려졌을 것 같은데, 과거의 나는 뇌마저 브루트했던 것 같다.