[CodeTree Java] 함께가는 열차

문제 링크

https://www.codetree.ai/training-field/search/a-train-that-goes-together/description?page=1&pageSize=20&username= 

 

접근 방법

위치가 증가하는 순서로 주어졌기 때문에 배열의 뒤에서부터 탐색한다.

열차의 속도가 같거나 작은 경우는 따라잡지 못하고, 큰 경우에는 따라잡을 수 있다.

반복문을 돌면서 가장 끝 위치의 속도를 저장하고 이 속도보다 작거나 같은 경우 만날 수 없기 때문에 결과값 증가, 열차의 속도를 현재 배열 값으로 갱신한다.

 

코드

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));
        StringTokenizer tokens;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            Integer.parseInt(tokens.nextToken());
            int speed = Integer.parseInt(tokens.nextToken());

            arr[i] = speed;
        }

        int res = 1;
        int min = arr[N - 1];

        for (int i = N - 2; i >= 0; i--) {
            if(arr[i] <= min){
                res++;
                min = arr[i];
            }
        }

        System.out.println(res);

    }
}