문제 url:
소트인사이드
문제:
🤔 문제 알아보기
이제는 오름차순이 아닌 내림차순으로 주어지며, 입력을 하나의 값으로 받는다.
보통 정렬을 할 때는 우리는 왼쪽값과 오른쪽값을 비교하며 정렬을 하는데,
하나의 수로 받으면 나누기가 어려울 수 있다.
그래서 입력 N을 String으로 받아서 이를 toCharArray() 메서드를 통해 배열로 만들어 준다.
이렇게 해주면 초기 세팅은 다 된것이다. 그럼 이제 문제를 같이 보면서 풀이를 해보겠다.
이번에는 Arrays.sort() , Arrays.sort(arr, Collections.reverseOrder()), 계수정렬 총 3가지로 풀이를 해보겠다.
🐱👤 실제 코드 1) Arrays.sort()
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String N = br.readLine();
char[] arr = N.toCharArray();
Arrays.sort(arr);
for (int i = arr.length -1; i >=0; i--) {
System.out.print(arr[i]);
}
}
}
Arrays.sort()는 여러번 언급한 적이 있어, 길게 설명하는 대신 모르는 분을 위해 짤막하게 말씀드리자면,
java.util.Arrays 클래스에서 제공하는 정적 메서드(static method)로 객체를 생성하지 않고도 사용할 수 있는 메서드이다.
Arrays.sort()는 DualPivotQuicksort 알고리즘을 사용하여 기존의 퀵소트보다 빠르게 정렬하는 장점이 존재한다. 그래서 정렬시 사용할 때 효율이 좋다.
평균 O(N logN)의 시간 복잡도를 가진다고 한다. 하지만, 퀵 정렬의 단점인 잘 정렬된 배열이라면 최악 O(N ^ 2)의 시간 복잡도를 가진다고 한다.
설명은 여기까지 하고, Arrays.sort로 인해 현재 배열은 오름차순이 된 것이다. 하지만 우리는 내림차순을 해야하는데... 결론부터 말씀드리면
for문으로 그냥 마지막 인덱스부터 0번째 인덱스까지 하면 그게 내림차순이 되는 것이다.
그렇다면 왜 sort()메서드 안에 존재하는 Collecitons.reverseOrder() 메서드를 사용하지 않는지 궁금하다. 그건 아래 코드와 함께 설명해보겠다.
🐱👤 실제 코드 2) Using Collections.reverseOrder()
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String N = br.readLine();
Character[] arr = new Character[N.length()];
for (int i = 0; i< arr.length; i++) {
arr[i] = N.charAt(i);
}
Arrays.sort(arr, Collections.reverseOrder());
for(int i = 0; i< arr.length; i++) {
System.out.print(arr[i]);
}
}
}
아시는 분은 아시겠지만, 모르는 분을 위해 Collections.reverseOrder()에 대해서 간략히 설명하면,
※로우 레벨까지는 다루지 않겠다.
return 값을 잘 보면 제너릭 타입으로<t>를 받는 것을 볼 수 있는데,즉, 우리가 아는 primitive(원시 타입 ex. int, double)은 받을 수 없고 wrapper class(Integer, Double)로 받아야 사용할 수 있다.
Collections.reverseOrder()메서드를 사용할 때 반드시 유의해야 하는 점이다.
그래서 위의 코드를 보면 배열을 생성할 때 Char가 아닌 Character 타입으로 정의한 것을 볼 수 있으며 toCharArray() 메서드를 사용할 수 없어 일일이 charAt()메서드를 이용해 넣는 모습을 볼 수 있다.
그렇다면, 단순히 이러한 복잡한 과정 때문에 첫 번째 방식을 이용한 것인가?
필자는 게을러서 그럴 수 있다
그것 이외에도 존재한다.
이전에 Collections 프레임워크에 대해 알아보면서 정리한 글을 보면 이해가 될 것이다.
컬렉션 프레임워크에 저장할 수 있는 데이터는 객체(Object)만 가능하다.
그래서 int형이나 double형과 같은 자바의 primitive 타입(원시 타입)은 적재하지 못한다.
따라서 primitive 타입을 wrapper 타입으로 변환해
Integer나, Double 객체로 박싱(Boxing)하여 저장해야 한다.
ex) List list = new List<>(); 이런것을 많이 봤을 것이다.또한, 객체를 담는 다는 것은 결국 주소값을 담는 것이기 때문에, null 역시 저장할 수 있다.
primitive 타입인 int형은 크기가 4Byte이다.
하지만 Wrapper 타입인 Integer는 (32bit JVM)환경에서는
객체의 헤더(8Byte), 원시필드(4Byte), 패딩(4Byte)로 최소 16Byte를 차지한다고 한다.
또한 이러한 객체 데이터들을 다시 주소로 연결하기 때문에 16 + a가 된다.
이 글을 인용해서 컬랙션 프레임워크이 적재할 수 있는 데이터는 객체만 가능하기에 Wrapper class를 이용해야 하는 것이고,
Wrapper 타입을 사용하기 때문에 메모리도 16 + alpha byte가 더 들어가는 것이다.
즉, 귀찮고... 메모리도 더 들어간다고 한 줄 요약이 가능하다
그럼 마지막으로 계수 정렬로 푼 문제까지 설명하면서 마치겠다.
🐱👤 실제 코드 3) 계수 정렬
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String N = br.readLine();
char[] arr = N.toCharArray();
int num_range = -1;
for (int i = 0; i< arr.length; i++) {
if(num_range < arr[i] - '0') {
num_range = arr[i] - '0';
}
}
int[] counting = new int[num_range+1];
for(int i =0; i < arr.length; i++) {
counting[arr[i] - '0']++;
}
for(int i = counting.length-1; i>= 0; i--) {
while(counting[i]-- > 0) {
System.out.print(i);
}
}
}
}
계수 정렬은 기존과 달리 각 테스트 케이스마다 수의 범위(range)가 다르기 때문에 아래와 같은 로직을 추가했다.
int num_range = -1;
for (int i = 0; i< arr.length; i++) {
if(num_range < arr[i] - '0') {
num_range = arr[i] - '0';
}
}여기서 '0'을 뺀 이유는 현재 arr은 문자형으로 되어 있기 때문에 이를 아스키 코드인 '0'을 빼줌으로써 숫자형 0으로 치환되어 계산할 수 있게 된다.
계수 정렬에 관해서 모르는 분을 위해서, 아래의 링크를 확인해주시면 감사하겠습니다.
[정렬] 계수 정렬(counting sort)에 대해 알아보자
읽기 귀찮으신 분을 위해 간략히 설명하자면,
계수 정렬은 배열에 데이터가 말 그대로 몇번 나왔는지 counting하며 이를 이용해 정렬하는 방식을 말한다.
🤢 회고
이렇게 총 3가지를 정리해봤고, 시간과 메모리를 보여주면 아래와 같다.
- 맨위 부터 계수정렬
- Collections.reverseOrder()
- sort()
특별히 차이가 안보여서 아쉽긴 하지만, 두 번쨰와 세 번째의 메모리가 차이가 있는 것을 보아 아까 위에서 설명한 바로 메모리를 조금 더 사용하는 것을 알 수 있다.
😎 리팩토링
어김없이 찾아온 리팩토링.. 필자도 3가지 방법을 생각하면서 음 그래! 나머지 방법이 또 있을까? 이정도면 포스팅을 마무리하자고 했지만 차마 블로그 아이덴티티를 무시하지 못했다.
그래서 또 어느 신기방기한 방법이 있을까 찾으니... 방법이 참 많았었다.
오늘도 얘기하는거지만, 개발의 세상은 무협지와 같다.
강호에는 늘 강자가 존재하고 무술의 한계가 보이면 더 성장하지 못한다.
그래서 이번에는.. 두 가지 방법을 가져왔다. 엄밀히 사실 한 가지이다. 한가지는 생각을 했지만 귀찮아서 하지 않았기 때문 어쨋든 두 가지 방법을 짧게 기록해보고자 한다.
🐱👤 리팩토링 1) 문자형이 아닌 숫자형으로 풀기 with 계수정렬
import java.io.*;
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());
// 아까 생각하지 못햇지만, 블로그 보니. 알았다
// 결국 수의 범위는 0 ~9 까지 존재하니깐 10으로 미리 줄 수 있었다.
int[] counting = new int[10];
while (N!=0) {
int index = N % 10; // 1의 자리 뽑기
counting[index]++;
N /= 10;
}
for(int i = counting.length-1; i>= 0; i--) {
while(counting[i]-- > 0) {
System.out.print(i);
}
}
}
}
보다피 나머지 연산자인 %를 이용해 각 자리를 구하여 해당 값을 counting 배열에 1씩 증가하는 것을 볼 수 있다.
🐱👤 리팩토링 2) InputStream으로 풀기 with 계수 정렬
import java.io.*;
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') { //입력이 줄바꿈이 될떄까지 반복
//입력 스트림은 문자형으로 받기 때문에 숫자 0을 나타내려면
//아스키 코드 '0' 혹은 - 48을 해줘야 한다.
counting[c - '0']++;
}
for(int i = counting.length-1; i >= 0; i--) {
while(counting[i]-- > 0) {
System.out.print(i);
}
}
}
}
사실 이것 때문에 리팩토링 세션을 적었다. InputStream에 대해서 다루지 못해 설명은 하지는 못하지만, 대충 코드적으로 이해한 바를 적는다면,
InputStream(입력 스트림)을 통해 사용자에게 키보드 등의 기계적 입력을 받으면,
in.read()를 통해 바이트로 읽을 수 있다.
하지만! while문을 적은 이유는 만약 우리가 2143을 입력을 받았다고 하면, 1byte씩 읽기 때문에 나머지 바이트는 스트림에 남아있어 값이 달리 나올 수 있다.
그래서 마지막 스트림까지 읽고자 반복문을 사용하는 것이다.
필자가 이해한 바는 이정도이면 InputStream에 대해서 더 알고 싶으시다면 필자가 읽은 링크를 아래에 올려 놓겠다.
JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader] Stranger's LAB
💜 참고자료
