백준 1181번
https://www.acmicpc.net/problem/1181
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
문제 이해는 그냥 단어 정렬을 하라는 거니까 비교적 간단했고,
어떻게 풀어야 하나 고민을 조금 하다가 HashMap
을 사용하면 가장 쉽겠다는 생각을 했다.
Key
를 단어로 생각하고 Value
를 단어의 길이로 지정해준다.
HashMap
의 정렬은 EntrySet
을 사용해서 정렬하는 걸로 결정했다.
먼저 HashMap
의 단어 삽입은 같은 단어가 있을 경우를 생각해서
getOrDefault()
메소드를 사용했다.
Key
값은 어차피 중복이 되지 않기 때문에 getOrDefault()
를 사용하면 문제가 쉽게 해결된다.
정렬과정에서 자리이동이 계속해서 일어나기때문에 정렬에서 일어나는
삽입과 추출의 효율성을 생각해서
LinkedList
로 EntrySet()
를 만들었다.
먼저 단어의 알파벳 기준으로 정렬을 해야되니까 Key
를 기준으로 정렬해주고
그 다음 단어의 길이 값인 Value
를 정렬한다.
만약 Key
를 먼저 정렬하지 않고 출력하게 됬을 경우,
Testcase 에 있는 길이2 의 단어 중no, it, im
단어가
im, it, no
순으로 나와야 정답이지만 알파벳 정렬은 되지 않은 채 첫번째 단어 순 그대로 나오면서 오답이 되게 된다.
정렬에 대한 지식이 1 올랐다..
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); HashMap<String, Integer> hashmap = new HashMap<>(); List<String> list = new ArrayList<>(); int loop = Integer.parseInt(br.readLine()); for(int i=0; i<loop; i++) { String temp = br.readLine(); int length = temp.length(); hashmap.put(temp, hashmap.getOrDefault(temp, length)); } List<Map.Entry<String, Integer>> entryList = new LinkedList<>(hashmap.entrySet()); //iterator.hasNext()는 다음 값이 있는지 없는지 확인하는 메소드 entryList.sort(Map.Entry.comparingByKey()); entryList.sort(Map.Entry.comparingByValue()); for(Map.Entry<String, Integer> entry : entryList) { System.out.println(entry.getKey()); } } }