백준 14002번 자바

문제

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

14002번: 가장 긴 증가하는 부분 수열 4

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int[] sequence = new int[A];
		int[] dp = new int[A];
		int lengthMax = 0;
		int valueMax = 0;
		List<Integer> temp = new LinkedList<Integer>();
		
		for (int i=0; i<A; i++) {
			sequence[i] = sc.nextInt();
		}
		
		int cnt = 1; // 부분수열의 길이
		for (int i=0; i<A; i++) {
			dp[i] = 1;
			
			for (int j=0; j<i; j++) {
				
				if (sequence[j] < sequence[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			
			for (int k=0; k<=i; k++) {
				if (dp[i]-dp[k] == 1 && sequence[i] > sequence[k] && cnt == dp[k]) {
					cnt++;
					temp.add(sequence[k]);		
					break; // 중복된 길이를 방지하기 위해 탈출
				}
			}
		}
		
		for (int i=0; i<dp.length; i++) {
			if (lengthMax < dp[i]) {
				lengthMax = dp[i];
				valueMax = i;
			}
		}
		System.out.println(lengthMax);
		
		for (int i=0; i<temp.size(); i++) {
			System.out.print(temp.get(i) + " ");
		}
		System.out.print(sequence[valueMax]);
		
	}
}

 

1. 뭔가 풀릴듯 안 풀릴듯해서 계속 헤맸던 문제다. 결국 정답을 보고 내 접근 방식 자체가 잘못됐다고 깨달았다. 천천히 삽질했던 과정을 복기하면서 다음엔 같은 실수를 하지 않게 노력해야겠다. 일단 위의 코드는 올바른 풀이가 아니다.

 

2. 위의 코드의 반례가 도저히 생각나지 않아 새롭게 메소드를 만들어 임의의 같은 수를 전달해 반례를 찾아냈다.

8	10	5	3	6	1	2	5	6	8
1	2	1	1	2	1	2	3	4	5

윗줄은 sequence의 배열 값이고, 아랫 줄은 해당 수까지의 부분수열의 길이(dp)다. 반례를 보고 바로 뭐가 문제 였는지 알아냈다. 

 

내가 작성한 코드는 dp배열을 생성하면서 앞쪽부터 탐색을 진행해 틀린것이다. 다시 말해 기본적인 수열의 특성을 전혀 고려하지 않았다. 양의 방향으로 계속 커지기에 배열의 끝부터 탐색을 했어야 했다. 만약에 실제 코딩테스트였다면 여지없이 틀렸을 문제다. 

 

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main14002 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int[] sequence = new int[A];
		int[] dp = new int[A];
		int max = 0;
		List<Integer> temp = new LinkedList<Integer>();
		
		for (int i=0; i<A; i++) {
			sequence[i] = sc.nextInt();
		}

		for (int i=0; i<A; i++) {
			dp[i] = 1;
			
			for (int j=0; j<i; j++) {
				
				if (sequence[j] < sequence[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max = Math.max(max, dp[i]);
		}

		System.out.println(max);
		
		while (max>=1) { 
			for (int j=A-1; j>=0; j--) { 
				if (dp[j] == max) {
					temp.add(sequence[j]); 
					max--; 
				} 
			} 
		}	 
		
		for (int i=temp.size()-1; i>=0; i--) {
			System.out.print(temp.get(i) + " "); 
		}
	}
}

3. 위 코드가 올바른 풀이다. 포인트는 끝에서부터 탐색하는 것.

다른 풀이들을 보니 Stack을 쓰는 것이 일반적인 해결법인듯 하다. 아무래도 LinkedList 와 Stack의 성능차이 때문인듯하다. 이 부분에 대해선 추가적으로 공부를 해보자

 

정리 : 

이번 문제로 꽤나 얻은 부분이 많은듯하다. 문제 해결이 안될 땐 역으로 생각하는 습관을 길들여보자.