[백준알고리즘-JAVA]1181번 풀이(단어정렬) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1181번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1181(단어 정렬)

문제

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

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

입력

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

출력

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

입력 예시

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

출력 예시

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	
	   	 	String[] arr = new String[num];
	   	 	
	   	 	for(int i =  0 ; i < num ; i++) {
	   	 		arr[i] = br.readLine();
	   	 	}
	   	 	
	   	 	Arrays.sort(arr, new Comparator<String>() {
	   	 		@Override
	   	 		public int compare(String s1, String s2) {
	   	 		if(s1.length() == s2.length()) {
	   	 			return s1.compareTo(s2);
	   	 		}else {
	   	 			return s1.length() - s2.length();
	   	 		}
	   	 		
	   	 	}
	   	 	});
	   
	   	 	System.out.println(arr[0]);
	   	 	for(int i = 1; i < num; i++) {
	   		if (!arr[i].equals(arr[i - 1])) {
				System.out.println(arr[i]);
			}
		}
	}
}
		

 

단어 정렬 알고리즘에서는 Arrays.sort를 재정의 하는 방법에 대해서 알아야 쉽게 해결할 수 있습니다. Array.sort를 손수 손 코딩을 통해서 구현해도 상관없지만, 언제나 저희가 코딩을 하면서 일일이 손 코딩하는 것보다는 기존에 있는 라이브러리를 활용한다면 더욱 효율적이게 프로그램을 제작할 수 있죠

 

이에 따라서 Arrays.sort를 재정의하는 방법에 대해서 알려드리겠습니다.

---

알고리즘 흐름도

입력받기 -> 순서대로 정렬하기 -> 중복 제거하기 -> 출력

---

STEP1 정렬하기

Arrays.sort는 기본적으로 인자를 2가지를 받습니다.

 

Array.sort(arr, new Comparator <>)

 

보편 적으로 저희가 배열을 정렬할 때는 Array.sort(arr) 이런 식으로 인자를 1개만 줄 경우 Comparator은 default값으로 적용되어 실행이 되는 것입니다. (정수 정렬할 때는 default값으로 진행해도 무리가 없죠)

 

그러나 문자열을 정렬하기 위해서는 따로 재정의가 필요합니다.

 

 1.1 Arrays.sort()의 Comparator 재정의하기

Arrays.sort(arr, new Comparator<String>() {
	   	 		
	   	 	});

이런 식으로 인자를 넣어줄 때 바로 Comparator객체를 생성하여 넣어줍니다.

 

 1.2 Comparator에 있는 메서드인 compare 오버 라이딩하기

(오버 라이딩이란, 이미 기존에 있는 Comparator에서 인터페이스로 정의되어있는 함수를 재정의하는 기술이다.)

Arrays.sort(arr, new Comparator<String>() {
	   	 		@Override
	   	 		public int compare(String s1, String s2) {
	   	 		
	   	 		
	   	 	}
	   	 	});

이런 식으로 compare을 정의하게 되죠. 여기서 String s1과 s2는 무엇을 의미하냐면 앞서 우리가 인자로 주었던 arr의 배열이 0 1 // 1 2 // 2 3 이런 식의 인덱스가 들어가게 되죠

 

 1.3 문자열의 길이 정렬하기

Arrays.sort(arr, new Comparator<String>() {
	   	 		@Override
	   	 		public int compare(String s1, String s2) {
	   	 			return s1.length() - s2.length();
	   	 	}
	   	 	});

자, 이제 반환 값을 주어야 하는데 해당 메서드의 반환 값은 양수, 음수로 판단하여 정렬을 하기 때문에 해당 방식처럼 하면 됩니다.

 

해당 반환 값이 양수면 s1이 큰 값이 됩니다.

 

 1.4 문자열 길이가 같다면 사전 순으로 정렬하기

Arrays.sort(arr, new Comparator<String>() {
	   	 		@Override
	   	 		public int compare(String s1, String s2) {
	   	 		if(s1.length() == s2.length()) {
	   	 			return s1.compareTo(s2);
	   	 		}else {
	   	 			return s1.length() - s2.length();
	   	 		}
	   	 		
	   	 	}
	   	 	});

간단합니다. 조건문으로 길이가 같음을 판별해주고 compareTo를 통해서 해당 문자열을 쉽게 정렬할 수 있습니다. compareTo는 Comparator 내부에 있는 메서드로 해당 객체가 이용할 수 있는 메서드입니다. 이 메서드는 String문자열을 사전 순으로 정렬해주는 기능을 하죠. 물론 위와 같은 형식으로 양수, 음수로 판별하여 사전 순으로 처리하기 때문에 큰 문제가 없습니다.

---

STEP2 중복 제거

System.out.println(arr[0]);
	   	 	for(int i = 1; i < num; i++) {
	   		if (!arr[i].equals(arr[i - 1])) {
				System.out.println(arr[i]);
			}
		}

뭐 중복제거는 별게 없습니다. 가장 앞에 있는 문자열은 그냥 출력을 해준 뒤

 

인덱스 1부터 그 이전 거와 문자열을 비교하여 같지 않다면, 출력해주면 끝~

---

해당 문제에서 가장 중요한 요점은 Arrays.sort에서 인자로 사용되는 Comparator 객체입니다. 해당 객체에 대한 내요은 한번 요약하여 블로그 글에 개제하겠습니다 ~