카드게임 문제

비전공 개발자로 CS공부를 하면서 가장 어려운 것은 역시 알고리즘이다. 나에게 알고리즘 문제는 마치 아이큐 테스트 같이 느껴진다. 공부를 해도 발전이 느껴지지 않는다. 그럼에도 대부분의 기업에서 알고리즘 문제로 코딩테스트를 보기 때문에 특히 좋은 회사일 수록 어려운 문제를 내는 경향이 뚜렷하기에 손에서 놓을 수가 없다.

 

이번에 푼 문제는 프로그래머스에서 제공하는 문제다. 혹시 저작권 문제가 있을지도 몰라 문제의 내용은 링크로 대체한다. 이번 풀었다고는 했지만 이 문제를 거의 2주일 동안 고민했다. 물론 매일매일 이어지는 야근 속에 깊이 고민할 시간이 대체로 부족하기는 했지만 그럼에도 2주 동안 답을 찾지 못하고 있었다.

 

그러다 오늘 아침 조금 일찍 출근해 문제를 풀다보니 실마리가 보였다. 순식간에 답을 완성하고(사실 문제를 풀 때, 정답을 생각하는 시간이 오래 걸리는 것이지 코드를 짜는데는 5분도 걸리지 않는다) 채점을 해보니 통과다. 알고리즘 문제를 일일이 블로그에 포스팅하지 않으려고 했지만 제법 감동적인 순간이라 이 풀이는 꼭 남기고 싶다.

 

먼저 문제를 이해해야 한다. 이 카드게임에서 카드가 제거되는 경우는 세 가지 이다. 왼쪽 카드만 제거(점수 없음), 오른 쪽 카드만 제거(카드에 적힌 숫자만큼 점수), 둘 다 제거(점수 없음). 점수가 나는 경우는 오로지 오른쪽 카드'만' 제거될 때이다.

 

처음에는 이 문제를 완전탐색으로 접근했다. 아마 실제로 이런 문제가 코딩테스트에 나왔고 쉽게 답이 떠오르지 않는다면 나는 완전탐색을 사용했을 것이다. 가지치기를 잘 하면 시간안에 할 수 있지 않을까 생각했는데 왠걸 효율성 테스트가 아닌 곳에서도 시간초과가 나왔다.

 

시간을 줄이기 위해 cache라는 2차원 배열을 사용했는데 [왼쪽카드번호][오른쪽카드번호]로 배열의 행열을 구분하고 해당하는 카드가 남아있을 때 최고점수를 저장했다. 그러면 완전탐색 코드에서 다시 이 배열에 새로운 점수를 넣으려고 할 때 이미 저장된 점수가 더 높다면 더 이상 탐색을 할 필요가 없어진다.

 

이 부분에서 나는 이 문제가 동적 계획법으로 풀릴 수 있다는 것을 깨닳았다. 그런데 실제로 문제를 푸는 것은 동적계획법으로 풀어야 겠다고 생각한 이후 거의 2주일이 흘러서 였으니...

 

아무튼 cache[i][j] 에서 i, j 번째 카드들이 남아있을 때 선택할 수 있는 경우는 오른쪽 카드만 버리는 경우(오른쪽 카드 숫자가 더 작다면) [i][j+1], 둘 다 버리는 경우 [i+1][j+1], 왼쪽 카드만 버리는 경우 [i+1][j] 세 가지 이고, 해당하는 cache 배열에는 가장 큰 값이 들어가야 한다.(더 큰 값이 있으면 값을 바꿀 필요가 없다. 위에서 탐색을 종료하는 것과 마찬가지)

 

경우는 세가지로 간단한데 문제는 어떤 경우에는 해당하는 카드에 도달할 수 없을 때가 있다는 것이다. 가령 왼쪽 i번째 카드의 숫자가 작아서 앞에서 카드를 둘 다 버리고 나면 오른쪽 j번째 뒤쪽의 카드는 사용할 수 없다. 이런 체크를 하기위해 check 변수를 만들고 고민을 거듭했는데 사실 바보같은 짓이었다 그냥 cache를 애초에 -1 같은 숫자로 채워 놓고 접근 가능한 곳만 점수를 입력하도록 만들면 되는 것이었다.

 

말로 하니까 설명이 복잡한데 코드를 보면 이해가 쉬울 것이다.

    public int solution(int[] left, int[] right) {
    	int max = 0;
    	int[][] cache = new int[left.length+1][right.length+1];
    	
    	for (int i = 0; i <= left.length; i++) {
    		for (int j = 0; j <= right.length; j++) {
    			cache[i][j] = -1;
    		}
    	}
    	
    	cache[0][0] = 0;
    	
    	for (int i = 0; i < left.length; i++) {
    		for (int j = 0; j < right.length; j++) {
    			if (cache[i][j] == -1) {
    				continue;
    			}
    			if (left[i] > right[j] && cache[i][j+1] < cache[i][j] + right[j]) {
    				cache[i][j+1] = cache[i][j] + right[j];
    			}
    			if (cache[i+1][j+1] < cache[i][j]) {
    				cache[i+1][j+1] = cache[i][j];
    			}
    			if (cache[i+1][j] < cache[i][j]) {
    				cache[i+1][j] = cache[i][j];
    			}
    		}
    	}
    	
    	for (int i = 0; i <= left.length; i++) {
    		if (cache[i][right.length] > max) {
    			max = cache[i][right.length];
    		}
    		if (cache[left.length][i] > max) {
    			max = cache[left.length][i];
    		}
    	}
    	return max;
    }

이 보다 훨씬 간단하게 코드를 구사한 사람들도 많은데 나의 코드는 조금 번잡하다. 그래도 기본적인 원리는 똑같다.