백준 27522 카트라이더: 드리프트 Java

: ) YOUNG·2023년 3월 5일
1

알고리즘

목록 보기
188/411
post-thumbnail

백준 27522번
https://www.acmicpc.net/problem/27522

문제




생각하기


  • 문자열, 정렬 문제이다.
    • 도착 시간을 파싱해서 시간순으로 정렬하면 된다.
    • 1도 어렵지 않음 (정렬 개념 만들기 딱 좋은 문제인 것 같음)

동작


    private static PriorityQueue<Time> pque = new PriorityQueue<>();

    private static class Time implements Comparable<Time> {
        int M;
        int SS;
        int sss;
        String team;

        public Time(int m, int SS, int sss, String team) {
            M = m;
            this.SS = SS;
            this.sss = sss;
            this.team = team;
        }

        @Override
        public String toString() {
            return "Time{" +
                    "M=" + M +
                    ", SS=" + SS +
                    ", sss=" + sss +
                    ", team='" + team + '\'' +
                    '}';
        }

        @Override
        public int compareTo(Time o) {
            if (M == o.M) {
                if (SS == o.SS) {
                    return sss - o.sss;
                }
                return SS - o.SS;
            }

            return M - o.M;
        }
    } // End of Time class

정렬을 하기위해서 PriorityQueue를 사용했다. (이하 Pque)

Pque는 Comparable 구현체를 만들어야 한다 여기서

compareTo를 문제에서 원하는 대로 구현하기만 하면 된다.

시간 순으로 정렬하는 문제이니까 가장 우선순위는 M이 낮은 순으로 정렬해야 할 거고,
M이 같을 경우 SS를 기준으로 정렬한다. SS도 같을 경우 sss순으로 정렬하면 된다.



        int size = pque.size();
        for (int i = 0; i < size; i++) {
            Time temp = pque.poll();

            if(temp.team.equals("R")) {
                redScore += scoreArr[i];
            } else {
                blueScore += scoreArr[i];
            }
        }

pque에 값을 넣고 다시 꺼내면서, 순서에 맞게 점수를 측정하고, 어떤 팀이 승리했는지 출력하면 된다.

참고로 PriorityQueue는 그냥 반복문으로 출력했을 때는 정렬이 되지 않은 상태로 나오게되므로, 정렬이 된 상태로 보여주기 위해서는 poll()을 해서 값을 모두 꺼내야만 정렬이 되어서 나온다는 점을 잊어서는 안된다.

Priority Queue는 값을 넣을 떄 내부에서 정렬된 것이 아님.. Tree형태로 값이 들어가는데, 단지 부모 > 자식의 성질만 유지가 되므로, 정확히 내가 설정한대로 정렬된 것은 아니다. 즉, 자식 끼리는 정렬되어 있지 않다.
정확히는 heap의 자료구조를 이해하는 것이 중요하다




코드


Java


import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int redScore = 0;
    private static int blueScore = 0;

    private static int[] scoreArr = {10, 8, 6, 5, 4, 3, 2, 1, 0};
    private static PriorityQueue<Time> pque = new PriorityQueue<>();

    private static class Time implements Comparable<Time> {
        int M;
        int SS;
        int sss;
        String team;

        public Time(int m, int SS, int sss, String team) {
            M = m;
            this.SS = SS;
            this.sss = sss;
            this.team = team;
        }

        @Override
        public String toString() {
            return "Time{" +
                    "M=" + M +
                    ", SS=" + SS +
                    ", sss=" + sss +
                    ", team='" + team + '\'' +
                    '}';
        }

        @Override
        public int compareTo(Time o) {
            if (M == o.M) {
                if (SS == o.SS) {
                    return sss - o.sss;
                }
                return SS - o.SS;
            }

            return M - o.M;
        }
    } // End of Time class

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        for (int i = 0; i < 8; i++) {
            st = new StringTokenizer(br.readLine(), ":");

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

            String temp = st.nextToken();
            int sss = Integer.parseInt(temp.substring(0, 3));
            String team = temp.substring(temp.length() - 1);

            pque.offer(new Time(m, ss, sss, team));
        }

        int size = pque.size();
        for (int i = 0; i < size; i++) {
            Time temp = pque.poll();

            if(temp.team.equals("R")) {
                redScore += scoreArr[i];
            } else {
                blueScore += scoreArr[i];
            }
        }

        if (redScore > blueScore) {
            sb.append("Red");
        } else {
            sb.append("Blue");
        }

        bw.write(sb.toString());
        bw.close();
    } // End of main
} // End of Main class

0개의 댓글