문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
- 시간복잡도: O(nlogn), 약 2천만
- 주어진 N의 크기가 100만이다. 따라서 최대 사용할수있는 복잡도는 O(nlogn)이다.
- 기본적으로 DP, 다른 알고리즘으로는 시간복잡도 상 이 문제를 풀수가 없다.
- 생각한 방식은 key값에 부분 수열에 길이를 저장하고 value에 해당 부분수열 길이를 가지는 최소한의 값을 나타내는 방법을 택했다.
- TreeMap을 이용하여 한개의 수에 O(logn)의 시간만 사용하게 했고 따라서 시간복잡도는 O(nlogn)이다. 더 쉽게 이해를 돋기위해
아래 그림을 토대로 설명하겠다. 새로운 값이 들어오면 해당 값은 본인 보다 큰 최솟값을 찾아야한다. 만일 20, 15, 10의 숫자 순이라면
10은 15의 부분수열 값을 조회하고 이를 치환할 수 있다.
이와 같은 방식을 구현하는 방법은 바이너리 서치를 활용한 이진탐색과 트리맵을 이용한 이진탐색이 있다. 본인은 후자를 통해서 구현했다.
예제 입력 예시
6
10 20 10 30 20 50
예제 출력 예시
4
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int max = 0;
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int cur = Integer.parseInt(st.nextToken());
Integer higherKey = treeMap.higherKey(cur);
if (treeMap.get(cur)!=null)
continue; // 1. treeMap에 현재 값 있으면 패스
if (higherKey == null) { // 2. 현재값보다 큰 값 없으면 바로 추가
treeMap.put(cur, ++max);
} else {
int value = treeMap.remove(higherKey);
treeMap.put(cur, value);
}
}
System.out.println(max);
}
}
문제 출처
https://www.acmicpc.net/problem/12015
'알고리즘 > 자바' 카테고리의 다른 글
[백준 알고리즘] 12100번 자바(Java) 2048(Easy) (0) | 2024.08.22 |
---|---|
[SWEA] 6109번 자바(Java) 추억의 2048게임 (0) | 2024.08.22 |
[백준 알고리즘] 9252번 자바(Java) LCS2 (0) | 2024.07.29 |
[백준 알고리즘] 2636번 자바(Java) 치즈 (2) | 2024.07.24 |
[백준 알고리즘] 1854번 자바(Java) K번째 최단경로 찾기 (0) | 2024.07.18 |