99클럽 코테 스터디 11일차 TIL [Greedy]

- 오늘의 학습 키워드 : Greedy 알고리즘

[문제 이름 : 도서관 (백준 1461, G4)]
문제 url : https://www.acmicpc.net/problem/1461

내가 작성한 코드는 아래와 같다.

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Integer> plusList = new ArrayList<>();
        List<Integer> minusList = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(num > 0) {
                plusList.add(num);
            } else {
                minusList.add(-num);
            }
        }

        // 절댓값 기준 내림차순 정렬
        Collections.sort(plusList, Collections.reverseOrder()); // 11 2
        Collections.sort(minusList, Collections.reverseOrder()); // 39 37 29 28 6

        int totalDistance = 0;

        // 가장 먼 거리를 한 번만 왕복 처리
        if (!plusList.isEmpty() && (minusList.isEmpty() || plusList.get(0) >= minusList.get(0))) {
            // 양수 리스트가 비어있지 않고, (음수 리스트가 비어있거나 양수 리스트 값이 더 클 때)
            totalDistance += plusList.get(0);
            for (int i = 0; i < m && !plusList.isEmpty(); i++) {
                plusList.remove(0);
            }
        } else if (!minusList.isEmpty() ) {
            // 음수 리스트가 비어있지 않고, 음수 리스트 값이 더 클 때
            totalDistance += minusList.get(0);
            for (int i = 0; i < m && !minusList.isEmpty(); i++) {
                minusList.remove(0);
            }
        }

        // 나머지 양수 그룹 처리
        for (int i = 0; i < plusList.size(); i += m) {
            totalDistance += plusList.get(i) * 2; // 왕복 거리
        }

        // 나머지 음수 그룹 처리
        for (int i = 0; i < minusList.size(); i += m) {
            totalDistance += minusList.get(i) * 2; // 왕복 거리
        }

        System.out.println(totalDistance);
    }
}

풀이 과정 (풀이 시간 : 30분)

m=2이고, 양수와 음수를 옮기게 된다면 책이 있는 0을 지나가게 되므로, 양수와 음수를 각각의 List에 저장해서 왕복 거리를 계산해야 한다. 문제 접근 방식이 독특해서 어렵게 느껴졌다.

 

1. 양수 리스트를 저장하는 plusList, 음수 리스트를 저장하는 minusList를 생성하고, 저장한다.

2. 내림차순으로 정렬한 뒤, 양수 리스트 또는 음수 리스트의 제일 큰 값에 따라 if-else문으로 m의 값에 따라 거리를 이동했다고 가정하고, 제일 큰 값을 totalDistance에 더한다.
3. 양수 그룹에서 제일 큰 값에 m의 차이가 나는 만큼 책을 가져다 놓을 수 있으므로, +=m씩 하며 큰 값을 더해 나간다.

4. 음수 그룹도 마찬가지로 3번 과정을 진행한다.

내일은 하반기 자기소개서를 작성하고, 제출할 예정이다.