[065] 14002. 가장 긴 증가하는 부분 수열 4

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

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

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 증가하는 부분 수열을 구하고, 가장 긴 값을 가져온다

- 가장 긴 값과 함께 수열에 들어있는 값도 출력한다.

 

 

 

🧶 풀이과정 

 

이 문제는 이전의 문제를 참고하고 있기 때문에 이전 문제를 참고하여 풀 수 있다.

2024.04.25 - [Algorithm] - [064] 11053. 가장 긴 증가하는 부분 수열

[064] 11053. 가장 긴 증가하는 부분 수열

 

저기에서 보면, 처음 재귀를 생각할 때 boolean을 사용하는 것을 고려했던 기록이 남아있다.

그것을 조금 더 깊게 활용하면 이번 문제는 쉽게 풀이가 가능하다.

 

우선, 기존의 코드를 그대로 두고 현재 값을 어떻게 담을지를 생각하면 되는데 여기에서 제일 효율적인 것은 Map을 쓰는 것이다.

Map은 key값의 중복이 없을 때 사용을 하기 때문에 현재와 같이 중복 값이 등장하지 않을 경우 유용하게 사용할 수 있다.

또한 Map의 Value값은 List로 담아왔는데, 고정 길이를 사용하는 array의 형식보다 가변 길이가 가능한 list가 이번 문제처럼 길이가 정해져있지 않은 값들을 담을 때에 더욱 편리하기 때문이다.

 

- Array와 List를 사용할 때 고정적 길이를 계속 사용해야 하고, 특정 인덱스의 지속적 수정이 이뤄질 경우는 Array, 가변 길이를 사용하고 특정 인덱스의 수정이 많이 일어나지 않을 때 List를 사용하는 게 좋다.

 

활용하는 방식은 다음과 같다

1) 현재 dp[i] 가 dp[j]+1이 될 경우 list를 dp[j]의 list로 변경한다.

2) 하위 반복문이 종료되는 시점에 list에 nums[i]의 값을 삽입한다.

3) map의 key값을 i로, value를 list로 하여 map에 삽입한다.

4) 반복문 종료 후, 가장 큰 값을 찾을 때 해당 값과 함께 인덱스도 함께 끌고 온다.(i)

5) 맵에서 인덱스를 키로 하는 value를 가져온다.

 

저번에 풀이를 하면서 이전에 풀었던 과정 중 생각한 방식을 차용하게 된 게 이번 풀이 시간을 단축한 것에 큰 몫을 했다 XD...!!

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q14002 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        int[] bp = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();

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

        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            nums[i] = num;
        }

        for(int i = 0; i < n ; i++){
            bp[i] = 1;
            ArrayList<Integer> list = new ArrayList<>();

            for(int j = 0 ; j < i ; j++){
                if(nums[i] > nums[j] && bp[i] < bp[j]+1){

                    // 기존 리스트 초기화하고
                    list.clear();

                    // 현재 리스트에는 j의 값을 넣고
                    list.addAll(map.get(j));

                    // bp[i]의 값은 bp[j] +1
                    bp[i] = bp[j] + 1;

                }
            }

            // 마지막으로 현재 i까지 list에 넣은 다음에 map에 넣기
            list.add(nums[i]);
            map.put(i, list);
        }


        int max = 0;
        int num = 0;
        for(int i = 0; i < n ; i++){
            if(max < bp[i]){
                max = bp[i];
                num = i;
            }
        }

        List<Integer> last = map.get(num);


        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        System.out.println(max);
        for(int i = 0; i < last.size() ; i++){
            bw.write(last.get(i) + " ");
        }

        bw.flush();
        bw.close();

        br.close();
    }
}

 

 

+ 여담으로 코파일럿이 칭찬해줌