[JAVA] 1181번 - 단어 정렬

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

정렬문제이다.

1. 길이가 짧은 순서로 정렬

2. 길이가 같다면 사전 순으로 정렬

 

시간복잡도

정렬의 시간복잡도는 O(NlogN)이고 단어의 개수는 20,000이다

O(NlogN) 은 약 86,000번의 연산이 필요하다

 

알고리즘

해시맵을 사용했다. 이유는 문제에서 "단, 중복된 단어는 하나만 남기고 제거해야한다."

라고 되어있어서 해시맵을 떠올렸다.

해시맵은 중복을 허용하지 않기 때문에 해시맵을 선택했다.

그리고 또 하나의 이유는 길이를 기준으로 정렬을 하기 때문에 length를 각각 가지고 있어야한다.

그래서 String타입과 int타입으로 해시맵을 통해 정렬하는 방식으로 접근을 시도했다.

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. n을 입력받는다

2. n개의 단어를 입력받고, 바로 length를 측정해서 바로 해시맵에 넣는다

3. 해시맵은 바로 정렬을 할 수 가 없어서 리스트로 변환후 리스트를 정렬해야한다.

=>그래서 해시맵의 ketSet을 이용하여 String을 리스트로 변환해서 단어 정렬을 수행한다.

4. 단어의 길이가 같을 경우 정렬하고, 길이가 같을 경우 사전순으로 정렬하는 람다함수를 작성해서 정렬을 수행한다.

5. 출력한다

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

첫번째 시도

=> 길이가 같을 경우 사전순으로 오름차순하는 경우를 고려하지 못했다! 오로지 길이만 고려했음

그리고 또 하나 알게된 사실은 Collections.sort(setlist) 이렇게 하면 길이는 고려하지 않고 사전순으로 출력된다

ㅇ왜냐하면 자연 정렬 순서가 사전 순이기 때문이다!!!

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());
		
		Map<String, Integer> map = new HashMap<>();
		
		for(int i=0; i<n; i++) {
			String[] input = br.readLine().split("\n");
			String key = input[0];
			int len = key.length();
			map.put(key, len);
		}
		
		List<String> setlist = new ArrayList<>(map.keySet());
		
		Collections.sort(setlist, (n1, n2) -> (map.get(n1).compareTo(map.get(n2))));
		
		for(String key : setlist) {
			System.out.println(key);
		}
		
	}
}

 

 

정답 코드

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());
		
		Map<String, Integer> map = new HashMap<>();
		
		for(int i=0; i<n; i++) {
			String[] input = br.readLine().split("\n");
			String key = input[0];
			int len = key.length();
			map.put(key, len);
		}
		
		List<String> setlist = new ArrayList<>(map.keySet());
		
		Collections.sort(setlist, (n1, n2) ->  {
			int m1 = map.get(n1);
			int m2 = map.get(n2);
			return (m1 == m2) ? n1.compareTo(n2) : m1 - m2;	
		});
		
		for(String key : setlist) {
			System.out.println(key);
		}
		
	}
}

 

 

정리

 Collections.sort(setlist)

자연정렬이기때문에 오로지 "사전순"으로만 정렬된다. 길이는 고려하지 못함

Collections.sort(setlist, (n1, n2) -> (map.get(n1).compareTo(map.get(n2))));

"길이만" 고려한다. 

 

=> 그렇다면 길이를 고려하되, 길이가 같을시 사전순으로 출력하려면

길이가 같으면 사전순으로 출력

길이가 다르면 길이순으로 출력

이렇게 접근할 수 있다.

Collections.sort(setlist, (n1, n2) ->  {
			int m1 = map.get(n1);
			int m2 = map.get(n2);
			return (m1 == m2) ? n1.compareTo(n2) : m1 - m2;	
		});

이렇게 삼항연산자를 이용했다.

** compareTo메서드는 string을 사전순으로 비교하게 되어 있다