BEAKJOON / 백준 - JAVA 29891번 체크포인트 달리기

2024.08.18기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 가장 적게 움직여 모든 체크포인트를 찍고 돌아왔을 때 걸리는 거리를 출력하는 문제입니다. 

 

1. 이 문제는 간단하게 가장 멀리 있는 순으로 k만큼 제거를 해주면 되는 문제입니다.

 

2. 우선 음수도 들어올 수 있기 때문에, 음수와 양수를 따로 저장하는 PriorityQueue를 생성합니다.

// 양수를 저장하는 큐
PriorityQueue<Integer> pos = new PriorityQueue<>(Collections.reverseOrder());

// 음수를 저장하는 큐
PriorityQueue<Integer> neg = new PriorityQueue<>();
int num;

while (n-- > 0) {
    num = Integer.parseInt(br.readLine());

    if (num > 0) { // 양수 라면
        pos.add(num);
    } else { // 음수라면
        neg.add(num);
    }
}

 

양수는 내림차순을 해야 가장 먼 거리부터 큐에서 나오기 때문에 reverseOrder()를 주고,

음수는 절대값 기준으로 먼 거리부터 나와야되기 때문에 오름차순으로 정렬을 해주었습니다.

 

3. 양수와 음수를 따로 따로 계산을 해주 었습니다.

long result = 0;
int together;

// 양수 체크포인트
while (!pos.isEmpty()) {
    result += pos.peek() * 2;
    together = k;

    // 현재 기준으로 제일 멀리 갔을 때 그 다음 먼 순으로 제거를 해준다.
    while (!pos.isEmpty() && together-- > 0) {
        pos.poll();
    }
}

// 음수 체크포인트
while (!neg.isEmpty()) {
    result += Math.abs(neg.peek()) * 2;
    together = k;

    // 현재 기준으로 제일 멀리 갔을 때 그 다음 먼 순으로 제거를 해준다.
    while (!neg.isEmpty() && together-- > 0) {
        neg.poll();
    }
}

 

체크포인트가 남은 기준으로 가장 먼거리를 갔을 때, 한 번에 들고 올 수 있는 k번 만큼을 큐에서 같이 제거를 해주며

갔다가 돌아와야 되기 때문에 거리는 *2를 해서 총 이동 거리에 더해줬습니다.

 

4. 계산된 거리 값을 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 체크포인트의 개수
		int k = Integer.parseInt(st.nextToken()); // 한 번에 체크가능한 포인트 개수
		
		// 양수를 저장하는 큐
		PriorityQueue<Integer> pos = new PriorityQueue<>(Collections.reverseOrder());
		
		// 음수를 저장하는 큐
		PriorityQueue<Integer> neg = new PriorityQueue<>();
		int num;
		
		while (n-- > 0) {
			num = Integer.parseInt(br.readLine());
			
			if (num > 0) { // 양수 라면
				pos.add(num);
			} else { // 음수라면
				neg.add(num);
			}
		}
		
		long result = 0;
		int together;
		
		// 양수 체크포인트
		while (!pos.isEmpty()) {
			result += pos.peek() * 2;
			together = k;
			
			// 현재 기준으로 제일 멀리 갔을 때 그 다음 먼 순으로 제거를 해준다.
			while (!pos.isEmpty() && together-- > 0) {
				pos.poll();
			}
		}
		
		// 음수 체크포인트
		while (!neg.isEmpty()) {
			result += Math.abs(neg.peek()) * 2;
			together = k;
			
			// 현재 기준으로 제일 멀리 갔을 때 그 다음 먼 순으로 제거를 해준다.
			while (!neg.isEmpty() && together-- > 0) {
				neg.poll();
			}
		}
		
		bw.write(Long.toString(result));
		bw.flush();
		bw.close();
		br.close();
	}
}