[백준] 10814번 : 나이순 정렬 - JAVA [자바]

www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

---

• 문제

 

 

 

 

 

 

 

※ 주의할 점

1. 나이순 정렬을 기준으로 하되, 나이가 같을경우 주어진 입력순으로 정렬한다.

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 문제의 경우 정말 다양한 방법이 있다.

1. 먼저 가장 간단한 방법은 String[][] 2차원 배열을 통해 각 배열에 나이와 이름을 저장한 뒤, 나이 순으로 정렬하는 방법이다. 이때 정렬방법은 Arrays.sort()에 Comparator 의 compare 메소드를 구현하여 사용자 정렬을 사용해서 쓸 수 있다.

compare 메소드는 앞선 포스팅을 보셨다면 알겠지만, 양의 정수, 0, 음의 정수 중 하나를 반환하며, 양의 정수일 경우만 두 객체의 위치를 바꿔주는 역할을 한다. 이에 대한 참고 글은 아래 더보기에 있는 링크를 클릭하여 보길 바란다.

st-lab.tistory.com/110#알고리즘

[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]

 

st-lab.tistory.com/112#알고리즘

[백준] 1181번 : 단어 정렬 - JAVA [자바]

 

 

즉, 나이순으로 정렬하면서 이름은 따로 비교를 안한다면 나이순으로 정렬하되, 나이가 같을 경우는 0이 반환되어 자연스레 입력순으로 정렬된다.

 

 

 

 

2. 또한 다른 방법으로는 배열을 이용하지 않고 클래스 객체를 만들어 배열처럼 사용하는 방법이 있다. 예로들자면 다음과 같다.

public static void main(String[] args) {
	Person[] p = new Paerson[size];
}

public static class Person {
	int age;
	String name;
    
	public Person(int age, String name) {
		this.age = age;
		this.name = name;
	}
}

 

이런식으로 Person 클래스를 만들어서 나이와 이름을 변수로 받는 생성자를 만들고, 이 Person 클래스를 하나의 타입(=객체 타입)으로 하여 배열을 생성해준뒤, 해당 객체의 나이끼리 비교하여 정렬해주는 방식이다. 이 방식 또한 정렬 방법은 Arrays.sort() 를 확장하여 정렬할 수 있다. (물론 Person 클래스에 Comparable 을 통해 정렬을 할 수도 있다.)

 

 

 

 

 

3.  우리가 자주 사용하는 StringBuilder 을 배열처럼 사용하여 Counting sort 형태로 사용할 수 있다.

나이는 1 이상, 200 이하이므로 201 개의 StringBuilder 배열을 만들면 된다. 즉, 위의 2번처럼 StringBuilder 객체를 하나의 타입으로 받아 사용할 수 있다. 또한 2번에 비해 더 좋은 점은 문자열을 append() 하여 문자를 이을 수 있기 때문에 우리가 카운팅 정렬을 하듯이 나이를 기준으로 배열에 입력받으면서, 같은 나이일 경우 이미 해당 인덱스에 존재하던 문자열 뒤에 append 하여 이어주기만 하면 성능 측면에서도 매우 좋아진다. 즉, 간략하게 보자면 아래와 같다.

 

public static void main(String[] args) {
	StringBuilder[] sb = new StringBuilder[201];

	for(int i = 0; i < n; i++) {
		int age = in.nextInt();
		// 나이를 index 로 하여 해당 위치에 나이와 이름을 문자열로 저장
		sb[age].append(age + " " + in.next() + "\n");
	}
}

 

 

 

 

 

---

• 7가지 방법을 이용하여 풀이한다.

 

위에서 설명한 각 3가지의 방법을 Scanner 와 BufferedReader로 나누어 풀어보고자 한다. 이번 문제에서는 출력은 모두 StringBuilder 로 통일하겠다. (다만 첫 알고리즘 1번만 System.out.println() 반복출력을 하는 케이스도 추가하겠다.)

 

즉, 풀이 방법은 다음과 같다.

 

1. String[][] + Scanner + System.out.println

2. String[][] + Scanner + StringBuilder

3. String[][] + BufferedReader + StringBuilder

4. Person[] + Scanner + StringBuilder

5. Person[] + BufferedReader + StringBuilder

6. StringBuilder[] + Scanner + StringBuilder;

7. StringBuilder[] + BufferedReader + StringBuilder;

 

 

 

---

• 풀이

- 방법 1 : [String[][] + Scanner + System.out.println]

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {		

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		String[][] arr = new String[N][2];
		

		for(int i = 0; i < N; i++) {
			arr[i][0] = in.next();	// 나이
			arr[i][1] = in.next();	// 이름
		}

		
		Arrays.sort(arr, new Comparator<String[]>() {
			// 나이순으로 정렬
			@Override
			public int compare(String[] s1, String[] s2) {
				return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
			}
			
		});
		
		for(int i = 0; i < N; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}
        
		
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

아마 가장 쉽게 접근할 수 있는 방법이 아닐까.. 물론 람다식으로 compare 을 구현해도 된다. 그리고 앞서 말했지만 나이순으로 정렬하면 compre 메소드에서 나이가 같을경우(반환값이 0 인경우)는 두 객체의 위치를 바꾸지 않기 때문에 자연스럽게 입력순서로 정렬이 된다.

 

참고로 in.next() 대신 in.nextLine() 으로 한 줄을 읽고 문자열을 분리하여 읽을 수도 있으니 여러분의 선호에 맞게 수정하시면 된다.

 

 

 

 

 

---

- 방법 2 : [String[][] + Scanner + StringBuilder]

 

 

이 방법은 출력 방법만 바꾼 것이기 때문에 별다른 설명은 하지 하지 않겠다. (성능차이를 보여주기 위해 한 것이니..)

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {		

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		String[][] arr = new String[N][2];
		

		for(int i = 0; i < N; i++) {
			arr[i][0] = in.next();	// 나이
			arr[i][1] = in.next();	// 이름
		}

		
		Arrays.sort(arr, new Comparator<String[]>() {
			// 나이순으로 정렬
			@Override
			public int compare(String[] s1, String[] s2) {
				return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
			}
			
		});

		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			sb.append(arr[i][0]).append(' ').append(arr[i][1]).append('\n');
		}
        
		System.out.println(sb);
		
	}

}

 

 

 

 

 

 

 

 

 

 

---

 

 

 

- 방법 3 : [String[][] + BufferedReader + StringBuilder]

 

 

 

입력을 Scanner 대신 BufferedReader 으로 사용한 방법이다.

당연하다면 당연하겠지만 Scanner 에 비해 성능도 빠르다. 그리고 BufferedReader 는 한 줄을 읽기 때문에 문자열 분리가 필요한데, 이는 StringTokenizer 를 사용하여 문자열을 분리해주도록 하겠다

 

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

public class Main {
	public static void main(String[] args) throws IOException {		

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String[][] arr = new String[N][2];
		

		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			arr[i][0] = st.nextToken();	// 나이
			arr[i][1] = st.nextToken();	// 이름
		}

		
		Arrays.sort(arr, new Comparator<String[]>() {
			// 나이순으로 정렬
			@Override
			public int compare(String[] s1, String[] s2) {
				return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
			}
			
		});

		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			sb.append(arr[i][0]).append(' ').append(arr[i][1]).append('\n');
		}
        
		System.out.println(sb);
		
	}

}

 

 

이렇게 첫 번째 알고리즘의 다양한 입출력 방법을 보여줘봤다. 이 부분은 그리 어렵지 않을 것이다. 혹여 모른다면 아까 필자가 언급했던 링크의 글들을 꼭 읽어보시길 바란다.

 

 

 

 

 

 

---

 

 

 

- 방법 4 : [Person[] + Scanner + StringBuilder]

 

 

 

 

Person 클래스를 생성하여 출력하는 방법이다.

참고로 toString() 메소드는 객체를 출력할 때, 사용자의 임의로 출력하고자 하는 문자열을 지정할 수 있다. (이는 아마 다 알겠지만,, 혹시 모르니....)

 

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {		

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
        
		Person[] p = new Person[N];
		

		for(int i = 0; i < N; i++) {
			p[i] = new Person(in.nextInt(), in.next());
		}

		
		// 타입을 Person 으로 둘 것.
		Arrays.sort(p, new Comparator<Person>() {
			// 나이순으로 정렬
			@Override
			public int compare(Person s1, Person s2) {
				return s1.age - s2.age;
			}
			
		});

		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			// 객체배열의 객체를 출력하면 해당 인덱스의 객체의 toString() 이 출력 됨
			sb.append(p[i]);
		}
        
		System.out.println(sb);
		
	}
    
	public static class Person {
		int age;
		String name;
        
		public Person(int age, String name) {
			this.age = age;
			this.name = name;
		}
        
		@Override
		public String toString() {
			return age + " " + name + "\n";
		}
	}

}

 

 

이 방법도 꽤나 자주 사용되는 방법이다. 특히나 객체지향언어인 자바에서는 위와같은 객체를 다루는 일이 매우 많으니 위와 같은 방법도 익혀두면 매우 유용하다.

 

 

 

 

 

 

---

 

 

 

- 방법 5 : [Person[] + BufferedReader + StringBuilder]

 

 

 

 

입력을 Scanner 대신 BufferedReader 으로 사용한 방법이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {		

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
        
		Person[] p = new Person[N];
		

		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int age = Integer.parseInt(st.nextToken());
			String name = st.nextToken();
			p[i] = new Person(age, name);
		}

		
		// 타입을 Person 으로 둘 것.
		Arrays.sort(p, new Comparator<Person>() {
			// 나이순으로 정렬
			@Override
			public int compare(Person s1, Person s2) {
				return s1.age - s2.age;
			}
			
		});

		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			// 객체배열의 객체를 출력하면 해당 인덱스의 객체의 toString() 이 출력 됨
			sb.append(p[i]);
		}
        
		System.out.println(sb);
		
	}
    
	public static class Person {
		int age;
		String name;
        
		public Person(int age, String name) {
			this.age = age;
			this.name = name;
		}
        
		@Override
		public String toString() {
			return age + " " + name + "\n";
		}
	}

}

 

이 방법은 더이상 설명할 게 없는 것 같다.. 혹여 이해 안된다면 댓글로 남겨주시면 최대한 빨리 답변드리겠다.

 

 

 

 

 

 

 

---

 

 

 

- 방법 6 : [StringBuilder[] + Scanner + StringBuilder]

 

 

 

 

이번에는 StringBuilder 객체 배열을 사용한 방법이다.

이 방법을 사용하면 카운팅정렬과 유사한 원리로 더욱 빠른 정렬이 가능하다는 장점이 있다. 이전에 필자가 별찍기 10 코드에서 StringBuilder 을 배열처럼 사용했듯이 비슷한 개념으로 사용하면 된다.

 

즉, 마지막 문제답게 정렬 카테고리에서 배웠던 좋은 알고리즘인 카운팅정렬, 방금 풀었던 객체배열을 모두 써보는 것이다. 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();

		// 입력되는 나이의 범위 : 1 ~ 200
		StringBuilder[] p = new StringBuilder[201];
		
		//객체배열의 인덱스에 각 StringBuilder 객체를 생성해준다.
		for(int i = 0; i < p.length; i++) {
			p[i] = new StringBuilder();
		}
		
		for(int i = 0; i < N; i++) {
			int age = in.nextInt();
			String name = in.next();
			// 카운팅 정렬 : 나이를 index 로 하여 해당 배열에 나이와 이름을 append() 한다
			p[age].append(age).append(' ').append(name).append('\n');
		}
		
		StringBuilder sb = new StringBuilder();
		for(StringBuilder val : p) {
			sb.append(val);
		}
        
		System.out.println(sb);
	}
}

 

 

위 알고리즘 그대로, 카운팅 정렬과 유사하게 나이를 기준으로 인덱스삼아 p 배열에 문자열을 이어준다. 그러면 같은 나이인 다른 이름의 사람이 들어오더라도 해당 배열에 있던 문자열에 이어 쓰면 되기 때문에 크게 어려울 것이 없다.

 

 

 

 

 

---

 

 

 

- 방법 7 : [StringBuilder[] + BufferedReader + StringBuilder]

 

 

 

 

위 방법 6에서 입력을 BufferedReader 로 바꾼 방법이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		int N = Integer.parseInt(br.readLine());

		// 입력되는 나이의 범위 : 1 ~ 200
		StringBuilder[] p = new StringBuilder[201];
		
		//객체배열의 인덱스에 각 StringBuilder 객체를 생성해준다.
		for(int i = 0; i < p.length; i++) {
			p[i] = new StringBuilder();
		}
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int age = Integer.parseInt(st.nextToken());
			String name = st.nextToken();
			// 카운팅 정렬 : 나이를 index 로 하여 해당 배열에 나이와 이름을 append() 한다
			p[age].append(age).append(' ').append(name).append('\n');
		}
		
		StringBuilder sb = new StringBuilder();
		for(StringBuilder val : p) {
			sb.append(val);
		}
        
		System.out.println(sb);
	}
}

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

위에서 부터 순서대로

 

채점 번호 : 20441129  - 방법 7 ; [StringBuilder[] + BufferedReader + StringBuilder]

채점 번호 : 20441126  - 방법 6 ; [StringBuilder[] + Scanner + StringBuilder]

채점 번호 : 20441124  - 방법 5 : [Person[] + BufferedReader + StringBuilder]

채점 번호 : 20441114  - 방법 4 : [Person[] + Scanner + StringBuilder]

채점 번호 : 20441110  - 방법 3 : [String[][] + BufferedReader + StringBuilder]

채점 번호 : 20441105  - 방법 2 : [String[][] + Scanner + StringBuilder]

채점 번호 : 20441098  - 방법 1 : [String[][] + Scanner + System.out.println]

 

 

 

 

같은 알고리즘끼리는 같은 색으로 묶었다.

위 결과를 보면 알 수 있듯이 Scanner 와 BufferedReader 의 성능차이는 꽤 많이 나는 편이다. 더욱이 카운팅 정렬을 사용한 마지막의 경우는 정렬 시간복잡도가 O(N) 이라 매우 좋은 성능을 나타낸다.

 

 

---

• 정리

 

 

단계별로 풀어보기 정렬 카테고리의 마지막 문제가 끝났다. 마지막 문제인 만큼 다양한 풀이 방법을 보여주고자 하는 마음에 글이 조금 길어진감이 없지않아 있다. 그래도 만약 처음부터 끝까지 정독한다면 분명 여러분들께 도움이 되리라 생각한다.

 

이제 다음 카테고리는 백트래킹이다. 브루트포스랑 비슷하면서도 약간은 다른 개념인데 이는 이제 새로운 포스팅에서 다루어 보겠다.