7701. 염라대왕의 이름 정렬

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG 

SW Expert Academy

 

분류

정렬

힙

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

이름을 최소 힙에 넣은 뒤 하나씩 빼며 출력하면 된다.

다만 중복된 이름은 map 구조를 이용해 체크한 뒤 힙에 넣지 않았다.

 

그런데, 지금 생각해보니 굳이 그렇게 하지 않고

모든 이름을 힙에 넣은 다음 하나씩 빼며 출력할때

이전에 출력한 이름과 지금 출력하려는 이름이 같은 경우 출력하지 않고 pop만 시켜주면

해결이 가능했을 것 같다.

 

시행착오

없음

 

코드

import java.util.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

class Solution{
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("s_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			int N = Integer.parseInt(br.readLine());
			Map<String, Boolean> m = new HashMap<String, Boolean>();
			Queue<Name> pq = new PriorityQueue<Name>();

			while (N-- > 0){
				String a = br.readLine();
				
				if (!m.containsKey(a)){
					pq.add(new Name(a));
					m.put(a, true);
				}
			}

			if (tc > 1) System.out.println();
			System.out.print("#" + tc);
	
			while (!pq.isEmpty()){
				System.out.print("\n" + pq.poll().name);
			}
		}
	}

	static class Name implements Comparable<Name>{
		String name;

		public Name(String name){
			this.name = name;
		}

		public int compareTo(Name n){
			int lenA = this.name.length(), lenB = n.name.length();
			if (lenB < lenA) return 1;
			if (lenA < lenB) return -1;
	
			if (n.name.compareTo(this.name) < 0) return 1;
			return -1;
		}
	}
}