문제 url:
나이순 정렬
문제:
🤔 문제 알아보기
해당 문제도, 정렬문제를 순서대로 풀어왔다면 아마 비슷한 형태인 것을 알 수 있다.
먼저, 나이와 이름을 받는데 그렇다면 해당 값들을 저장하기 위해 2차원 배열을 사용할 수 있을 것이다.
[[21, Junkyu] , [21, Dohyun], [20, Sunyoung]] 이런 식으로 말이다.
그렇다면 2차원 배열을 생성하는데, 이름은 숫자형이 안되기 때문에 문자열 2차원 배열을 생성하여 한번 풀어보자
준비를 이렇게 마쳤고, 다시 본문으로 돌아와 조건을 읽어보면
나이를 기준으로 오름차순을 한다. 하지만 만약 같다면 입력 순으로 나열하라고 한다.
즉, 나이를 기준으로 오름차순을 하는데, 같으면 비교를 하지 않고 그대로 놔두면 조건과 같게 출력이 될 것이다.
🐱👤 실제 코드
import java.io.*;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.Arrays;
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[] o1, String[] o2) {
if(Integer.parseInt(o1[0]) > Integer.parseInt(o2[0])) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
} else if(Integer.parseInt(o1[0]) < Integer.parseInt(o2[0])) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
}
return 0;
}
});
for (int i = 0; i< N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
}
}
여기서 주요 로직만 리뷰를 해본다면.
Arrays.sort(arr, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
if(Integer.parseInt(o1[0]) > Integer.parseInt(o2[0])) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
} else if(Integer.parseInt(o1[0]) < Integer.parseInt(o2[0])) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
}
return 0;
}
});해당 부분이 주요 로직이 될 것이다. 지금까지 정렬에 대해서 사용할 때, 다음과 같이 풀었을 것이다.
A, B 두 수가 존재한다고 가정하자,
1. A - B < 0 즉, A가 B보다 작다는 의미이므로 변경할 필요가 없다.
2. A - B == 0 즉, A와 B가 같다는 의미로 변경할 필요가 없다.
3. A - B > 0 즉, A가 B보다 크다는 의미로 변경할 필요가 있다.A와 B를 비교했을 때 양수, 음수, 0 을 기준으로 비교를하며 변경을 해왔다. 이 부분은 이번 문제에도 그대로 적용시키면 풀 수 있을 것이다.
🤢 코드 리팩토링
사실, 위의 로직에서 return문을 잘못 사용하는 바람에 문제를 못 풀었다. 덕분에 또 다른 로직들을 공부할 수 있어서 이렇게 다른 방법들도 배워보고자 한다.
🐱👤 리팩토링 코드 1) 클래스 객체 만들기
해당 방법은 이 문제를 풀기전에 필자도 생각해봤던 방법이었다. 하지만, 위의 로직이 더 낫다고 판단하여 위의 로직을 구현하였는데,
역시.. 해보지 않으면 모르는거라고 생각했던 것보다 깔끔하게 짜여서 놀라웠고 자바를 더 배우고 싶어 기존의 Python -> Java로 바꾼것에 대한 보상과 같은 문제였다.
기초 자바는 알고리즘 공부하면서 하나씩 배우는 것 같다. 따봉~ 👍👍👍
import java.io.*;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.Arrays;
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을 타입으로 하는 배열 생성;
Person[] arr = new Person[N];
for (int i = 0; i< N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// arr 배열안에 Person 객체 생성하여 초기화
arr[i] = new Person(Integer.parseInt(st.nextToken()), st.nextToken());
}
Arrays.sort(arr, new Comparator<Person>() {
@Override
public int compare(Person p1 , Person p2) {
return p1.age - p2.age;
}
});
for(int i = 0; i < N; i++) {
System.out.println(arr[i]);
}
}
static class Person {
int age;
String name;
Person(int age, String name) {
this.age = age;
this.name = name;
}
@Override
public String toString() {
return age + " " + name;
}
}
}
Person이라는 클래스를 따로 만든 다음, 객체를 생성하여 배열에 넣어준 다음
age 필드에 해당하는 값을 비교하여 정렬을 할 수 있다.
필자가 몰라서 기록하는 메서드
toString():
객체를 출력하면 자동으로 호출되는 메서드로 toString은 Object 클래스에 속해 있어 이렇게 오버라이드를 통해서 재정의하여 사용할 수 있다.즉, Person 객체를 출력하게 되면 toString()메서드가 출력되고 만약 이를 오버라이딩 한 것이 있다면, 재정의 된 내용으로 출력된다.
🐱👤 리팩토링 코드 2) 계수 정렬을 이용한 정렬
이 방법은 참신하다 못해.. 이게 되구나 허탈감을 줬다.
왜 장인들이.... '400문제는 풀어봐야 이제 쪼금 보인다' 라는 말이 무슨말인지 이해했다.
아무튼 바로 또 로직을 공부하고 풀어보았다.
import java.io.*;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.Arrays;
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 <= age <= 200 이라고 했기 때문이다.
// 여기서 나이를 통해 해당 인덱스 값에 나이와 이름을 저장하고자 한다.
StringBuilder[] sbd_arr = new StringBuilder[201];
// 현재 StringBuilder 데이터 타입의 배열만 있을뿐,
// 해당 인덱스에는 StringBuilder 객체가 존재하지 않아
// 추가 해줘야 해당 인덱스에서 StringBuilder를 사용할 수 있다.
for (int i = 0; i < sbd_arr.length; i++) {
sbd_arr[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();
sbd_arr[age].append(age).append(" ").append(name).append("\n");
}
// 배열에 값을 넣었지만, 출력을 할 수 있는 상태가 아니다.
// 그래서 출력을 할 수 있는 값들만 따로 보관하는
// StringBuilder 객체를 생성
StringBuilder sbd = new StringBuilder();
for (StringBuilder val : sbd_arr) {
sbd.append(val);
}
System.out.println(sbd);
}
}이번 문제는 로직 구현을 하다가 좀 막혀서 보고 하고 보고 하고 했다.
그만큼 완벽히 이해하지 못했던 것 같은데.. 아직도 기본적인 배열, 그리고 객체 생성에 대한 이해가 없어보이는 것 같아 살짝 마음이 아프다.
객체를 배열에 넣지않고, 돌리다가 NullPointException이 떠서 황급히 각 배열마다 new StringBuilder() 객체를 주입..
출력하기 위한 StringBuilder객체를 생성하지 않고, 그대로 출력하다가 줄바꿈만 표시된 터미널을 보고 윙?..
그리고 다시 보니 아!. 배열에 존재하는 값들을 또 출력을 위한 StringBuilder에 담아줘야 하구나... 그리고 부랴부랴 다시 짜고
🤢 회고
- 448ms -> StringBuilder를 이용한 계수 정렬
- 1512ms -> 클래스 객체 만든 다음 Arrays.sort()
- 1824ms -> 2차원 배열을 만든 다음 Arrays.sort()
확실히.. O(N)의 시간 복잡도를 가지는 계수 정렬이 빠르다....
나도 이렇게 이해하고 푸는 날이 올지 모르겠다.
여러 방법들을 보면서 공부하고 있는데, 아직까지는 식견이 넓어졌다는 느낌이 들진 않았다. 하지만 근래, 한 가지 방법이 아닌 두 가지 방법을 떠올리고 있는 모습을 보며
한 문제 한 문제 정성스레 풀고, 시간이 오래 걸려도 리팩토링 하면서 포스팅 하는 것이 어쩌면 나에게 많은 성장을 주고 있지 않은가? 하는 느낌이 든다.
사실, 보통 포스팅 하면 간단한 문제라도 1시간 가량 시간을 사용한다. 어려운 문제라면... 2 ~ 3시간은 보통이다. 그래서 많은 문제를 풀지 못해 시간을 줄여 볼까 생각을 했지만!
앞으로도 시간이 얼마나 걸리든 포스팅을 하고자 한다.
💜 참고자료
