[Java] SWEA 3307 최장 증가 부분 수열

3307 최장 증가 부분 수열 문제 링크

#1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];
            int[] dp = new int[N];
             
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
             
            for(int i=0; i<N-1; i++) {
                for(int j=i+1; j<N; j++) {
                    if(arr[i] < arr[j]) {
                        dp[j] = Math.max(dp[i]+1, dp[j]);
                    }
                }
            }
             
            int answer = 0;
            for(int i=0; i<N; i++) {
                answer = Math.max(answer, dp[i]);
            }
             
            StringBuilder sb = new StringBuilder();
            sb.append("#").append(t).append(" ").append(answer+1);
            System.out.println(sb.toString());
        }
    }
}

• dp로 풀이함 : O(n^2)
• 완탐으로 하는 게 가장 기본적인? 풀이인 것 같은데
• 완탐은 사실 시간복잡도가 너무 커서 dp로 풀이함
• 근데 dp로 풀고 나니까 시간 복잡도가 완탐이랑 똑같음..

#2

package week01;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class SWEA_3307_binarySearch {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			// 최대 길이 수열의 길이?를 저장할 배열
			LinkedList<Integer> result = new LinkedList<>();
			// 서치 결과 인덱스
			int nowIndex;
			for(int i=0; i<N; i++) {
				// arr[i]가 result에 있는지 탐색 후 index값 반환
				nowIndex = Collections.binarySearch(result, arr[i]);
				
				// result에 arr[i]가 있는 경우
				if(nowIndex >= 0) {
					// result의 nowIndex 위치에 arr[i]를 넣음 -> 같은 수는 증가 수열로 체크 안 함 (무의미한 갱신)
					result.add(nowIndex, arr[i]);
				}
				else {
					// binarysearch는 검색한 배열에 해당 값이 존재하지 않는 경우
					// 해당 배열에 오름차순 정렬로 위치해야 할 -index-1 값을 반환
					
					// binarysearch로 들어온 index(-index-1)를 실제 index로 변환하는 과정
					int point = (nowIndex+1)*-1;
					// point가 result의 모든 요소 중 가장 큰 값임
					if(point == result.size()) {
						// result size가 1개 커짐
						result.add(arr[i]);
					} 
					// 가장 최근의 요소가 piont보다 큰 값임
					// 그래서 원래는 넣을 필요 없지만
					// point 위치를 해당 요소로 덮어씌워야 다음 배열들이 얼마나 이어지는지 체크 가능
					// 그니까 결과적으로, 최장 부분 배열을 구하는 건 불가능, 길이를 구하는 건 가능
					else {
						// set으로 해당 index 값을 덮어씌움
						result.set(point, arr[i]);
					}
				}
				
			}
			sb.append("#").append(t).append(" ").append(result.size()).append("\n");
		}
		System.out.println(sb);
	}
}

• binarysearch를 활용한 풀이 : O(nlogn)
• 이게 최장 증가 부분 수열의 길이 구하는 문제의 정석 풀이..? 라고 하더라
• 스터디원 분의 도움을 받아서 작성한 풀이..

#3

package week01;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class SWEA_3307_binarySearch {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			// 최대 길이 수열의 길이?를 저장할 배열
			LinkedList<Integer> result = new LinkedList<>();
			// 서치 결과 인덱스
			int nowIndex;
			for(int i=0; i<N; i++) {
				// arr[i]가 result에 있는지 탐색 후 index값 반환
				nowIndex = Collections.binarySearch(result, arr[i]);

				// binarysearch는 검색한 배열에 해당 값이 존재하지 않는 경우
				// 해당 배열에 오름차순 정렬로 위치해야 할 -index-1 값을 반환
				
				// binarysearch로 들어온 index(-index-1)를 실제 index로 변환하는 과정
				int point = (nowIndex+1)*-1;
				// point가 result의 모든 요소 중 가장 큰 값임
				if(point == result.size()) {
					// result size가 1개 커짐
					result.add(arr[i]);
				} 
				// 가장 최근의 요소가 piont보다 큰 값임- rmflrh 
				// 그래서 원래는 넣을 필요 없지만
				// point 위치를 해당 요소로 덮어씌워야 다음 배열들이 얼마나 이어지는지 체크 가능
				// 그니까 결과적으로, 최장 부분 배열을 구하는 건 불가능, 길이를 구하는 건 가능
				else {
					result.set(point, arr[i]);
				}
				
			}
			sb.append("#").append(t).append(" ").append(result.size()).append("\n");
		}
		System.out.println(sb);
	}
}

• 코드를 보니까..

// result에 arr[i]가 있는 경우
if(nowIndex >= 0) {
	// result의 nowIndex 위치에 arr[i]를 넣음 -> 같은 수는 증가 수열로 체크 안 함 (무의미한 갱신)
	result.add(nowIndex, arr[i]);
}

• 이 부분은 무의미한 갱신이라는 생각이 들어서
• 없어도 되지 않나.. 라는..
  
  
• 근데 어쨌든 갱신 파트를 삭제한 건데 메모리는 증가하고 속도는 변화가 없다는 사실...
• 속도는 그렇다 치는데 메모리는 대체 왜 늘어난 거지..?
  
  
• 아하.. linkedList를 사용했기 때문에 삽입 파트에서 효율이 좋아서 add문 조금 뺀 걸로는 속도의 큰 차이가 없다는군요..
• 메모리는 반대로 linkeList가 이미 비효율적이여서 유의미한 차이가 없다네요..