[백준알고리즘-JAVA]10814번 풀이(나이순 정렬) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

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

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

---

백준 10814 (나이순 정렬)

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

 

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

입력 예시

3
21 Junkyu
21 Dohyun
20 Sunyoung

출력 예시

20 Sunyoung
21 Junkyu
21 Dohyun

성공 코드

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][2];
	   	 	
	   	 	for(int i =  0 ; i < num ; i++) {
	   	 		String[] st = br.readLine().split(" ");
	   	 		arr[i][0] = st[0];
	   	 		arr[i][1] = st[1];
	   	 	}
	   	 	
	   	 	
	   	 	Arrays.sort(arr, new Comparator<String[]>() {
	   	 		@Override
	   	 		public int compare(String[] s1, String[] s2) {
	   	 		if(s1[0] == s2[0]) {
	   	 			return 1;
	   	 		}else {
	   	 			return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
	   	 		}
	   	 	}
	   	 	});
	   
	   	 	
	   	 	for(int i = 0; i < num; i++) {
				System.out.println(arr[i][0] +" "+ arr[i][1]);
	   	 		}
	}
}

나이순 정렬 알고리즘은 정렬에서 아주 많이 쓰이는 Comparator을 이용한 정렬을 사용하면 쉽게 해결할 수 있는 알고리즘입니다. Comparator이 무엇인지 모른다고요?

 

STEP을 따라가면서 쉽게 이해해 보세요 ~

---

알고리즘 흐름도

입력받기 -> 받은 입력 배열에 넣기 -> 넣은 배열 정렬하기 -> 출력하기

---

STEP1 입력 배열에 저장하기

입력받은 값은 반복문을 통해서 입력을 받아야 합니다. 여기서 주의할 점은 바로 2차원 배열을 이용해야 된다는 점입니다. 왜냐하면 입력값을 보면 나이 + 이름으로 입력을 받고 이 2가지를 통해서 정렬을 해야 하기 때문입니다.

 

String[][] arr = new String[num][2];
	   	 	
	   	 	for(int i =  0 ; i < num ; i++) {
	   	 		String[] st = br.readLine().split(" ");
	   	 		arr[i][0] = st[0];
	   	 		arr[i][1] = st[1];
	   	 	}

여기서 num은 맨 처음에 입력받은 숫자입니다~

---

STEP2 정렬하기

이 알고리즘의 핵심인 정렬하기!!

 

여기서 먼저 짚고 넘어가야 할 점은 바로 배열을 정렬하기 위해 JAVA에서 제공하는 라이브러리 중 하나인 Arrays.sort를 사용하는 겁니다.

 

일반적으로 우리가 알고 있는 배열 정렬은

Arrays.sort(arr);

이런 식으로 간편하게 사용했었죠. 그러나 해당 sort메서드는 기본적인 정수 배열만 정렬을 해주기에 저희는 따른 메서드를 사용하여 정렬을 해야 하죠

 

기본적인 Array.sort메서드는 2개의 인자를 받습니다. 저희가 일반적으로 쓰는 위 코드의 경우 인자를 1개만 전달하면 나머지 하나의 인자는 default 초기값으로 적용되어 정렬이 되죠

Arrays.sort(arr, Comparator<T>)

여기서 Comparator을 사용하면 됩니다. 해당 인자를 즉석으로 만들어서 적용해주면 됩니다.

 

Arrays.sort(arr, new Comparator<String[]>() {
	   	 		@Override
	   	 		public int compare(String[] s1, String[] s2) {
	   	 		if(s1[0] == s2[0]) {
	   	 			return 1;
	   	 		}else {
	   	 			return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
	   	 		}
	   	 	}
	   	 	});

해당 메서드를 하나하나 이해시켜드리겠습니다.

 

Comparator에서 <> 해당 기호는 제네릭이라고 합니다. 해당 기호를 모르신다면 스킵하셔도 됩니다. 2차원 배열이면 String [], 1차원 배열이면  String을 넣어주면 됩니다. 이후 compare메서드를 재정의 해줘야 합니다.

 

compare를 통해서 해당 알고리즘을 해결해봅시다.

여기서 s1은 첫 번째 행을 가리키게 되고 s2는 두 번째 행을 가리키게 됩니다.  그렇게 되면 s1 [0]은 arr [0][0]을 가리키게 되고 s2 [0]은 arr [1][0]을 가리키게 되죠

 

만약에 나이가 같다면 먼저 들어온 사람이 우선순위가 돼야 하므로 반환 값은 1

 

이게 무슨 의미인가?? 의문이 드실 수 있습니다. 이거는 compare의 특성으로 만약에 양수라면 앞에 있는 s1이 먼저 정렬되고 음수이면 s2가 먼저 정렬이 되는 형식이기 때문입니다.

 

compare 뿐만 아니라 Comparator자체의 정렬은 다 이와 같은 형식을 지니 죠

 

때문에 나이가 다를 경우에는 두 나이를 빼서 양수 음수를 가려 내림차순으로 정렬을 해주게 되죠

 

만약에 아직도 Comparator이 이해가 안 가신다면.... 제가 이와 관련된 내용을 블로그 글에 정리하여 올려드리겠습니다~

---

STEP 3 출력하기

출력하기는 뭐.. 그냥 단순 반복문을 돌리면 되니 코드를 참고하세요~

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