백준 문제를 풀 때, 다른 사람의 코드를 봐야하는 이유

백준 문제를 풀다가 간신히 통과하는 경우가 있다. 문제를 제출할 때, 처음부터 완벽하고 깨끗하며 효율적인 코드를 작성하기엔 어렵다. 따라서 문제에서 요구하는 사항과 기본적인 테스트 케이스를 통과하는 경우 코드가 어떻든 맞으면 장땡이다(?). 하지만 실제 코딩테스트에서 요구하는 시간제한이나 메모리 제한이 다를 수 있기 때문에 나의 정답 코드에 대해 무조건적으로 신뢰하는 것은 위험하다. 따라서 정답자의 코드 중 10위 안에 드는 코드들을 리뷰하게 되면 나의 코드가 얼마나 비효율적이고 지저분한 코드인지 알 수 있다.

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

1717번: 집합의 표현

• 유니온 파인드 알고리즘을 사용하여 해결할 수 있는 문제이다.

1. 나의 코드

package Backjoon.graph;

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

public class No1717 {
    static int[] array;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]); // 집합 개수 n 개
        int m = Integer.parseInt(input[1]); // 연산 개수 m 개
        array = new int[n + 1]; // 0 부터 n까지 인덱스를 가져야 하기 때문에 n+1 크기의 배열로 생성
        for (int i = 0; i <= n; i++) {
            array[i] = i; // 맨 처음엔 대표 노드를 자신으로 지정 -> Union 연산 시 변경 됨.
        }

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int findOrUnion = Integer.parseInt(input[0]); // 0이면 Union, 1이면 Find 연산 수행
            int first = Integer.parseInt(input[1]);
            int second = Integer.parseInt(input[2]);

            if (findOrUnion == 0) {
                int firstPresent = functionFind(first);
                int secondPresent = functionFind(second);
                if (firstPresent <= secondPresent) array[secondPresent] = firstPresent;
                else array[firstPresent] = secondPresent;
            } else {
                // Find 함수 + 출력
                if (functionFind(first) == functionFind(second)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    private static int functionFind(int node) {
        // node와 연결되어 있는 즉, 대표하는 값(최솟값) 찾기
        if (array[node] == node) return node;
        array[node] = functionFind(array[node]);
        return array[node];
    }
}

2. jkm5368님의 소스코드를 리뷰한 뒤 수정한 코드

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

public class No1717 {
    static int[] array;

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]); // 집합 개수 n 개
        int m = Integer.parseInt(input[1]); // 연산 개수 m 개
        array = new int[n + 1]; // 0 부터 n까지 인덱스를 가져야 하기 때문에 n+1 크기의 배열로 생성
        for (int i = 0; i <= n; i++) {
            array[i] = i; // 맨 처음엔 대표 노드를 자신으로 지정 -> Union 연산 시 변경 됨.
        }

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int findOrUnion = Integer.parseInt(input[0]); // 0이면 Union, 1이면 Find 연산 수행
            int first = Integer.parseInt(input[1]);
            int second = Integer.parseInt(input[2]);

            if (findOrUnion == 0) {
                // Union 함수
                functionUnion(first, second);
            } else {
                // Find 함수 + 출력
                if (functionFind(first) == functionFind(second)) {
                    sb.append("YES").append("\n");
                } else {
                    sb.append("NO").append("\n");
                }
            }
        }

        System.out.println(sb);
    }


    private static int functionFind(int node) {
        // node와 연결되어 있는 즉, 대표하는 값(최솟값) 찾기
        if (array[node] == node) return node;
        array[node] = functionFind(array[node]);
        return array[node];
    }

    private static void functionUnion(int first, int second){
        int firstPresent = functionFind(first);
        int secondPresent = functionFind(second);

        if (firstPresent <= secondPresent) array[secondPresent] = firstPresent;
        else array[firstPresent] = secondPresent;
    }
}

• 매번 System.out.println()을 통해 출력하지 않고, StringBuffer에 값을 저장한 뒤 한 번에 출력하였다.
• Union에 해당하는 연산 부분을 함수로 만들었다.

3. 속도 차이

• 그림에서 3번째가 내가 작성한 코드, 1번째가 리뷰 후 보완한 코드이다. 단순히 출력하는 방법을 바꿨는데도 64% 가까이 줄일 수 있었다. jkm5368님의 코드에는 값을 입력받을 때, BufferedReader와 split()을 사용하지 않았기 때문에 속도가 훨씬 빠르다.