[Java] 백준 1181번 [단어 정렬] 자바

: ) YOUNG·2021년 12월 29일
2

알고리즘

목록 보기
5/417
post-thumbnail

백준 1181번
https://www.acmicpc.net/problem/1181


문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.


출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.


생각하기

문제 이해는 그냥 단어 정렬을 하라는 거니까 비교적 간단했고,
어떻게 풀어야 하나 고민을 조금 하다가 HashMap을 사용하면 가장 쉽겠다는 생각을 했다.
Key를 단어로 생각하고 Value를 단어의 길이로 지정해준다.

HashMap의 정렬은 EntrySet을 사용해서 정렬하는 걸로 결정했다.

먼저 HashMap의 단어 삽입은 같은 단어가 있을 경우를 생각해서
getOrDefault() 메소드를 사용했다.
Key값은 어차피 중복이 되지 않기 때문에 getOrDefault()를 사용하면 문제가 쉽게 해결된다.

정렬과정에서 자리이동이 계속해서 일어나기때문에 정렬에서 일어나는
삽입과 추출의 효율성을 생각해서
LinkedListEntrySet()를 만들었다.

먼저 단어의 알파벳 기준으로 정렬을 해야되니까 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());
		}			
	}
}

0개의 댓글