[Baekjoon] 15323_ZigZag

문제(출처: https://www.acmicpc.net/problem/15323)

---

< ZigZag >

 

문제 풀이 

 

각 알파벳에 해당하는 우선수위 큐를 만들어 구분하여 저장한다. 각 알파벳으로 시작하는 단어들 중에서 알파벳 순서와 선택 횟수를 판별하여 선택한다. 

 

+ 각 단어의 시작하는 알파벳에 구분하여 따로 저장하지 않고 한 번에 저장할 경우 시간초과가 발생한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _15323_ { // ZigZag
	static class Word implements Comparable<Word> {
		private String w;
		private int count;

		public Word(String w, int count) {
			this.w = w;
			this.count = count;
		}

		@Override
		public int compareTo(Word o) {
			if (this.count == o.count) {
				return this.w.compareTo(o.w);
			}
			return this.count - o.count;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

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

		HashMap<Character, PriorityQueue<Word>> map = new HashMap<>();
		for (int i = 0; i < 26; i++) {
			map.put((char) ('a' + i), new PriorityQueue<>());
		}

		for (int i = 0; i < k; i++) {
			String str = bf.readLine();
			map.get(str.charAt(0)).add(new Word(str, 0));
		}

		for (int i = 0; i < n; i++) {

			char x = bf.readLine().charAt(0);

			Word word = map.get(x).poll();
			bw.write(word.w + "\n");
			word.count += 1;
			map.get(x).add(word);
		}
		bw.flush();
	}
}

변수)
k, n : 단어, 문자 개수
map : HashMap <Character, PriorityQueue <Word>>
x : 문자

 

Word

단어와 선택 횟수를 변수로 가지며 선택 횟수가 작을수록, 선택 횟수가 같다면 알파벳순으로 우선순위를 가진다.

 

Main

단어와 문자 개수를 입력받는다. 각 알파벳에 따라 구분하여 저장하기 위해 HashMap에 알파벳을 key 값으로, PriorityQueue를 value로 저장하여 초기화한다. 단어 수만큼 단어를 입력받아 시작하는 알파벳이 해당하는 곳에 저장한다. 문자 개수만큼 문자를 입력받아 map에서 key값으로 문자를 가지는 우선순위 큐를 찾아 첫 번째 값을 출력한다. 그 후 선택 횟수를 증가시켜 다시 우선순위 큐에 저장한다.

---

---