[BackJoon]11053번, 가장 긴 증가하는 부분수열

문제

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 

A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

 

동적계획법의 유명한 문제라고 알려진 가장 긴 증가하는 부분수열(LIS - Longest Increasing Subsequence) 문제이다.

 

예전에 한 번 풀었던 풀이를 보니 탑다운 방식으로 구성되어 있어서,

 

이번에는 나름대로 바텀업으로 구현하려고 했다.

 

다만 문제를 앞에 두고 고민을 좀 하다 보니 메모이제이션을 굳이 배열로 만들 필요가 없어 보여서,

 

언제나 좋아하는 스트림과 맵을 이용해서 풀이를 구성했다.

 

알고리즘은 다음과 같다.

 

1. 주어진 숫자는 그대로 배열로 담되, 0번 인덱스의 값을 0으로 설정한 뒤 1번부터 담았다.
2. 키-값이 둘 다 정수인 해시맵을 만들어서 (0, 0)을 초기값으로 담아주었다.
3. 배열의 1번 인덱스부터 N번 인덱스까지 반복문을 돌며
   
   
   1. 위에서 만들어둔 맵을 엔트리셋으로 변환한 뒤 스트림을 열고
   2. 키값이 현재 인덱스의 값보다 작은 요소 중에 밸류가 가장 큰 요소를 고른다.
   3. 이 과정에서 해당하는 요소가 없다면 (0, 0)을 만들어 새로 수열을 시작한다.
   4. 키값을 현재 인덱스의 값으로 하고, 밸류값을 찾아낸 값에서 +1 해준,
      즉 길이가 1 증가한 요소를 새로 만들어 맵에 넣어준다.
4. 와 같은 과정을 반복한 뒤에 맵에서 가장 긴 수열, 그러니까 가장 큰 밸류값을 출력해 주었다.

이 과정에서 Map.Entry 라거나 이를 구현한 SimpleEntry에 대해 배울 수 있었고,

 

그 내용은 아래 글에 정리해 두었다.

2023.03.29 - [Development/Java] - [Java]Map.Entry 인터페이스

[Java]Map.Entry 인터페이스

마지막으로 코드를 보면 아래와 같다.

package BackJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractMap;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Prob11053_2 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] arr = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Map<Integer, Integer> integerMap = new HashMap<>();

		integerMap.put(0, 0);

		for (int i = 1; i <= n; i++) {

			int finalI = i;

			Map.Entry<Integer, Integer> entry = integerMap.entrySet().stream()
				.filter(integerIntegerEntry -> integerIntegerEntry.getKey() < arr[finalI])
				.max(Map.Entry.comparingByValue())
				.orElse(new AbstractMap.SimpleEntry<>(0, 0));

			integerMap.put(arr[finalI], entry.getValue() + 1);
		}

		System.out.println(Collections.max(integerMap.values()));
	}
}

 

솔직이 이게 되나..? 싶었고 실제로 잘 안 돼서 몇 번 고쳤지만

 

통과가 되긴 되는 걸 보고 흥미를 느꼈다.

 

실제 메모이제이션을 사용한 바텀업 방식과 논리적으로는 차이가 없다는 게 내 의견.

 

동적 계획법은 아무리 해도 익숙해지진 않는다..

 

끝!