문제
풀이
첫 번째 풀이
바로 생각나는 대로 적어본 풀이는 다음과 같다.
1. if (리스트 길이<1) 라면 리스트에 단순 추가
2. 새로운 원소 x가 들어갈 위치 알아내기 by. 이진탐색
3. 만일 그 위치가 1이거나 리스트길이-1이라면
(맨 앞이나, 맨 뒤라면) 단순 추가
4. 만일 그 위치가 2이거나 리스트길이-2이라면
(맨 앞의 바로 뒤나, 맨 뒤의 바로 앞이라면)
4-1. Math.max(현재 맨 앞 원소, x)를 이용하여 맨 앞에 더 큰 수가 올 수 있게 함
4-2. Math.min(현재 맨 뒤 원소, x)를 이용하여 맨 뒤에 더 작은 수가 올 수 있게 함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
static LinkedList<Integer> list;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int arr[] = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
list = new LinkedList<>();
list.add(arr[0]);
for(int i=1; i<N; i++) {
int pos = binarySearch(0, list.size(), arr[i]);
if(pos == 0 || pos == list.size()) {
list.add(pos,arr[i]);
} else if(pos == 1) {
list.removeFirst();
list.addFirst(Math.max(list.get(0),arr[i]));
} else if(pos == list.size()-2) {
list.removeLast();
list.addLast(Math.min(list.get(list.size()-1),arr[i]));
}
}
System.out.println(list.size());
}
static int binarySearch(int left, int right, int key) {
int mid = (left+right)/2;
while(left < right) {
mid = (left+right)/2;
if(mid >= list.size()) return list.size();
if(list.get(mid) < key) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
애초에 LIS 문제집을 통해 풀게 된 문제였기 때문에 LIS를 안 써서 통과가 안 되지 않을까 .. 싶기는 했는데
역시나 ^^ 5%에서 실패가 떴다.
웬만한 테스트 케이스는 다 통과하는 것 같은데 로직의 어딘가에 문제가 있나보다. 근데 여전히 어디가 문젠지 모르겠음
두 번째 풀이
LIS와 LDS를 이용한 풀이를 활용했다.
이 블로그에서 설명해주신 예시를 통해 LIS와 LDS를 문제에 적용하는 이유와 방법을 파악하였다.
그런데 이를 바탕으로 코드를 짜서 제출해도 5%에서 자꾸 실패하는 이슈 .. 제출한 코드는 아래와 같음
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] arr = new int[N];
int[] inDp = new int[N];
int[] deDp = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int inMax = 1;
int deMax = 1;
for(int i=0; i<N; i++) {
inDp[i] = 1;
deDp[i] = 1;
for(int j=0; j<i; j++) {
if(arr[i] > arr[j]) {
// LIS
inDp[i] = Math.max(inDp[i], inDp[j]+1);
if(inDp[i] > inMax) inMax = inDp[i];
} else {
// LDS
deDp[i] = Math.max(deDp[i], deDp[j]+1);
if(deDp[i] > deMax) deMax = deDp[i];
}
}
}
System.out.println(N==0? 0: inMax+deMax-1);
}
}단순히 '아, LIS와 LDS를 구하고 두 길이를 더한 다음, 한 원소가 겹칠테니 1을 빼주면 되겠구나' 라고 생각하고 짠 코드다.
디버깅을 하니 코드와 로직 자체가 어딘가 잘못 되었다는 걸 알았는데, 정확히 어느 부분을 어떻게 고쳐야 할 지 갈피를 한참을 못 잡았다.
10
100 99 98 97 3 2 1 50 49 48내가 짠 코드에 위의 예제를 넣어보면, 다음과 같은 결과가 다온다.
답은 100 99 98 97 3 2 1 혹은 100 99 98 97 50 49 48으로 7이 나와야 하는데, 내가 짠 코드로는 LIS가 2, LDS는 7으로 2+7-1인 8이 나오게 된다.
이 예제를 보고 내가 하나의 숫자를 기준으로 LIS와 LDS를 구해야 함을 간과했다는 것을 알게 되었다.
즉, 첫 번째 원소인 100을 기준으로 했을 때 100을 포함하여 앞에 나오는 LIS와 100을 포함하여 뒤에 나오는 LDS를 구해야 했던 것 ㅎ
한 번 깨달으니 참말로 당연한 일인데 내 뇌는 아직 딱딱한가보다 하하
그런데 이걸 어떻게 또 코드로 녹여내야할 지는 막막했음 ..
세 번째 풀이
그러다 이 블로그의 풀이를 보고 적용해서 코드를 작성했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] arr = new int[N];
int[] inDp = new int[N];
int[] deDp = new int[N];
int ans = 0;
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for(int i=N-1; i>=0; i--) {
for(int j=i+1; j<N; j++) {
if(arr[j] > arr[i]) {
// LIS
inDp[i] = Math.max(inDp[i],inDp[j]);
} else {
deDp[i] = Math.max(deDp[i],deDp[j]);
}
}
inDp[i]++;
deDp[i]++;
ans = Math.max(ans, inDp[i]+deDp[i]-1);
}
System.out.println(ans);
}
}한 원소를 기준으로 이후에 나오는 원소들을 검토하여야 하므로 for문은 역방향으로 순회한다.
✔️ 주요 사항
- inDp[n]은 arr[n]에 해당하는 수부터 시작하는 LIS 길이를 나타낸다.
- deDp[n]은 arr[n]에 해당하는 수부터 시작하는 LDS 길이를 나타낸다.
즉, inDp[2]는 arr[2]에 해당하는 98을 처음으로 시작하여 만들어낼 수 있는 LIS 길이를 나타낸다. 98보다 더 큰 수가 이후에 존재하지 않으므로 그 값은 자신만을 포함한 1이 된다.
한편 deDp[2]는 98을 처음으로하여 만들어낼 수 있는 LDS의 길이를 나타낸다. 97 3 2 1 혹은 97 50 49 48 으로 LDS가 구성될 수 있으므로 그 값은 4가 된다.
위 코드로 아까 예제를 풀이해보면 아래와 같은 결과가 나온다.
답은 100을 기준으로 한 1+7-1으로 7이 도출된다.
휴 .. 쉽지 않네 ^^
그래도 이렇게 열심히 헤매는 문제 하나씩 만날 때마다 성장함을 느낀다
아자아자
