[SWEA 7701] 염라대왕의 이름 정렬 (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG

SW Expert Academy

1. 주의할 점

- Comparable을 무조건 사용해야 한다(사용하지 않으면 N*N만큼 뒤져봐야한다)

- Set이나 Map을 통해서 logN으로 줄이도록 해야한다.

 

2. 구현

- 첫 번째 방법: HashMap + Priority_Queue 사용

  HashMap<String,Integer> 에 입력받은 문자열, 문자열의 크기를 저장했다. 또한, 중복을 방지하기 위해 사용했다.

  Priority_Queue는 Comparable을 implement하고 문자열 길이의 오름차순으로 정렬하도록, 또한 길이가 같다면 사전순으로 정렬하도록 설정했다.

 

- 두 번째 방법: TreeSet + Comparable 사용

  TreeSet에는 문자열을 입력받고 정렬하는 방법은 위와 똑같은 방법을 사용했다. 

  TreeSet 또한 중복을 방지하기 위해 사용했다. 

 

[HashMap + Priority_Queue 사용]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;

public class Solution_d4_7701_염라대왕의이름정렬 {
	static class Info implements Comparable<Info>{
		String str;
		int len;
		public Info(String str, int len) {
			this.str = str;
			this.len=len;
		}
		@Override
		public int compareTo(Info o) {
			if(this.len==o.len)
				return this.str.compareTo(o.str);
			return Integer.compare(this.len, o.len);
		}
	}
	static PriorityQueue<Info> pq;
	static HashMap<String, Integer> map;
	public static void main(String[] args) throws Exception{
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int test= Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			pq = new PriorityQueue<>();
			map = new HashMap<>();
			int num = Integer.parseInt(br.readLine().trim());
			for(int i=0;i<num;i++) {
				String s = br.readLine().trim();
				map.put(s, s.length());				
			}			
			Iterator<String> mapIter = map.keySet().iterator();	 
	        while(mapIter.hasNext()){
	            String key = mapIter.next();
	            int len = map.get(key);
	            pq.add(new Info(key,len));
	        }			
			Info ii;
			System.out.println("#"+t);
			while(!pq.isEmpty()) {
				ii=pq.poll();
				System.out.print(ii.str+'\n');
			}
		}
	}
}

 

[TreeSet + Comparable 사용]

import java.io.*;
import java.util.*;

public class Solution_d4_7701_염라대왕의이름정렬Treeset {
	
	static class Info implements Comparable<Info>{
		String str;
		public Info(String str) {
			this.str = str;
		}
		@Override
		public int compareTo(Info o) {
			if(this.str.length()==o.str.length())
				return this.str.compareTo(o.str);
			return Integer.compare(this.str.length(), o.str.length());
		}
	}
	static Set<Info> set;
	public static void main(String[] args) throws Exception{
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int test= Integer.parseInt(br.readLine());
		for(int t=1;t<=test;t++) {
			set  = new TreeSet<>();
			int num = Integer.parseInt(br.readLine().trim());
			for(int i=0;i<num;i++) {
				String s = br.readLine().trim();
				set.add(new Info(s));				
			}			
			Iterator<Info> it = set.iterator();	 
			bw.write("#"+t+'\n');
	        while(it.hasNext()){
	        	bw.write(it.next().str+'\n');
	        }			
		}
		bw.flush();
        bw.close();
	}
}