[백준] 1965. 상자 넣기 (자바 JAVA)
문제
정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.
상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.
입력
파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.
예제 입력 1
8
1 6 2 5 7 3 5 6
예제 출력 1
5
예제 입력 2
10
1 2 3 4 5 6 7 8 9 10
예제 출력 2
10
접근 방법 🧐
문제를 읽어보면 상자넣기가 곧 가장 긴 증가하는 부분수열 문제라는 것을 알 수 있는데,
2가지의 접근 방법이 있다.
1. 2중 for문 이용
1. dp : 각 위치에서 최대로 넣을 수 있는 상자개수를 의미한다.
2. dp를 계산하는데, 각 원소 boxes[i]에 대해 더 작은 값을 가지고 있으면 dp[i] = Math.max(dp[i], dp[j] + 1])로 최대값을 넣어준다.
이 방식은 시간복잡도가 O(N^2)이다.
2. 이분 탐색(Binary Search) 이용
2중 for문을 이용해서 비교하는 방식으로 풀 수도 있겠지만 여기서 이런 의문이 들 수 있을 것이다.
dp[i]를 계산하기 위해 boxes[0] ~ boxes[i - 1]를 꼭 다 훑어봐야 하는가?
첫 번째 알고리즘에서 boxes[0] ~ boxes[i - 1]를 훑어본 것은 boxes[i]보다 작은 boxes[j]를 가지는 j들 중 가장 큰 dp[j]를 찾기 위함이었다. 여기서 다음과 같은 생각을 이끌어낼 수 있다.
만약 dp[j] = k를 만족하는 j 중에서 boxes[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면,
나중에 dp[i] (i > j)를 계산할 때 그 값들만 참조하면 dp[i]의 값을 쉽게 알 수 있다.
내가 쓴 코드 ✍️
1. 2중 for문 이용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
int[] boxes = new int[n]; // 상자 크기 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
boxes[i] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[n]; // 각 위치에서 최대로 넣을 수 있는 상자 개수
int answer = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (boxes[i] > boxes[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
answer = Math.max(answer, dp[i]);
}
System.out.println(answer);
}
}이 코드를 제출하면 정답이지만, 상술한대로 시간복잡도가 O(N^2)이라서 만약에 N의 범위가 10000을 넘어선다면 시간 초과가 발생할 것이다.
그래서 효율성을 높이는 2번 알고리즘이 더 최적일 것이다.
2. 이분 탐색(Binary Search) 이용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
int[] boxes = new int[n]; // 상자 크기 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
boxes[i] = Integer.parseInt(st.nextToken());
}
int[] LIS = new int[n]; // LIS를 추적하기 위해 사용되는 배열. 이 배열에는 LIS를 구성할 가장 작은 수들이 단계별로 저장
int length = 0; // LIS의 길이
for (int i = 0; i < n; i++) {
int currentSize = boxes[i];
int left = 0;
int right = length;
while (left < right) {
int mid = (left + right) / 2;
if (LIS[mid] < currentSize) {
left = mid + 1;
} else {
right = mid;
}
}
LIS[left] = currentSize;
// 만약 새로운 숫자가 LIS의 마지막 위치에 추가되었다면 길이를 증가
if (left == length) {
length++;
}
}
System.out.println(length);
}
}