[JAVA] 백준_2828 사과 담기 게임

https://www.acmicpc.net/problem/2828

📌 문제 탐색하기

N칸으로 구성된 스크린이 있고 바구니는 M칸을 차지하고 처음에는 스크린의 가장 왼쪽에 위치한다. 사과가 한번에 하나씩 J번 떨어진다면 모든 사과를 바구니에 담기위한 바구니를 움직인 거리의 최솟값을 구하는 문제이다. 
이때 조건은 사과는 바닥에 도달할때 바구니가 해당 칸을 덮고 있어야 하고 바구니는 스크린의 범위를 벗어나면 안된다.

📌 가능한 시간복잡도

사과의 최대 개수는 20개, 사과마다 위치 비교하고 이동 거리를 계산하는데 필요한 시간 복잡도는 O(N)이다.
따라서 가능한 시간복잡도는 O(N) 입니다.

📌 코드 설계하기

바구니의 지금 현재 범위를 유지하면서 떨어지는 사과가 바구니 안에 있으면 이동하지 않는다. 
바구니 범위 바깥이면 바구니를 사과 위치에 맞게 옮기고 이동한 거리를 누적시키며 바구니가 움직인 거리의 최솟값을 구하면 됩니다.

📌 정답 코드

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

public class Main {

    public static int solution(int N, int M, int[] apples) {
        int move = 0;
        int left = 1;    
        int right = M;    
        for (int apple : apples) {
            if (apple < left) {
                move += left - apple;
                right -= (left - apple);
                left = apple;
            } else if (apple > right) {
                move += apple - right;
                left += (apple - right);
                right = apple;
            }
        }

        return move;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());


        int J = Integer.parseInt(br.readLine());
        int[] apples = new int[J];


        for (int i = 0; i < J; i++) {
            apples[i] = Integer.parseInt(br.readLine());
        }
        int result = solution(N, M, apples);
        System.out.println(result);
    }
}