Code Clinic | 백준 31217 코드 리뷰

백준 31217을 해결하기 위해 작성한 코드를 리뷰하는 글입니다.

코드 클리닉 - 백준 31217 코드 리뷰

코드클리닉 - 백준 31217 문제 코드리뷰

요즘 '실용주의 프로그래머'라는 책을 읽고 있다. 이 책에서 '깨진 창문을 만들지 말라'는 팁을 받았다. 이 이야기를 듣고 조금 충격적이었다. 내가 작성하는 코드가 수없이 많은 깨진 창문들이지 않았을까 하는 생각에. 더이상 깨진 창문을 만들지 않고 싶어 작성하는 코드들을 들여다 보려고 한다. 오늘 푼 백준 31217 문제의 코드를 살펴보면서, 내가 작성한 코드가 깨진 창문인지 살펴보고, 깨져 있다면 수리해 보려고 한다.

작성한 코드

import java.util.*;
import java.io.*;

public class baekjoon31217 {
    // Part 1
    static int N, M;
    static final int MOD = 1000000007;
    static List<Integer>[] graph;

    // Part 2
    public static void main(String[] args) throws IOException{
        input();
        System.out.println(search());
    }
    
    // Part 3
    private static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        br.close();
    }
    
    // Part 4
    private static int search(){
        int cnt = 0;
        for(int i=1; i<=N; i++){
            int size = graph[i].size();
            if(size>=3){
                int thisCnt = size*(size-1)*(size-2)/6;
                cnt += thisCnt;
                cnt %= MOD;
            }
        }
        return cnt;
    }
}

 

이 코드 스타일이 여태까지 내가 작성하던 전형적인 코드 스타일이다. 위의 코드는 총 4개의 부분으로 이루어져 있다.

• Part 1

해당 문제 해결을 위해서 여러 곳에서 사용되는 변수들을 정의한다.

• Part 2

모든 문제들을 문제 유형별 패키지 내의 클래스로 작성을 한다. (* github/YdMinS에서 확인 가능) 이렇게 작성을 하면 문제 하나당 하나의 클래스 파일을 작성하더라도, 클래스별로 코드를 실행할 수 있다.

• Part 3

input() 메서드를 통해서 문제 해결에 필요한 데이터를 입력받는다. 이 부분은 입력을 한 번에 입력값을 입력하는 백준 문제풀이에 특화된 부분이라고도 할 수 있고, 단일책임원칙(SRE)를 잘 따르게 구현한다고 생각하는 부분이다.

• Part 4

실제 문제 해결의 로직이 시작되는 메서드인 search()이다.

코드 분석

• 변수선언

변수들을 static으로 선언하는 이유는 전역적으로 사용하기 위해서이다. 코딩테스트를 대비하는 목적으로 작성하기 때문에 인자를 주고받는 과정을 메모리의 영향을 크게 받지 않는 한 전역적으로 작성해 왔다. 하지만 늘 작성하면서 이렇게 작성하는게 올바를지는 항상 고민하고 있었다.

해당 변수들이 사용되는 부분을 살펴보자면, 프로그램이 실행되면서 변수가 선언되고, input() 메서드가 실행되면서 할당되고, search()메서드에서 사용된다. 해당 프로그램은 search()메서드가 수행된 다음에는 출력 후 종료되는데, 변수들의 스코프가 지나치게 넓지 않는지가 기준이 될 것이다.  해당 코드는 search() 메서드를 한 번만 수행하기 때문에 해당 변수들이 정의되고 사용되지 않는 스코프는 input() 메서드가 호출되기 전까지이고, 실제 유휴스코프 또한 input() 메서드가 실행되기 전까지다. 해당 코드에서 변수를 전역적으로 사용하는 건 "ACCEPTABLE" 하다고 볼 수 있다. 하지만 이런 프로그램에서 의미있는 코드를 작성하기 위해 별도의 클래스를 만들어 (예. Graph.class) 작성하는건 코딩테스트에 적합하지 않은 over coding이 될 수 있기 때문에, 코딩테스트용 코드에 한 해서 이와 같은 스타일을 유지하는게 나쁘지 않다고 생각된다.

• 상수선언

MOD라는 상수를 선언해 사용하고 있다. 하지만 MOD는 search() 메서드, 즉 문제 해결 로직내에서만 사용된다. 이럴 경우 static으로 정의해 둘 필요가 있을지 고민이 된다. 이를 비교해 보기 위해서 시간자원과 공간자원 측면에서 비교해 보았다.

MOD	static으로 선언	local variable로 선언
변수 선언 및 할당 시간 소요	1~5 ns	2~10 ns * 함수 호출 수
호출시 시간 소요	1~2 ns	1~2ns
공간 소요	프로그램 가동 중 : 4 byte	함수 호출 전 : 0 byte 함수 호출 시 : 4 byte 함수 호출 후 : 0 byte

위와 같은 자원 소모를 예상해 볼 수 있다.

시간 자원	공간 자원
static으로 선언 시, 변수 선언 시간 및 할당이 한 번 수행되므로 함수 호출이 잦을 경우 static이 효율적이고, 함수 호출 수가 늘어날 수록 local variable의 경우 시간 소모가 누적된다.	static 변수는 프로그램 작동 내내 메모리를 차지하는 반면, local variable은 함수 작동 중에만 메모리를 필요로 한다.

이처럼 비교를 수행할 때, 아래와 같은 결과를 얻을 수 있다.

1. 함수 호출 수가 적거나 메모리 사용량이 중요한 경우라면 Local Variable이 유리할 수 있다.
2. 함수 호출 수가 많거나 성능이 중요한 경우라면 Static Variable이 유리할 수 있다.

오늘의 코드의 경우는 함수 호출 수도 적고, 함수가 종료하면 프로그램도 종료하기 때문에 두 경우 모두 "ACCEPTABLE"하다. 이럴 경우는 가독성을 위해서 변수선언들을 한 곳에 두도록 하겠다.

• main()

main() 메서드를 정의하는 이유는 각 클래스가 하나의 프로그램처럼 작동하도록 하기 위함이다. 이렇게 코드를 짤 때의 장점은 문제별 각 클래스가 하나의 프로그램 처럼 작동해 별도의 클래스 호출, 메서드 호출 없이 바로 프로그램을 작동 시킬 수 있다. 단점은 main() 메서드에서 호출하는 모든 메서드와 변수가 static으로 선언되어야 한다는 불편한 진실이 존재한다.

이 문제를 해결하기 위해선, 클래스내에 inner class를 만들어 그 안에 main() 메서드를 넣거나, main() 메서드를 포함하는 클래스의 객체를 main() 메서드 내에서 생성하는 해결하는 방법이 있을 수 있다.

그런데 역시나 코딩테스트라는 특수한 목적을 달성하기 위한 클래스를 작성하면서 이와 같은 솔루션을 생각하는 건 over coding 위험이 있어 코딩 테스트용 코드로는 적합하지 않을 수 있다. 따라서 static main() 메서드를 사용하는 것도 코딩테스트에 한해서는 계속 사용해도 괜찮을 것으로 보인다.

• input()

코딩테스트에서 입력은 input() 메서드를 이용해서 처리한다. 이 설계가 나름 SRP를 적용한 괜찮은 코드라고 생각했고 코딩테스트에 임할 때 하나의 템플릿처럼 작성할 수 있어 좋다고 생각했다. 하지만 깨진 창문 이야기를 듣고 살펴보니 살짝 수정의 여지가 있을 수 있다는 것을 알게 됐다.

모든 입력을 한 곳에서 받지 않고, 노드의 수와 연결의 수를 받는 메서드와 연결정보를 받는 메서드를 따로 구축할 수 있다. 하지만, 역시 코딩테스트용으로 작성하는 경우 완벽하게 SRP를 지키기 위해 모든 요소를 분리하는 건 짧은 시간내에 구현을 완료해야 하는 코딩테스트에 적합하지 않는 방식인 것 같다는 생각이 든다.

• search()

해당 메서드는 연결의 경우의 수를 계산 하는 부분을 메서드로 추출할 수 있다. 이 문제의 한해서는 큰 문제가 되지 않지만, 계산 부분은 메서드로 추출하는 것이 좋다. 왜냐하면 여러 조건에서 해당 계산을 여러번 수행해야 할 수도 있기 때문이다.

또한 결과인 cnt는 MOD를 이용해서 1000000007로 나눈 나머지 값을 결과값으로 출력하기 때문에, int로 충분하다. 하지만 MOD를 이용하는 것 자체가 오버플로우를 염두에 둔 것이기 때문에, 안전하게 한단계 더 큰 값을 표현할 수 있는 long을 사용하는 것이 연산 중간에 발생하는 오버플로우에 대처하며 MOD 연산을 최소로 할 수 있다.

private static long search(){
        long cnt = 0;
        for(int i=1; i<=N; i++){
            long size = graph[i].size();
            if(size>=3){
                cnt += caculateCombination(size) % MOD;
            }
        }
        return cnt;
}

private static long calculateCombination(long i){
	return i * (i-1) * (i-2) / 6;
}

결과

코드 분석을 해보니, 늘 쓰던 코드에 좀 더 확신이 생겼다. 현재 코드가 100% 좋은 코드는 아니지만 코딩테스트의 관점에서는 짧은 시간내에 해결해야 하는 과제와 코드 품질의 합의점에 잘 서있다는 느낌도 받았다. 동시에 코드 리뷰를 코딩테스트라는 너무나 특수하고 사용을 목적이 아닌 코드로 진행하는 것에는 한계가 많은 점도 느끼게 되었다. 다음 번 코드클리닉은 하나의 시스템 내에서 의미를 갖고 있는 것으로 시도해 봐야 겠다.