[softeer/java] 징검다리

 

문제

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

제약조건

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

입력형식

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

 

출력형식

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

 

입력예제

5

3 2 1 4 5

 

---

처음에는 단순히 앞 뒤로 비교 후 뒤 값이 크면 count++ 형식으로 하려했으나...

철수가 돌을 뛰어 넘을 수도 있기 때문에 해당 방법은 틀린 방법이다.

저 방법은 철수가 걷기만 가능할 때 유효함.

 

따라서 이분탐색으로 해결하기로 함

현재 원소와 뒤의 원소를 이분 탐색하여 최종 배열 길이를 출력해주면 된다.

현재 원소보다 큰 값일 찾기위해 이분 탐색을 사용하는거임

 

과정

 

• 3 → list = [3]
• 4 → list = [3, 4]
• 1 → list = [1, 4] (3이 1로 대체됨)
• 2 → list = [1, 2] (4가 2로 대체됨)
• 5 → list = [1, 2, 5] (5 추가됨)

 

 정답

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  //돌의 개수
        int[] arr = new int[n]; //돌의 높이 배열, 낮은곳에서 높은곳으로 뛰어 넘을 수도 있음. 그래서 단순 count++ 방법은 불가

        for (int i=0 ; i<n ; i++) {
            arr[i] = sc.nextInt();
        }

        //이분 탐색 배열
        int[] list = new int[n];
        int len = 0;  

        for (int i=0 ; i<n ; i++) {
            //현재 돌의 높이를 list 배열 내에 삽입할 위치를 이분 탐색으로 찾는다.
            int pos = Arrays.binarySearch(list, 0, len, arr[i]);
            
            if (pos < 0) { //음수라면?
                pos = -(pos + 1);
            }

            list[pos] = arr[i];  //해당 위치에 현재 값을 삽입

            //만약 list의 끝에 새 값을 추가한 경우라면 길이를 늘린다.
            if (pos == len) {
                len++;
            }
        }

        System.out.println(len); //배열 길이를 출력
    }
}