[자바] 백준 15323 - ZigZag (java)

목차

문제 : boj15323

 

 

필요 알고리즘

• 우선순위 큐
  
  • 정렬을 통해서도 짤 수 있다. 내 경우에 가장 간단히 짤 수 있는게 우선순위 큐라 생각해서 사용했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  문제에서 제시된 조건을 정리해보면 다음과 같다.

1. K개의 문자열을 입력받는다.

2. N개의 문자를 입력받으며 각각에 대해, 입력받은 문자로 시작하는 현재까지 가장 말한 횟수가 적은 문자를 얘기한다.

3. 만약 가장 말한 횟수가 적은 문자가 여러개라면 사전순으로 앞서는 단어를 얘기한다.

 

  그렇다면 필요한건 각 단어별로 말한 횟수와, 맨 앞 문자가 동일한 문자들끼리의 사전순 순서이다.

내 경우엔 'a'부터 'z'에 해당하는 배열을 만들고, 각 배열에 우선순위 큐(이하 pq)를 두었다. 그리고 정렬 방식은 문제에서 제시된대로 말한 횟수가 빠른 순서, 동일하다면 문자열 자체의 사전순이다.

 

  그럼 매번 해당 문자에 해당하는 pq에서 하나를 뽑아내서 출력하면 답이 된다. 뽑아낸 문자는 횟수만 늘려서 다시 pq에 집어넣는다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        PriorityQueue<Letter>[] arr = new PriorityQueue['z'-'a'+1];
        for (int i = 0; i < arr.length; i++) arr[i] = new PriorityQueue<>();

        while (k-->0) {
            String s = br.readLine();
            arr[s.charAt(0) - 'a'].add(new Letter(s));
        }

        StringBuilder answer = new StringBuilder();
        while (n-->0) {
            int idx = br.readLine().charAt(0) - 'a';
            Letter cur = arr[idx].poll();
            answer.append(cur.s).append('\n');
            arr[idx].add(new Letter(cur));
        }
        System.out.print(answer);
    }
}

class Letter implements Comparable<Letter> {
    final String s;
    final int cnt;

    public Letter(String s) {
        this.s = s;
        this.cnt = 0;
    }

    public Letter(Letter letter) {
        this.s = letter.s;
        this.cnt = letter.cnt+1;
    }

    @Override
    public int compareTo(final Letter o) {
        if (this.cnt == o.cnt)
            return this.s.compareTo(o.s);
        return this.cnt - o.cnt;
    }
}