[Java] 그리디 알고리즘, 정렬 | 백준 1461 도서관

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

 

내 접근 방식

예제 입력 3개를 직접 손으로 풀어보았고 예제 출력에 대한 답을 올바르게 구할 수 있어 이를 코드로 구현하였다.

손 풀이 접근

1. 0의 위치에 책이 모아져 있으므로 0을 기준으로 음수 쪽에 놓아야 될 책들과 양수 쪽에 놓아야 될 책들로 분류됨.

2. 이를 위해 우선 주어진 책의 위치를 오름차순으로 정렬.

=> 이 부분에서 어떻게 책을 옮기는 방법에 대해 고민했는데,

그냥 M씩들어서 놓고 0으로 돌아가는 것을 반복하는 방법은 최소가 아님을 확인했다. 

 

더 효율적인 방법을 생각하다 0에 있는 책을 M개를 들어 바로 옆 위치로 모두 이동시키고, 해당 위치에 놓일 책을 제외하고 다시 M개씩 들어 모두 그 다음 위치로 이동시키는 방식을 생각했다. 

예제 1 

7 2
-37 2 -6 -39 -29 11 -28

예제 1의 경우 7개의 책을 옮겨야하고 최대 2개의 책을 들수 있으므로, 왼쪽 그림과 같이 옮겼을 때 최소 걸음 수로 책을 옮길 수 있었다.

 

이것을 공식화 시키기 위해 처음엔, 

-6 까지 오는데 5번 이동, -6에서 -28 사이를 3번 이동, -28에서 -29까지를 3번이동, -29에서 -37까지 1번, -37에서 -39까지 1번으로 나누어서 규칙을 찾아보았다.

최대로 들수 있는 책 M이 2여서 5번, 3번, 3번, 1번, 1번으로 2 단위씩 회수가 주는 패턴을 발견했는데 코드로 표현하려니 너무 수식이 많아지는 불편함을 느꼈다.

 

위의 그림의 화살표들을 이어지게 한번에 그려보았고, 아래와 같이 더 직관적이 패턴을 찾을 수 있었다.

-39까지 가는 화살표(0에서 가장 멀리 떨어져있는 지점)을 제외하고는 모두 2개의 화살표로 나타낼 수 있었다.

39를 더하고, 다음로 필요한 화살표는 -39 지점에서 2칸 더 이동한(M=2이므로) 지점 -29 에서 0까지의 길이 29를 두번,

-29 지점에서 두 칸 더 이동한 -6 지점에서 0까지 길이 6을 두번,

양수 쪽에서는 끝지점 11에서 2번을 모두 합하면 최소 걸음 131번을 구할 수 있다.

 

 

예제 2를 통해서 이 방법이 정답임을 다시 한번 확인할 수 있었다.

예제 2

8 3
-18 -9 -4 50 22 -26 40 -45

 

왼쪽 복잡한 그림의 단계를 다시 하나의 화살표로 길게 이어보면 아래와 같은 경로로 단수화 시킬 수 있다.

 

 

 

 

 

 

단순화시킨 경로에서 가장 0으로 부터 먼 거리였던 50을 한번 나머지 45를 2번, -45에서 3칸(M=3 이기 때문)간 -9지점에서 9를 2번 더해주면 최소 걸음 158을 구할 수 있다.

 

 

 

 

코드 작성

N, M, books 배열 초기화 후 books 배열 원소 오름차순 정렬

static int N; // 책 개수
static int M; // 한 번에 옮길 수 있는 최대 책 개수
static int[] books;

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    books = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
        books[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(books); // NlogN

    System.out.println(findMinimumSteps());
}

 

최소 걸음 수를 반환하는 findMinimumSteps() 메서드 구현

int totalSteps : 총 걸음 수

int lastNegativeIndex : 음수와 양수의 경계를 구분하기 위해 가장 마지막 음수 직후 인덱스(첫 양수 등장하는 지점)

int farthest : 0 기준 가장 멀리 떨어져 있는 거리 => 편도 처리(1번만 더할 거리)

=> 음수, 양수 둘다 존재할 경우 : 첫 원소의 절대값과 마지막 원소의 대소 비교

=> 양수만 있을 경우 : 가장 끝 원소, 음수만 있을 경우 : 가장 첫 원소의 절대값

 

음수 구간 내 : 첫 원소 부터 M 단위로 인덱스 점프하며 totalSteps에 거리 더하기

양수 구간 내 : 마지막 원소부터 -M 단위로 인덱스 점프하며 totalSteps에 거리 더하기

 

이렇게 구한 totalSteps에 2를 곱하여 한번에 왕복 처리 

마지막으로 가장 먼 거리였던 farthest에서는 다시 0으로 돌아가지 않으므로 왕복 처리했던 것에서 한번 빼주어 제외시킨다.

totalSteps -= farthest;

private static int findMinimumSteps() {
    int totalSteps = 0;

    int lastNegativeIndex = 0;
    while (lastNegativeIndex < N && books[lastNegativeIndex] < 0) {
        lastNegativeIndex++;
    }

    // 가장 먼 위치 확인
    int farthest = 0;
    if (lastNegativeIndex > 0 && lastNegativeIndex < N) {
        farthest = Math.max(Math.abs(books[0]), books[N - 1]);
    } else if (lastNegativeIndex == 0) { // 양수만 있을 때
        farthest = books[N - 1];
    } else { // 음수만 있을 때
        farthest = -books[0];
    }

    // 음수 (0 ~ lastNegativeIndex 미만)
    for (int i = 0; i < lastNegativeIndex; i += M) { //M개 단위로 옮기기
        totalSteps += Math.abs(books[i]);
    }

    // 양수 (lastNegativeIndex ~ 끝)
    for (int i = N - 1; i >= lastNegativeIndex; i -= M) {
        totalSteps += books[i];
    }

    totalSteps *= 2; //모든 경우 왕복 처리 위해 2배 처리
    totalSteps -= farthest; //가장 먼 거리 편도 처리

    return totalSteps;
}

 

 

이번 문제는 직접 그림을 그려보고 푼 코드로 작성하기에는 복잡했던 로직을 단순화하는 단계에서 시간이 걸렸다. 좀 더 다양한 문제를 경험하면서 고민하는 시간을 단축시켜봐야겠다.