[백준(JAVA)] 2668번: 숫자고르기

문제

✔ 난이도 - Gold 5

설명

처음 생각

2개~N개 조합을 쭉 뽑으면서 검사
그러니까 1~N 까지 돌면서 2개씩 뽑는 조합을 검사하고 그다음은 1~N까지 돌면서 3개씩 뽑는 조합을 검사하고,,, 이걸 N개씩 뽑는 조합까지 검사
N개 중에 2개를 뽑고, 3개를 뽑고... 이렇게 모든 조합을 다 확인
-> N은 최대 100 -> 100개 중 몇 개를 뽑는 모든 경우의 수는 2^100 -> 시간초과!!!

올바른 설계

1이 3을 가리키고 2가 1을 가리키고 3이 1을 가리킨다고 생각하자. 즉, 첫줄의 수가 두번째줄의 수를 가리킨다고 생각하자.
1이 3을 가리킬 때, 3은 또 1을 가리키고 있다. 즉, 1 -> 3 -> 1 이런 순환구조가 생김. 그럼 1은 뽑아야하는 수인 것!!!
-> 내가 어떤 숫자를 골랐을 때, 그 숫자들이 위아래 세트가 똑같으려면 출발한 숫자가 결국 다시 자기 자신으로 돌아와야 함. 즉, 사이클이 이루어지면 뽑아도 되는 숫자인 것!

⚠️ 1 -> 3 -> 2 -> 1 이럴수도 있음 ⚠️
⚠️ 1 -> 3 -> 2 -> 3 -> 2 이럴수도 있음 ⚠️
이런 엣지케이스들도 생각해야함

💡 이 문제는 "모든 숫자가 단 하나의 화살표만 가진다" 라는 특징이 있음.
즉, 갈림길이 없다는 뜻. 그냥 쭉 따라가기만 하면 된다. 이런 경우에는 복잡한 Stack 객체보다 재귀 함수나 단순한 while문이 훨씬 좋음.

왜 1 -> 3 -> 1 일때 1과 3 둘 다 안뽑고 1만 뽑음?

사이클에 포함되는 수를 한 번에 다 뽑으려면
1. 매 검사때마다 어떤 수를 거쳐왔는지 리스트를 확인해야하고
2. 매 검사때마다 내부 사이클이 없는지 확인하는 subVisited도 필요하고
3. 전체적으로 방문여부를 확인하는 글로벌 visited도 필요하다

너무 많은 체크를 해줘야하므로 헷갈리고 복잡해진다.

또한 N=100에서는 속도 차이가 의미없다.

• 지금 방식: 최대 $100 \times 100 = 10,000$번 연산
• 최적화 방식: 최대 $100$번 연산

컴퓨터에게 1만 번과 100번의 차이는 0.0001초와 0.000001초의 차이 정도. 사람이 느끼기엔 둘 다 즉시 끝나는데 굳이 로직을 복잡하게 만들어서 위험을 감수할 필요가 전혀 없다.

알고리즘 문제 풀이에서 제한 시간 내에 들어오는 가장 단순한 로직이 가장 좋은 로직이다.
$N$이 100,000처럼 매우 컸다면 현재 방식은 시간 초과가 났을 것이고, 그때는 어쩔 수 없이 복잡한 $O(N)$ 방식을 고민해야 했을 것.
하지만 지금은 $N=100$이므로, 현재의 헷갈리지 않게 하나씩 꼼꼼히 보는 풀이도 좋다.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] graph = new ArrayList[N+1];
        for (int i = 1; i <= N; i++){
            graph[i] = new ArrayList<Integer>();
        }

        for (int i = 1; i <= N; i++){
            int input = Integer.parseInt(br.readLine());
            graph[i].add(input);
        }
        // 그래프 연결 끝

        // boolean[] visited = new boolean[N+1];
        ArrayList<Integer> answer = new ArrayList<>();

        for (int i = 1; i <= N; i++){
            int flag = 1;
            boolean[] visited = new boolean[N+1];

            int first = i;
            int second = graph[first].get(0);

            while (second != i){

                if (visited[second]){
                    flag = 0;
                    break;
                }   

                visited[second] = true;

                second = graph[second].get(0);
            }

            if (flag == 1){
                answer.add(i);
            }

        }
        
        sb.append(answer.size()).append("\n");
        for (int i = 0; i < answer.size(); i++){
            sb.append(answer.get(i)).append("\n");
        }

        
        System.out.println(sb);
    }
}

⏰ 시간복잡도

$O(N^2)$