[백준] 23889: 돌 굴러가유 - JAVA

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

 

풀이

마을들이 일자로 배치되어있고 돌은 벽을 만날때까지 왼쪽에서 오른쪽으로 굴러간다.

 

마을에는 모래성이 있어서 돌이 굴러가면 모래성이 다 부서진다.

 

벽을 세워 돌을 막을 수 있는데 모래성이 가장 적게 부서지게 세워야 한다.

 

돌의 위치와 몇개의 모래성을 부수는지 이차원배열에 담았다.

 

먼저 돌이 굴러가기 시작하는 위치를 배열에 넣고, 돌의 위치를 기준으로 다음 돌까지 모래성의 개수를 합하여 배열에 넣었다.

 

부수는 모래성의 개수를 기준으로 내림차순 정렬하고,

 

가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가장 빠른 답을 출력해야 하므로 모래성의 개수가 같을 경우 돌의 위치를 기준으로 오름차순 정렬하였다.

 

벽의 개수 k만큼 모래성의 개수가 많은 순으로 벽을 세워주면 된다.

---

 

메모리: 39748KB
시간: 644ms
언어: Java 11

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] castle = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; i++) {
            castle[i] = Integer.parseInt(st.nextToken());
        }

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

        for (int i = 0; i < k; i++) {
            int start = stone[i][0];
            int end = n + 1;
            if (i < k - 1) {
                end = stone[i + 1][0];
            }

            for (int j = start; j < end; j++) {
                stone[i][1] += castle[j];
            }
        }

        Arrays.sort(stone, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }
                return o2[1] - o1[1];
            }
        });

        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < m; i++) {
            set.add(stone[i][0]);
        }

        StringBuilder sb = new StringBuilder();
        for (int wall : set) {
            sb.append(wall).append("\n");
        }

        System.out.println(sb);
    }
}