[소프티어] 징검다리(JAVA)

27200 2025. 3. 13. 20:55

문제

풀이(12분)

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

public class Main {
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine()); // 돌의 개수

        st = new StringTokenizer(br.readLine());

        int firstHeight = Integer.parseInt(st.nextToken()); // 0번째 돌의 높이
        list.add(firstHeight); // 0번째 돌의 높이 리스트에 추가

        for(int i = 1; i < n; i++){ // 1번째 돌부터
            int height = Integer.parseInt(st.nextToken());
            if(height > list.get(list.size() - 1)){ // 만약 돌의 높이가 현재까지 중 최고라면
                list.add(height); // 리스트에 그냥 추가
                continue;
            }
            int idx = binarySearch(height); // 돌의 높이를 대체할 인덱스 찾기
            list.set(idx, height); // 리스트에 값 변경
        }

        System.out.println(list.size()); // 리스트 사이즈가 밟을 수 있는 돌의 최대 갯수
    }

    public static int binarySearch(int num){
        // 1 2 4 가 있는데 3이 들어옴
        int start = 0; // 0
        int end = list.size()-1; // 2
        int mid = (start + end) / 2; // 1
        while(start <= end){
            mid = (start + end) / 2;
            if(list.get(mid) == num){ // 처음에 mid == 1이기 때문에 3이 아님 (list.get(mid) == 2)
                return mid;
            }
            if(list.get(mid) < num){ // 처음에 mid == 1이기 때문에 3보다 작음 (list.get(mid) == 2)
                start = mid + 1; // start = 1 + 1이므로 2이가 됨.
                continue;
            }
            end = mid - 1; // start = 2가 되었을 때 mid = 2가 되고, list.get(mid) == 4이므로 여기로 내려옴.
            // end = 2 - 1이 되어 반복문 끝남.
        }
        return start; // 2가 반환됨
    }
}

문제 풀이 전략

LIS라는 것을 깨닫는 순간 코드를 바로 구현했다. 만약, LIS를 모른다면 https://to-travel-coding.tistory.com/303 글을 참고하자.

규칙은 다음과 같다.

1. 첫번째 수열의 값을 리스트에 추가한다.

2. 다음 입력값이 리스트의 끝(코드를 보다 보면 알겠지만 리스트는 자연스럽게 오름차순 정렬이 된다.) 보다 크다면 리스트에 추가한다.

3. 입력값이 리스트의 끝보다 작다면 어떠한 인덱스의 값을 바꿔줄 것인지 이분탐색을 통해 찾는다.

4. 이분탐색을 통해 찾은 인덱스의 값을 대체한다.

예를 들어,

라는 수열이 있다고 하자.

1. List<Integer>의 시작은 [1] 일 것이다. (List <Integer>의 상태 : [1])

2. 2가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List <Integer>의 상태 : [1, 2])

3. 4가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List <Integer>의 상태 : [1, 2, 4])

4. 3이 들어온다. 3번 규칙에 의해 이분탐색을 통해 인덱스 2를 대체해야 함을 알게 된다. 인덱스 2에 있는 4를 값 3으로 바꿔준다.

(List의 상태 : [1, 2, 3])

-> 이분탐색이 이해가 안 된다면 코드의 주석을 참고하자.

5. 5가 들어온다. 2번 규칙에 의해 리스트에 곧바로 추가된다. (List<Integer>의 상태 : [1, 2, 3, 5])