I am visible
intro : List를 통해서도 풀 수 있지만 값의 범위가 지정되어 있으니 2차원 배열로도 풀 수 있다.
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
문제 풀이 (640ms)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 좌표값을 저장할 2차원 배열 선언
int[][] inputArray = new int[forCount][2];
// 빈복문을 통해 2차원 배열에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
inputArray[i][0] = Integer.parseInt(st.nextToken());
inputArray[i][1] = Integer.parseInt(st.nextToken());
}
// 배열 정렬
Arrays.sort(inputArray, (o1, o2) -> {
if (o1[0] != o2[0]) {
// x값이 다르다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
} else {
// x값이 같다면 y값을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
});
// 정렬된 2차원 배열 데이터 sb.append() 메서드를 통해 저장
for (int[] arr : inputArray) {
sb.append(arr[0])
.append(" ")
.append(arr[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
이 문제를 풀기전에 다른 비슷한 정렬 문제를 하나 풀어보니까 이제는 이런 문제나오면 반갑다.. 혹시 그 문제가 무엇인지 궁금하다면 영단어 암기는 괴로워 를 풀어보는걸 추천한다. 이문제랑 결이 비슷하면서도 조금 더 ? 어주 살짝 더 어려운 문제인거 같다.
문제 해석 방향
이 문제는 정렬의 조건이 오름차순으로 정렬해야 하는것으로 굉장히 명확하다, x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬 이라는 조건이 문제에서 주어지는데, 그렇다면 해당 정렬을 하기 위해 어떤 자료구조를 사용할지 선택만하면 된다. 초기에는 2차원 배열을 통해 데이터를 관리했던것은 아니고, List를 통해 데이터를 관리했는데, 다음과 같이 코드를 작성하여 문제를 풀었었다.
620ms 소요
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 좌표값을 저장할 리스트 선언 (타입은 1차원 배열)
List<int[]> list = new ArrayList<>();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 빈복문을 통해 리스트에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
// 리스트에 저장할 1차원 배열 객체 생성
int[] tempArray = new int[2];
tempArray[0] = Integer.parseInt(st.nextToken());
tempArray[1] = Integer.parseInt(st.nextToken());
list.add(tempArray);
}
// 리스트 정렬
list.sort((o1, o2) -> {
if (o1[0] != o2[0]) {
// x값이 다르다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
} else {
// x값이 같다면 y값을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
});
// 정렬된 리스트 sb.append() 메서드를 통해 저장
for (int[] intArray : list) {
sb.append(intArray[0])
.append(" ")
.append(intArray[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
List 타입으로 문제 잘 풀어놓고 왜 배열로 리팩토링을 하였는가 ?
항상 알고리즘 문제를 풀때 다양한 관점으로 문제를 풀어보려 하는데, 해당 문제는 배열로 풀 수 있는 가능성이 있었다. 그 이유는 입력값으로 정확히 배열의 사이즈를 지정할 수 있는 개수를 초기에 지정해주기에 배열로 선언해서 사이즈를 지정할 수 있었고, 해당 문제의 시간복잡도는 배열의 정렬을 어떻게 하는냐에 따라서 시간적으로 차이가 많이 날 것이라고 생각했다. 왜냐하면, Arrays.sort()는 List.sort()보다 이론적으로 빠르게 작동하기에 당연히 배열을 통해 문제를 푸는게 더 나을거라고 생각했다.
Arrays.sort()가 List.sort()보다 왜 더 빠르게 작동하는가 ?
보통 성능적으로 크게 차이가 나지 않을거라고 생각하지만 입력값의 크기가 커지면 커질수록 성능의 차이는 더 커진다. 그 이유는 List.sort()는 내부적으로 컬렉션을 배열로 변환하는 과정을 거친다. 그 이후 배열의 대한 정렬(Arrays.sort())를 진행하고 다시 List로 변환한다. 해당 과정을 거치는 이유 때문에 Arrays.sort()가 보다 더 빠르게 동작한다. (동작 단계로만 따져봐도 누가 더 빠르게 동작할지 알 수 있다.)
그래서 두개의 코드 실행 시간은 차이가 얼마인가 ?
이론적으로는 2차원 배열로 푸는것이 빠르다고 생각했는데 실제로는 리스트가 더 빨랐다. 여러번 실행해보니 거의 속도적인 차이는 없었는데, 그 이유는 문제에서 주어진 입력값의 개수가 크지않기에 속도적인 차이가 나지않았다. 아무래도 100,000개의 데이터를 처리하는 코드에 있어서는 큰 차이를 볼수없고, 몇백만개정도는 되어야 두개의 자료구조를 통한 풀이가 속도 차이가 있을 것 같다.
혹시 정렬코드 return o1 - o2 가 이해가 안된다면?
다른 방식으로도 정렬기준을 정할 수 있다. 다음과 같이 코드를 작성할 수 도 있고 사실상 해당 문제에 한해서는 속도적인 차이가 거의 나지를 않으니 본인 코드 스타일에 맞게 선택 하면 될 것 같다.
616ms 소요
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 좌표값을 저장할 리스트 선언 (타입은 1차원 배열)
List<int[]> list = new ArrayList<>();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 빈복문을 통해 리스트에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
// 리스트에 저장할 1차원 배열 객체 생성
int[] tempArray = new int[2];
tempArray[0] = Integer.parseInt(st.nextToken());
tempArray[1] = Integer.parseInt(st.nextToken());
list.add(tempArray);
}
// 리스트 정렬
list.sort((o1, o2) -> {
// x 값 기준으로의 오름차순 정렬
if (o1[0] < o2[0]) {
return -1;
} else if (o1[0] == o2[0]) {
// x 값이 같다면 y값 기준으로의 오름차순 정렬
if (o1[1] < o2[1]) {
return -1;
} else if (o1[1] == o2[1]) {
return 0;
} else {
return 1;
}
} else {
return 1;
}
});
// 정렬된 리스트 sb.append() 메서드를 통해 저장
for (int[] intArray : list) {
sb.append(intArray[0])
.append(" ")
.append(intArray[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
마무리
왜 리팩토링을 하면 할수록 속도가 더 느려지는지는 의문이지만(미비하게나마 느려진다), 분명히 이론적으로는 Arrays.sort()가 빠르다고했는데… 그냥 직관적으로 단순하게 풀어버릴걸 그랬나 싶기도 하지만 다양하게 테스트 해보고 왜 빠르고 느린지에 대해서 스스로 탐구하고 이해하는 과정이 나에게 큰 도움이 되었던 것 같다.