[백준 알고리즘 -11722] 가장 긴 감소하는 부분 수열 - java (Collections.reverse(), Java 8 Stream API)

int[] 뒤집기 (Collections) feat. 백준 11722

---

문제풀다보면 Arrays나 Collections의 도움을 참 많이 받게 되는데,

간단한 sort는 따로 정리할 것도 없지만, 요론건 또 정리해줘야 기억날듯하다.

int형 배열을 뒤집으려면 간단하게는 새로운 배열을 생성해서 하나하나 for문 돌릴 수 있겠지만,

사람이 또 뭔가 그런 방법말고 다른 방법 없나 찾고싶고 그런 마음이 있다ㅎㅎㅎㅎㅎ

JAVA 8에서 Stream API로 Object[]로 바꿔서 반환해주는게 있긴 하던데, Object[]를 또 int[]로 바꾸기 한참 걸려서 패스 하고,

Collections를 사용하기로 했다.

물론 List를 int[]로 바꾸는데 활용하긴 했음

사실 Arrays에서 reverse메소드를 제공해주면 참 쉬워질텐데 아쉽다 핳

 Integer[] arr = new Integer[N];//바꿔야할 배열
/* 여긴 패스
 StringTokenizer stringTokenizer=new StringTokenizer(br.readLine());
 int ai=0;
 while(stringTokenizer.hasMoreTokens()){
     arr[ai++]=Integer.parseInt(stringTokenizer.nextToken());
 }
 */
 List<Integer> tempArr=Arrays.asList(arr);//Collections를 사용하기위해 List로 변환
 Collections.reverse(tempArr);//reverse!
 arr=tempArr.stream().toArray(Integer[]::new);//Collections -> Integer[]로 변환하는 Java 8 Stream API

하는김에 백준 11722풀이

---

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

문제는 이러하고, 뒤에서부터 돌아서 증가 수열을 구해도 되고

비교 조건을 감소 조건으로 해도 되지만, 이 전에 증가 부분 수열 구하는 문제를 풀었고 그 코드를 그대로 사용하고자했다.

수열의 앞 뒤 순서만 유지하면 되기 때문에 뒤집어도 전혀 지장없이 문제를 풀이할 수 있다.

따라서, 배열을 뒤집고 증가 부분 수열 코드를 그대로 갖다 쓰면 문제 해결 가능하다.

​
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
​
public class Main {
​
    public static void main(String[] args) throws IOException {
​
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
​
        Integer[] arr = new Integer[N];
​
        StringTokenizer stringTokenizer=new StringTokenizer(br.readLine());
        int ai=0;
        while(stringTokenizer.hasMoreTokens()){
            arr[ai++]=Integer.parseInt(stringTokenizer.nextToken());
        }
        List<Integer> tempArr=Arrays.asList(arr);
        Collections.reverse(tempArr);
​
        arr=tempArr.stream().toArray(Integer[]::new);
​
        int[] d=new int[N];
        d[0]=1;
​
        int max=1;
​
        for(int i=1; i<N; i++){
            d[i]=1;
            int amax=1;
            for(int j=i-1; j>=0; j--){
                if(arr[j]<arr[i] && amax < d[j]+1 ){
                    d[i]=d[j]+1;
                    amax=d[j]+1;
                    if(max < d[i])
                        max=d[i];
                }
            }
​
        }
​
        System.out.println(max);
​
​
    }
}
​