👨💻 문제
세준이는 도서관에서 일한다.
도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다.
세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다.
각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오.
세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다.
책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.
그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.
⌨️ 입력
첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다.
둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다.
책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.
🖨️ 출력
첫째 줄에 정답을 출력한다.
📖 예제
입력
7 2 -37 2 -6 -39 -29 11 -28출력
131
✍️ 풀이
⌨️ 데이터 입력
static int BookCnt, CarryCnt, MaxDistance;
static PriorityQueue<Integer> BookLeft, BookRight;
public static void input() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BookCnt = Integer.parseInt(st.nextToken());
CarryCnt = Integer.parseInt(st.nextToken());
BookLeft = new PriorityQueue<>(Collections.reverseOrder());
BookRight = new PriorityQueue<>(Collections.reverseOrder());
st = new StringTokenizer(br.readLine());
for(int i=0; i<BookCnt; i++){
int book = Integer.parseInt(st.nextToken());
int book_abs = Math.abs(book);
( (book>0) ? BookRight : BookLeft ).add( book_abs );
MaxDistance = Math.max(MaxDistance, book_abs );
}
}📌 음수와 양수 분할
세준이가 한 번에 들 수 있는 책의 개수를 운반량,
책의 원래 위치를 목적지라고 칭하겠다.
🧑 : 세준
🚩 : 목적지
⬜ : 빈 공간
Case :
🚩⬜⬜🚩🚩🧑⬜🚩⬜⬜🚩
📚 책의 수: 5권
🚩 목적지: -5, -2, -1, 2, 5
💪 운반량: 2권
☠️ 비효율적 이동
🚩⬜⬜🚩🚩🧑⬜🚩⬜⬜🚩
🚩⬜⬜🚩🧑⬜⬜🚩⬜⬜🚩 1👣
🚩⬜⬜🚩⬜⬜⬜🧑⬜⬜🚩 4👣
🚩⬜⬜🚩⬜🧑⬜⬜⬜⬜🚩 6👣
만일 세준이 -1과 2를 방문하고 0으로 돌아온다면,
총 6 걸음을 소모한다.
⭐️ 효율적 이동
🚩⬜⬜🚩🚩🧑⬜🚩⬜⬜🚩
🚩⬜⬜🚩🧑⬜⬜🚩⬜⬜🚩 1👣
🚩⬜⬜🧑⬜⬜⬜🚩⬜⬜🚩 2👣
🚩⬜⬜⬜⬜🧑⬜🚩⬜⬜🚩 4👣
만일 세준이 -1과 -2를 방문하고 0으로 돌아온다면,
총 4 걸음을 소모한다.
이는 같은 방향의 목적지를 지난다면 거리가 가장 먼 목적지만 고려하면 된다는 것을 의미한다.
사실 애초에 다른 방향의 목적지를 한 번에 방문하는 것 자체가 잘못되었다.
이 행위는 반드시 0을 지나치기 때문이다.
그렇기 때문에 음수와 양수값을 따로 저장할 것이다.
BookLeft = new PriorityQueue<>(Collections.reverseOrder());
BookRight = new PriorityQueue<>(Collections.reverseOrder());
st = new StringTokenizer(br.readLine());
for(int i=0; i<BookCnt; i++){
int book = Integer.parseInt(st.nextToken());
int book_abs = Math.abs(book);
( (book>0) ? BookRight : BookLeft ).add( book_abs );
MaxDistance = Math.max(MaxDistance, book_abs );
}방향이 많았다면 배열을 사용하였겠지만,
방향은 단 2개 뿐이므로 BookLeft, BookRight 라는 2개의 우선순위 큐를 선언하였다.
BookRight는 양수의 목적지를 저장한다.
BookLeft는 음수의 목적지를 저장한다.
모든 값은 절댓값으로 저장한다.
추후 BookRight에 적용할 메소드를 BookLeft에도 적용시키기 위함이다.
MaxDistance는 가장 먼 목적지를 저장한다.
이 변수는 마지막에 설명하겠다.
📌 우선순위 큐 (정렬)
BookLeft = new PriorityQueue<>(Collections.reverseOrder());
BookRight = new PriorityQueue<>(Collections.reverseOrder());Case :
🧑🚩🚩🚩🚩🚩
📚 책의 수: 5권
🚩 목적지: 1, 2, 3, 4, 5
💪 운반량: 2권
☠️ 비효율적 이동
🧑🚩🚩🚩🚩🚩
⬜⬜🚩🧑🚩🚩 3👣
🧑⬜🚩⬜🚩🚩 6👣
⬜⬜⬜⬜🧑🚩 10👣
🧑⬜⬜⬜⬜🚩 14👣
만일 세준이 1과 3를 방문하고 0으로 돌아온 후,
2과 4를 방문하고 0으로 돌아온다면,
총 14 걸음을 소모한다.
⭐️ 효율적 이동
🧑🚩🚩🚩🚩🚩
⬜⬜🧑🚩🚩🚩 2👣
🧑⬜⬜🚩🚩🚩 4👣
⬜⬜⬜⬜🧑🚩 8👣
🧑⬜⬜⬜⬜🚩 12👣
만일 세준이 1과 2를 방문하고 0으로 돌아온 후,
3과 4를 방문하고 0으로 돌아온다면,
총 12 걸음을 소모한다.
이는 같은 방향의 목적지라도 무작위의 순서가 아닌 정렬된 순서로 방문하는 것이 효율적임을 의미한다.
그러므로 목적지들의 값들이 정렬되어야 한다.
📌 내림차순 정렬
Collections.reverseOrder()Case :
🧑🚩🚩⬜⬜🚩
📚 책의 수: 3권
🚩 목적지: 1, 2, 5
💪 운반량: 2권
책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다는 조건은 일단 생략하겠다.
☠️ 비효율적 이동
🧑🚩🚩⬜⬜🚩
⬜⬜🧑⬜⬜🚩 2👣
🧑⬜⬜⬜⬜🚩 4👣
⬜⬜⬜⬜⬜🧑 9👣
🧑⬜⬜⬜⬜⬜ 14👣
만일 세준이 1과 2를 방문하고 0으로 돌아온 후,
남은 목적지인 5를 방문하고 0으로 돌아온다면,
총 14 걸음을 소모하게 된다.
⭐️ 효율적 이동
🧑🚩🚩⬜⬜🚩
⬜🚩⬜⬜⬜🧑 5👣
🧑🚩⬜⬜⬜⬜ 10👣
⬜🧑⬜⬜⬜⬜ 11👣
🧑⬜⬜⬜⬜⬜ 12👣
만일 세준이 2과 5를 방문하고 0으로 돌아온 후,
남은 목적지인 1을 방문하고 0으로 돌아온다면,
총 12 걸음을 소모하게 된다.
이는 책의 수가 한 번에 들 수 있는 책의 개수에 나누어 떨어지지 않을 때, 절댓값이 큰 목적지들끼리 우선적으로 함께 방문해야 하는 것을 의미한다.
이와 같은 이유로 내림차순으로 정렬한다.
👣 최소 걸음 구하기
public static int getMinWalk(PriorityQueue<Integer> Book){
int result = 0;
while(!Book.isEmpty()){
int dist = Book.poll();
for(int carry=1; carry<CarryCnt && !Book.isEmpty(); carry++){
Book.poll();
}
result += dist * 2;
}
return result;
}📌 알고리즘 동작
그림은 이해를 돕기 위한 매체일 뿐, 실제로 구현되어 작동하는 배열은 아니다.
🧑🚩🚩⬜⬜🚩⬜⬜🚩🚩
📚 책의 수: 5권
🚩 목적지: 1, 2, 5, 8, 9
💪 운반량: 3권
1
int dist = Book.poll();우선순위 큐의 첫 값 (0에서 가장 먼 목적지) 을 dist 변수에 저장한다.
🧑🚩🚩⬜⬜🚩⬜⬜🚩🚩
⬜🚩🚩⬜⬜🚩⬜⬜🚩🧑 dist = 9
2
for(int carry=1; carry<CarryCnt && !Book.isEmpty(); carry++){
Book.poll();
}남은 운반량만큼 우선순위 큐에서 목적지를 제거한다.
⬜🚩🚩⬜⬜🚩⬜⬜🚩🧑 남은 운반량 : 2
⬜🚩🚩⬜⬜🚩⬜⬜🧑⬜ 남은 운반량 : 1
⬜🚩🚩⬜⬜🧑⬜⬜⬜⬜ 남은 운반량 : 0
3
result += dist * 2;가장 먼 목적지에 도달한 후 0으로 돌아오므로 반환값(result)에 dist의 2배를 더한다.
⬜🚩🚩⬜⬜🧑⬜⬜⬜⬜ dist = 9
🧑🚩🚩⬜⬜⬜⬜⬜⬜⬜ 18👣
4
while(!Book.isEmpty()){
int dist = Book.poll();
for(int carry=1; carry<CarryCnt && !Book.isEmpty(); carry++){
Book.poll();
}
result += dist * 2;
}
return result;남은 목적지가 없을 때까지 이를 반복한 후 result를 반환한다.
🧑🚩🚩⬜⬜⬜⬜⬜⬜⬜ 18👣
⬜🚩🧑⬜⬜⬜⬜⬜⬜⬜ dist = 2, 남은 운반량: 2
⬜🧑⬜⬜⬜⬜⬜⬜⬜⬜ dist = 2, 남은 운반량: 1
🧑⬜⬜⬜⬜⬜⬜⬜⬜⬜ 22👣
22를 반환한다.
🤔 결과값 구하기
public static void main(String[] args) throws IOException{
input();
int result = getMinWalk(BookLeft) + getMinWalk(BookRight) - MaxDistance;
System.out.println(result);
}책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다는 조건이 존재한다.
getMinWalk()는 항상 0으로 돌아오는 알고리즘이다.
알고리즘은 가장 먼저 방문하지만
가장 먼 목적지를 마지막에 방문하였고 0으로 돌아오지 않았다고 생각하면 된다.
우리는 이전에 절댓값이 가장 먼 목적지를 MaxDistance라는 변수에 저장하였다.
음수 영역의 결과값과 양수 영역의 결과값을 더한 후, MaxDistance를 뺀다면 우리가 원하는 결과값이 나오게 된다.
📄 전체 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int BookCnt, CarryCnt, MaxDistance;
static PriorityQueue<Integer> BookLeft, BookRight;
public static void main(String[] args) throws IOException{
input();
int result = getMinWalk(BookLeft) + getMinWalk(BookRight) - MaxDistance;
System.out.println(result);
}
public static void input() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BookCnt = Integer.parseInt(st.nextToken());
CarryCnt = Integer.parseInt(st.nextToken());
BookLeft = new PriorityQueue<>(Collections.reverseOrder());
BookRight = new PriorityQueue<>(Collections.reverseOrder());
st = new StringTokenizer(br.readLine());
for(int i=0; i<BookCnt; i++){
int book = Integer.parseInt(st.nextToken());
int book_abs = Math.abs(book);
( (book>0) ? BookRight : BookLeft ).add( book_abs );
MaxDistance = Math.max(MaxDistance, book_abs );
}
}
public static int getMinWalk(PriorityQueue<Integer> Book){
int result = 0;
while(!Book.isEmpty()){
int dist = Book.poll();
for(int carry=1; carry<CarryCnt && !Book.isEmpty(); carry++){
Book.poll();
}
result += dist * 2;
}
return result;
}
}