[자바] 백준 19845 - 넴모넴모 2020 (java)

목차

문제 : boj19845

 

 

필요 알고리즘

• 이분 탐색
  
  • 의외로 이분 탐색 문제이다! 물론 다른 방법들도 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  문제 설명이 좀 복잡해서 그렇지 잘 생각해보면 해야하는건 단순한 편이다.

배열 arr에다가 arr[1]부터 arr[n] 까지에 입력으로 주어진 N개의 정수 a를 순서대로 담아두었다고 해보자.

 

  우선 오른쪽으로 나가는 레이저로 몇 마리가 제거되는지만 생각해보자. 이 경우 입력으로 들어온 (x,y)값을 기준으로 arr[y] - x+1 을 하면 될 것이므로 이건 쉽게 생각할 수 있다. 수식을 말로 설명해보면 "현재 층에 arr[y] 마리가 존재하는데 레이저가 x번째부터 시작되므로, 현재 층에 존재하는 마리수 중 x번째 이상에 있던 녀석들이 제거된다"는 의미이다.

 

  그럼 위로 향하는 레이저는 어디까지 넴모들을 제거할까?

 

  일단 이걸 어떻게 해결할지 알고리즘을 먼저 생각하기보다는, 그냥 단순하게 직관적으로 생각해보면 입력으로 들어온 x값보다 더 작은 수(= x-1 이하)가 살고있는 층이 몇층인지 알아내면 된다! 예를들어 아래와 같은 상황이라면 당연히 x=3인 레이저는 arr에 들어있는 값이 3 이상인 곳에만 영향을 끼칠 수 있으므로, arr에 들어있는 값이 3 미만으로 바뀌는 위치를 찾아내면 그 층 직전까지 제거되는 것이다.

 

  하지만 매번 arr을 순회하면서 찾게 되면 O(NQ)가 되므로 통과할 수 없다. 그러므로 이제 알고리즘을 생각해봐야하는데, 뭐 펜윅이나 세그 등을 써도 되겠지만 어차피 입력은 항상 내림차순으로 들어오므로 그냥 이분 탐색으로 처리하면 된다. 다만 정확히 특정 값을 찾으라는 식으로 이분 탐색을 할 순 없고, c++에 있는 lower_bound 와 비슷하게 탐색을 해야한다(특정 값보다 작은 값). 자바에도 그게 있는데, TreeSet이나 TreeMap의 lower 함수를 쓰면 된다(미만이 아니라 이하를 탐색하려면 floor).

 

  이 때 TreeSet으로 처리하려면 커스텀 정렬을 구하기가 상당히 어려워져서, TreeMap으로 key는 arr[인덱스], value는 인덱스로 해주면, lower을 통해 특정값 미만의 인덱스 위치를 알 수 있게 된다. 주의점은 특정값 미만인 '가장 작은 인덱스'를 찾아야 한다는 점이다. 즉, arr = [3, 3, 2, 2, 2] 일 경우 3 미만을 찾는다고 하면 결과가 2가 나와야지(처음 3미만인 값으로 바뀐 인덱스), 3이나 4가 나오면 안된다.

int[] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
    if (tm.containsKey(arr[i])) continue;	// 해당 값의 최소 인덱스를 유지하기 위한 부분
    tm.put(arr[i], i);	// TreeMap에 넣기
}

StringBuilder sb = new StringBuilder();
while (q-->0) {
    st = new StringTokenizer(br.readLine());
    int c = Integer.parseInt(st.nextToken());
    int r = Integer.parseInt(st.nextToken());

    if (c > arr[r]) {	// 이미 arr[y]보다 x가 크다면 무시
        sb.append(0).append('\n');
        continue;
    }
	
    // arr[r]-c+1 은 우측으로 제거되는 부분.
    // tm.lowerEntry(c).getValue()-1-r 은 위쪽으로 제거되는 부분.
    sb.append(arr[r]-c+1+tm.lowerEntry(c).getValue()-1-r).append('\n');
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        TreeMap<Integer, Integer> tm = new TreeMap<>();
        tm.put(0, n+1);

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (tm.containsKey(arr[i])) continue;
            tm.put(arr[i], i);
        }

        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            if (c > arr[r]) {
                sb.append(0).append('\n');
                continue;
            }

            sb.append(arr[r]-c+1+tm.lowerEntry(c).getValue()-1-r).append('\n');
        }

        System.out.print(sb);
    }
}