BAEKJOON / 백준 - JAVA 15966번 군계일학

2024.06.30기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 입력 받은 수열중 연속된 수열을 계산하는 문제입니다.

 

이 문제를 풀때 순서를 유지 해야 된다는걸 발견하지 못해 문제가 있었습니다.

 

1. 입력 받은 수열을 1부터 시작해 배열에 저장합니다.

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

 

2. 연속된 수열의 개수를 저장하는 dp배열을 생성합니다.

int[] dp = new int[1000001]; // 연속된 수열의 개수를 저장하는 배열

 

3. 생성된 배열에 들어온 수열의 순서대로 참조하는 인덱스의 바로 뒷 인덱스의 값의 +1를 하여 저장합니다.

for (int i = 1; i <= n; i++) {
    dp[arr[i]] = Math.max(dp[arr[i]], dp[arr[i] - 1] + 1); // 뒤에 연속된 수열의 개수보다 +1
    count = Math.max(count, dp[arr[i]]);
}

 

4. 그 중 가장 큰 값을 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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());
		}
		
		int[] dp = new int[1000001]; // 연속된 수열의 개수를 저장하는 배열
		int count = 0;
		
		for (int i = 1; i <= n; i++) {
			dp[arr[i]] = Math.max(dp[arr[i]], dp[arr[i] - 1] + 1); // 뒤에 연속된 수열의 개수보다 +1
			count = Math.max(count, dp[arr[i]]);
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}