[자바] 백준 25393 - 교집합 만들기 (java)

 문제 : boj25393

---

 

필요 알고리즘 개념

• 이분 탐색 (binary search)
  • 이 문제에서 매개 변수 탐색 알고리즘을 사용하기 위해 기본적으로 알아야 한다. 
• 매개 변수 탐색 (parametric search)
  • 이분 탐색에서 약간 응용된 알고리즘이다. 이분 탐색은 값 A를 찾는 것이고, 매개 변수 탐색은 값 A를 찾을 수도 있고, 그 보다 크거나 작은 수의 위치도 찾을 수 있다.
• 해시를 사용한 집합과 맵
  
  • 자바를 기준으로 해시맵 자료구조를 알고 사용할 줄 알아야 한다.
• 애드 혹
  • 애드 혹 문제이다. 이게 뭐냐면 그냥 아이디어 상품같은거라고 생각하면 된다. 보통 정형화된 방법으로 풀리지 않고 아이디어가 필요한 문제에 태그로 붙곤한다. 어찌보면 그리디에 가깝다. 이게 태그에 달려있다고 그걸보고 풀 수 있는건 아니니(?) 별로 신경 안써도 된다.

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

 

 

---

 

풀이

  좋은 문제라 생각한다. 푸는 방법도 다양하게 나올 수 있고, 아이디어도 필요하다. 실버보단 골드 하위권 정도로 생각된다.

 

  1개 이상의 최소의 구간을 선택해 '그 교집합이 정확히 [l, r]이 되도록' 만들어야 한다. 이것부터 한번 잘 생각해보자. 뭘 말하고 싶은거냐면, 애초에 3이상의 수가 답으로 나올 수 있겠냐는거다. '최소'의 구간을 선택해야 하고, 그 '교집합'이어야 하므로 가능하다면 무조건 1개 아니면 2개가 답이 될 수 밖에 없다. 예르들어 3개로 가능한 경우라면 다음과 같은 경우 뿐이다. 당연히 저 주황색 부분은 필요없는 부분으로, 파랑과 녹색 두가지만 가지고도 [l, r]을 만들 수 있다. 이게 이 문제를 풀 때 필요한 아이디어이다.

 

---

 

   좀 더 일반화해서 그럼 어떻게 [l, r]을 찾을 수 있을지 생각해보자.

 

1. 질의 'l r'에 대해 [l, r] 구간이 존재한다.

  예를들어 다음과 같은 경우이다. '3 5' 질의에 정확히 일치하는 구간이 이미 있으므로 1이 답이다.

2
3 5
4 6
1
3 5

 

2. [l, r]에 대해 [l, r 초과]인 구간과 [l 미만, r]인 구간이 존재한다.

  예를들어 다음과 같은 경우이다. '2 4' 질의에 대해 [l, r초과]인 [2, 5]와 [l미만, r]인 [1, 4]가 존재하므로 이 경우에 답은 2가 된다. 이상, 이하라 작성하지 않은 이유는 '1.'인 경우와 중복되기 때문이다.

3
2 5
1 4
3 5
1
2 4

 

3. 그 이외

  그 이외 모든 경우는 -1을 출력해주면 된다.

 

---

 

  그치만 아이디어를 알았다해도 구현을 어떻게 해야 가능할지 생각해내기 어려울 수 있다. '1.'만 해도 만약 N개를 모두 입력받아두고 Q번의 질의에 대해 N개를 찾아보며 [l, r]과 동일한 구간을 찾는다면 O(NQ)로 시간초과가 나게 된다.

 

  내 경우엔 'l' 값을 키로하고 r값을 매개변수 탐색하기 위한 자료구조를 값으로 하는 해시맵과, 반대로 'r'값을 키로하고 l값을 매개변수 탐색하기 위한 자료구조를 값으로 하는 해시맵 두개를 사용해 해결했다.

 

  참고로 매개변수 탐색은 이분탐색을 활용한 방법으로, 이분탐색 자체로는 정확히 일치한 값을 찾는 알고리즘이지만 매개변수 탐색은 거기에 더해 일치하는 값도 찾을 수 있고 그보다 크거나 작은 가장 가까운 값의 위치도 찾을 수 있다. 직접 구현해봐도 좋다. 자바에서도 이분탐색을 내장함수로 의외로 지원한다. 그치만 그걸로 매개변수 탐색을 하려면 좀 빡쌘데, 코드가 아래처럼 나온다 ㅋㅋㅋ 개인적으로 지저분하고 알아보기도 힘들어서 상당히 싫어한다.

arr.set(-Collections.binarySearch(vec, num)-1, num);

 

  자바에서 이분탐색을 직접 구현하지 않고 사용하기 좋은 방법은 TreeSet을 사용하는 것이다. BST(Binary Search Tree, 이진탐색트리) 형태로 자료를 유지하기 때문에 이분탐색을 직접 구현한 것과 동일하게 사용 가능하다. 매개변수 탐색도 이미 지원하는데, ceiling이 해당 값 이상의 최소 값을 가져온다. floor가 해당 값 이하의 최대 값을 가져온다. c++의 upper_bound, lower_bound와 동일한 개념이므로 c++에 익숙해도 사용하기 좋다. 주의점은 찾으려는 값이 존재하지 않을 시 null을 리턴한다. 그러므로 primitive type(int, long, ..)으로 받게되면 오류가 날 가능성이 있으므로 wrapper class(Integer, Long, ...)로 받아줘야 한다. 자세한 구현은 이하 코드의 getAnswer()을 참고하자.

 

  아무튼 위와 같이 매개변수 탐색으로 찾아주게 되면 Q개의 질의에 대해 매번 O(logN)으로 답을 출력할 수 있게 되므로, O(QlogN)으로 문제없이 통과 가능하다. 아이디어도 필요하고 구현력도 어느정도 필요해서 좋은 문제라 생각한다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    HashMap<Integer, TreeSet<Integer>> left = new HashMap<>();
    HashMap<Integer, TreeSet<Integer>> right = new HashMap<>();

    private int getAnswer(int l, int r) {
        if (!left.containsKey(l) || !right.containsKey(r))
            return -1;

        Integer tmp = left.get(l).ceiling(r);
        if (tmp == null)
            return -1;
        else if (tmp == r)
            return 1;

        tmp = right.get(r).floor(l);
        if (tmp == null)
            return -1;
        return 2;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            if (!left.containsKey(l))
                left.put(l, new TreeSet<>());
            left.get(l).add(r);
            if (!right.containsKey(r))
                right.put(r, new TreeSet<>());
            right.get(r).add(l);
        }

        int q = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();
        while (q-->0) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            answer.append(getAnswer(l, r)).append('\n');
        }
        System.out.print(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}