[백준] 1427번 : 소트인사이드 - JAVA [자바]

www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

---

• 문제

 

 

 

오랜만에 매우 쉬운 문제가 나왔다.

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 문제의 경우 접근 방법이 정말 무궁무진하다. 먼저 정렬 알고리즘으로 배열을 이용하여 Arrays.sort 를 사용하는 방법부터 카운팅정렬을 사용하는 방법, 이렇게 크게 두 가지가 있을 것이다.

 

 

또한 각 자릿수의 값을 정렬하는 것이다보니 입력방법도 다양하게 할 수 있다. Scanner 을 사용하여 입력받는 방법, BufferedReader 로 입력받는 방법, InputStream 으로 입력받는 방법 등 매우 많다.

 

각 자릿수를 값으로 사용하기 위해서는 정수를 그대로 입력받아 ÷10 을 하면서 나머지 값을 통해 자리수를 알아내는 방법이 있고, toCharArray() 메소드로 하나의 문자열을 각 자리의 문자(아스키값)으로 변환하여 char[] 배열로 만들어주는 방법, charAt() 을 사용하는 방법 등 매우 많으니 다양한 풀이 방법을 고민해보셨으면 한다.

 

 

 

 

 

---

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

 

이쯤되면 대부분은 Scanner 가 아닌 BufferedReader 도 사용하실 수 있으리라 생각된다.

그러니 다음과 같은 순서로 보여줄 것이니 각자 취향에 맞게 수정하거나 선택하시면 된다.

 

1. Scanner + 수학 연산 + 카운팅 정렬
2. Scanner + toCharArray + Arrays.sort
3. BufferedReader + toCharArray + Arrays.sort
4. BufferedReader + charAt + 카운팅 정렬
5. InputStream + 카운팅 정렬

 

 

이렇게 다양한 방법들이 있다. 그 외에도 다른 방법들을 조합하여 쓸 수 있는데 다 쓰려면 케이스만 18가지가 되어버리니 몇가지 대표적인 것만 골라서 보여주기로 한다.

 

 

 

 

---

• 풀이

- 방법 1 : Scanner + 수학 연산 + 카운팅 정렬

 

/*
Scanner + 수학 연산 + 카운팅 정렬
*/

import java.util.Scanner;

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

		Scanner in = new Scanner(System.in);

		int[] counting = new int[10];

		int N = in.nextInt();

		while (N != 0) {
			counting[N % 10]++;
			N /= 10;
		}

		for (int i = 9; i >= 0; i--) {
			while (counting[i]-- > 0) {
				System.out.print(i);
			}
		}

	}
}

 

 

카운팅 정렬 하면 각 자릿수는 0~9 까지이니 10칸의 배열만 사용하면 된다.

 

---

- 방법 2 : Scanner + toCharArray + Arrays.sort

 

 

아마 가장 간편한 방법이지 않을까 생각된다.

/*
 Scanner + toCharArray + Arrays.sort
*/

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

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

		Scanner in = new Scanner(System.in);

		char[] arr = in.nextLine().toCharArray();


		Arrays.sort(arr);

		for (int i = arr.length - 1; i >= 0; i--) {
			System.out.print(arr[i]);
		}

	}
}

 

 

 

참고로 char 형태이기 때문에 만약 배열을 연산을 할 경우 '0' ~ '9' 에 해당되는 값 (48~57)이 연산되기 때문에 이점 유의해야한다.

 

 

 

---

- 방법 3 : BufferedReader + toCharArray + Arrays.sort

 

 

위 방법 2에서 했던 알고리즘이랑 같고, 입력 방법만 바꾸어 BufferedReader 로 변환해준 것이다.

 

/*
BufferedReader + toCharArray + Arrays.sort
*/

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

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] arr = br.readLine().toCharArray();


		Arrays.sort(arr);

		for (int i = arr.length - 1; i >= 0; i--) {
			System.out.print(arr[i]);
		}

	}
}

 

 

 

 

 

 

---

- 방법 4 : BufferedReader + charAt + 카운팅 정렬

 

 

 

 

아마 문자열로 받고자 한다면 이 방법도 꽤 유용한 방법이다. 일단 charAt() 이 익숙한 메소드다보니 쉽게 접근할 수도 있고...

 

/*
BufferedReader + charAt + 카운팅 정렬
*/

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

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int[] counting = new int[10];
		String s = br.readLine();

		for (int i = 0; i < s.length(); i++) {
			counting[s.charAt(i) - '0']++;
		}

		for (int i = 9; i >= 0; i--) {
			while (counting[i]-- > 0) {
				System.out.print(i);
			}
		}
	}
}

 

 

 

 

 

---

- 방법 5 : InputStream + 카운팅 정렬

 

 

뭔가 각 자릿수별로 받는데 한 줄을 통째로 받고, 굳이 다시 또 쪼갤 필요가 있을까? 라는 생각에서 푼 코드다.

필자의 입력 뜯어보기를 읽어보셨다면 알겠지만 모든 문자들은 바이트단위로 읽어들인 뒤, 각 입력 방식에 맞춰 버퍼를 두고 인코딩을 한다거나 등 내부적인 작업들이 들어간다. 

그런데 처음부터 바이트 단위로 읽어들이는데 굳이 합쳐서 입력받을 필요가 있을까? 사용자 입장에서는 편할지는 몰라도 기계입장(?)에서는 편하지 않을 수 있다. 그러니 이 과정들을 간소화하여 풀어보고자 한다.

 

/*
InputStream + 카운팅 정렬
*/

import java.io.InputStream;
import java.io.IOException;

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

		InputStream in = System.in;

		int[] counting = new int[10];
		int c;
		while((c = in.read()) != '\n') {
			counting[c - '0']++;
		}

		for (int i = 9; i >= 0; i--) {
			while (counting[i]-- > 0) {
				System.out.print(i);
			}
		}
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

위에서 부터 순서대로

 

채점 번호 : 20165560 - 방법 5 : InputStream + 카운팅 정렬

채점 번호 : 20165556 - 방법 4 : BufferedReader + charAt + 카운팅 정렬

채점 번호 : 20165553 - 방법 3 : BufferedReader + toCharArray + Arrays.sort

채점 번호 : 20165549 - 방법 2 : Scanner + toCharArray + Arrays.sort

채점 번호 : 20165547 - 방법 1 : Scanner + 수학 연산 + 카운팅 정렬

 

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

나머지는 뭐... 사실상 알고리즘에 대한 성능차이는 그리 크게 차이나지 않는 것 같다.

---

• 정리

 

오늘은 '정말 다양한 풀이 방법이 있구나' 라는 것을 보여드리기 위해서 여러 방법들을 섞어가며 보여드렸다. 필자의 경우 문자단위로 풀이하는 문제들이 있을경우 앵간하면 System.in.read() 로 읽어들인다. 물론 한글을 사용할 때는 매우 조심해서 써야하지만 숫자나 영어의 경우는 크게 상관없이 쓸 수 있어서 편리하다.

 

여튼 여러분들도 위 방법들 말고도 다른 방식으로 조합해보면서 풀어보시는 것도 좋은 것 같다.