백준 2668번 <숫자고르기>

백준 알고리즘 2668번

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

---

2668번

가로X세로가 N X 2인 표가 있다. 첫 행에는 1부터 N까지의 숫자가 적혀있고 두번째 행에 적혀있는 숫자는 주어진다. 이때 첫 행에서 적절히 숫자 몇 개를 뽑으면 뽑은 숫자들의 집합과 해당 숫자들의 두번째 행에 적혀있는 숫자들의 집합이 같다. 

이런 경우를 만족하도록 최대로 숫자를 뽑아라.

 

입력으로 첫 줄에 N이 주어지고 그 다음 N개의 줄에 걸쳐 1부터 N까지에 해당하는 두번째 행의 숫자가 주어진다.

 

출력으로 첫 줄에 뽑은 숫자의 개수를,  그 다음 줄부터 뽑은 숫자를 오름차순으로 출력한다.

---

문제 해결

처음에 부분집합을 사용해서 완전 탐색을 하는 방법을 생각했는데 N의 최대 숫자가 100으로 2^100은 너무 크기 때문에 다른 방법을 찾았다.

 

그러다가 찾은 방법이 입력으로 들어오는 두번째 행의 숫자들을 set(TreeSet)에 넣어서 판별하는 방법이었다.

3가지 경우로 나눠서 출력을 진행했다.

1. set의 크기가 1인 경우는 입력으로 들어오는 숫자가 1개이기 때문에 해당 숫자만 선택할 수 있다.
2. set의 크기가 N인 경우는 모든 숫자를 선택할 수 있는 경우이다.
3. 나머지 경우에는 아래와 같이 진행하였다.
   1. set에 들어있는 숫자를 첫번째 행의 값으로 생각하고 두번째 행의 값을 가지는 또 다른 newSet(TreeSet)을 만들었다. 
   2. set의 크기와 newSet의 크기가 같으면 정답을 구했기 때문에 출력을 진행하였다.

처음에는 TreeSet이 아니라 HashSet으로 구현하였는데 마지막에 오름차순으로 출력하기 때문에 정렬을 해주는 TreeSet으로 바꿔서 구현하였다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class BOJ_2688 {
    static int N;
    static int[] NUM;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        NUM = new int[N+1];
        TreeSet<Integer> set = new TreeSet<>();     // set : 입력으로 들어온 숫자들의 set
        for (int i = 1; i < N+1; i++){
            NUM[i] = Integer.parseInt(br.readLine());
            set.add(NUM[i]);
        }
        // end input

        if (set.size() == 1) {  // set의 크기가 1이라면 입력으로 들어온 숫자가 1개
            System.out.println(1);
            // 입력으로 들어온 숫자가 1개이기 떄문에 어차피 선택하는 숫자는 1개
            System.out.println(NUM[1]);
        } else if (set.size() == N) {   // set의 크기가 N이라면 다 선택하면 된다.
            System.out.println(N);
            for (int i = 1; i < N + 1; i++) {
                System.out.println(i);
            }
        }else{
            // newSet : set에 들어있는 숫자를 index로 해서 NUM 배열의 값을 가져온 새로운 TreeSet
            TreeSet<Integer> newSet = update(set);
            while (set.size() != newSet.size()) {   // set과 newSet의 크기가 같을 떄까지 반복
                set = newSet;
                newSet = update(set);
            }
            // set과 newSet의 크기가 같다면 정답을 구한 것
            System.out.println(set.size());
            for (Integer i : set) {     // TreeSet이라 정렬을 보장하기 떄문에 그냥 출력
                System.out.println(i);
            }
        }
    }
    static TreeSet<Integer> update(TreeSet<Integer> set){
        TreeSet<Integer> ans = new TreeSet<>();
        for (Integer i : set) {
            ans.add(NUM[i]);
        }
        return ans;
    }
}

---

결과

 

---

문제를 풀고나서 알고리즘 분류를 봤더니 "그래프 이론, 그래프 탐색, 깊이 우선 탐색" 이길래 놀랐다...ㅎ