[코테/Java] 백준 12014번 문제 99% 틀림 디버깅

간단한건데 이걸 왜 몰랐을까 기록용

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for (int testcase = 1; testcase <= T; testcase++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            
            int[] stock = new int[N+1];
            
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                stock[i] = Integer.parseInt(st.nextToken());
            }
            
            System.out.println("Case #" + testcase);
            
            //LIS            
            int[] lis = new int[N+1];
            int len = 0;
            
            for (int i : stock) {
                int left = 0;
                int right = len;
                
                while(left < right) {
                    int mid = (left + right) / 2;
                    if(lis[mid] < i) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                lis[left] = i;
                if(left == len) {
                    len++;
                }
            }
            
            System.out.println(len >= K ? 1 : 0);
            
        }
    }
}

LIS를 사용하는 문제임을 알았고, 단순하게 LIS의 길이만 구하면 된다는 것도 빨리 알아차렸는데 위 코드로 99%에서 자꾸 틀렸다..

좀 더 차분하게 이유를 분석해보니 생각보다 간단했다

//LIS            
int[] lis = new int[N + 1];
int len = 0;

for (int i: stock) {
    int left = 0;
    int right = len;

    while (left < right) {
        int mid = (left + right) / 2;
        if (lis[mid] < i) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    lis[left] = i;
    if (left == len) {
        len++;
    }
}

LIS 길이만 구하는 코드에서,
int[] stock = new int[N+1];을 통해서 초기화 해주면 stock[0]~stock[N]까지 0으로 초기화 하고 지정하기 때문에 stock[0]은 0인 상태이다.
이후 for (int i: stock) 라는 for문을 통해 0~N까지 모든 인덱스를 점검하게 되는데, 여기서 문제가 발생하는 것이다.

예제 하나를 들자면,
입력 :
1
5 2
5 4 3 2 1

출력 :
0

인 예제가 있다고 해보자
stock[1]부터 끝까지 정상적으로 봤다면 전체 길이는 1로 답은 0이 맞다

그러나,
stock[0] = 0인 상태에서, stock[0]부터 쭉 훑어보기 시작하면 전체 수열을 0, 5, 4, 3, 2, 1인 상태로 인식하게 된다.

즉 LIS 상태는

• 0 추가 / lis = [0]
• 5 추가 / lis = [0, 5]
• 4로 수정 / lis = [0, 4]
• 3로 수정 / lis = [0, 3]
• 2로 수정 / lis = [0, 2]
• 1로 수정 / lis = [0, 1]
  즉 결과인 길이는 2가 되어 답이 1이고, 여기서 틀리게 되는 것이다..

해결책으로는 stock을 탐사하는 범위만 제한하면 되기 때문에,

for (int idx = 1; idx <= N; idx++) {
	int i = stock[idx];

으로만 for문을 바꿔주면 된다^^