문제
1. 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
2. 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
[ X좌표 순 ] [ Y좌표 순 ]
| 예제 입력 1 5 3 4 1 1 1 -1 2 2 3 3 |
예제 출력 1 1 -1 1 1 2 2 3 3 3 4 |
예제 입력 1 5 0 4 1 2 1 -1 2 2 3 3 |
예제 출력 1 1 -1 1 2 2 2 3 3 0 4 |
문제풀이
이 두 문제는 매우 유사하기 때문에 같이 묶어서 설명하겠다.
문제를 읽어보면 알겠지만 2개의 인자 중 주 인자와 보조 인자를 설정하여 주 인자 순으로 정렬하되 순서가 같은 주 인자들은 보조 인자를 사용하여 정렬을 하는 문제이다.
그래서 본인은 다음과 같은 과정을 통해 문제를 해결하였다.
1. 주 인자를 1차원 배열에 담는다.
2. 주 인자를 key로 가지고 보조 인자들을 가지는 리스트를 value로 하는 map을 사용하여 좌표들을 입력받는다.
3. 주 인자를 가진 1차원 배열을 정렬한다.
4. 보조 인자들이 들어있는 리스트들을 정렬한다.
5. 정렬된 1차원 배열의 값들에 해당하는 value들을 리스트에서 뽑아내면서 출력한다
이상이다.
그럼 위 동작들을 코드로 설명하겠다. 여기서 좌표 정렬하기 1의 주 인자와 보조 인자는 x, y이고 좌표 정렬하기 2의 주 인자와 보조 인자는 y, x이다.
1.
먼저 얼마만큼 입력받을 것인지 n을 입력받고 주 인자를 저장할 1차원 배열(coor)을 선언한다.
그리고 map을 선언하는데 key는 정수형으로 value는 정수형 리스트로 정하여 선언한다.
여기서 linkedhashmap을 쓴 이유는 순차적으로 저장되면 찾을 때도 더 빠를 것 같아서 썼다.
그리고 임시로 문자열을 저장할 tmp변수를 선언한다.
2 ~ 3.
[ 1 ]
[ 2 ]
위 그림처럼 tmp에 저장할 값 문자열을 입력받고
coor배열에 x 또는 y를 입력받는다.
그리고 만약 해당 값이 map에 key로 존재하지 않는다면 map을 새로 생성한 후 그 안에 나머지 y 또는 x를 입력받는다.
그 후 주 인자가 들어있는 coor 배열을 정렬한다.
이렇게하면 주 인자들의 순서가 정렬된다.
4.
그렇가 저장된 map에서 value로 저장된 리스트들을 검사하면서 size가 1이라면 그 키에 해당하는 value가 1개 밖에 없다는 것이므로 아무 동작도 하지 않고 size가 2 이상이라면 해당 리스트를 정렬한다.
이렇게 함으로써 주 인자들에 해당하는 보조 인자들의 순서가 정렬된다.
5.
[ 1 ]
[ 2 ]
이제 주 인자 배열을 돌면서 값들을 리스트의 맨 처음에서 하나씩 꺼내어 그에 해당하는 값을 출력하고 해당 값을 value의 리스트에서 제거하는 식으로 정렬된 좌표들을 문자열에 추가한다.
[1]과 [2]의 빨간색으로 밑줄 친 부분은 x,y의 출력순서가 다른 부분이다.
그리고 완성된 문자열을 리턴하여 출력하면 모든 값들이 정상적으로 정렬되어 출력되는 것을 볼 수 있다.
Junit 테스트
junit테스트는 따로하지 않았다 왜냐하면 문제에 주어진 예시만 제대로 정렬해도 다른 모든 값들에 대해서 정상적으로 동작하기 때문이다.
시간 테스트
문제에 주어진 시간테스트를 하기위해 다음과 같은 코드를 작성하였다.
위 코드는 -100000 < x < 100000 , -100000 < y < 100000에 해당하는 좌표들을 입력된 n들을 갯수와 함께 출력해주는 코드이다.
위 코드를 사용하여 100,000개의 값들을 돌린결과
0.4 ~ 0.5초 정도 나오는 것을 확인할 수 있었다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
import java.io.*;
import java.util.*;
public class Main
{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static String sortCoordinate1() throws IOException {
int n = Integer.parseInt(br.readLine());
int[] coor = new int[n];
Map<Integer, List<Integer>> map = new LinkedHashMap<>();
String tmp;
// 입력받은 값들을 map에 저장하고 배열을 정렬
for(int i = 0,cnt=0;i < n;i++,cnt+=2)
{
tmp = br.readLine();
coor[i] = Integer.parseInt(tmp.substring(0,tmp.indexOf(' ')));
if(!map.containsKey(coor[i])) {map.put(coor[i],new ArrayList<>());}
map.get(coor[i]).add(Integer.parseInt(tmp.substring(tmp.indexOf(' ')+1)));
}
Arrays.sort(coor);
// 중복된 리스트를 정렬
for(int a :coor)
{
if(map.get(a).size()==1) continue;
map.get(a).sort(null);
}
// 각 리스트에 있는 키 값과 value 값을 문자열로 반환
StringBuffer stringBuffer = new StringBuffer("");
List<Integer> arr;
for(int a :coor)
{
arr = map.get(a);
stringBuffer.append(a + " " + arr.get(0) + "\n");
arr.remove(0);
}
return stringBuffer.toString();
}
public static String sortCoordinate2() throws IOException {
int n = Integer.parseInt(br.readLine());
int[] coor = new int[n];
Map<Integer, List<Integer>> map = new LinkedHashMap<>();
String tmp;
// 입력받은 값들을 map에 저장하고 배열을 정렬
for(int i = 0,cnt=0;i < n;i++,cnt+=2)
{
tmp = br.readLine();
coor[i] = Integer.parseInt(tmp.substring(tmp.indexOf(' ')+1));
if(!map.containsKey(coor[i])) {map.put(coor[i],new ArrayList<>());}
map.get(coor[i]).add(Integer.parseInt(tmp.substring(0,tmp.indexOf(' '))));
}
Arrays.sort(coor);
// 중복된 리스트를 정렬
for(int a :coor)
{
if(map.get(a).size()==1) continue;
map.get(a).sort(null);
}
// 각 리스트에 있는 키 값과 value 값을 문자열로 반환
StringBuffer stringBuffer = new StringBuffer("");
List<Integer> arr;
for(int a :coor)
{
arr = map.get(a);
stringBuffer.append(arr.get(0) + " " + a + "\n");
arr.remove(0);
}
return stringBuffer.toString();
}
public static void main(String args[]) throws IOException {
bw.write(sortCoordinate1());
bw.write(sortCoordinate2());
bw.flush();
bw.close();
}
}
|
cs |
느낀점
이 문제는 값을 입력하는 과정에서 조금 시간이 오래 걸려서 당황했던 문제였다.
우리가 직접 입력한 값들을 처리하는 실제 코드에서는 상관이 없지만 junit을 테스트하기 위해서 여러 값들을 입력받는 코드에서 문자열로 인자를 전달받았을 때 해당 문자열을 실제 좌표들로 변환하고 Map에 매핑하는 과정에서 값들을 하나씩 입력받으면 굉장히 오랜 시간이 걸렸었다.
이런 문제를 해결하고자 아래 코드를 이용하였다.
값을 str 문자열로 입력받은 뒤 제일 첫 번째 값을 빼서 n에 저장하고 나머지 문자열의 개행 문자를 모조리 공백으로 바꾼다.
그 후 모든 문자열을 공백을 기준으로 나눠서 배열에 저장하고 실제 값들을 저장할 땐 해당 배열에서 직접적으로 입력받았다.
왜냐하면 배열 자료구조는 값의 탐색이 빠르기 때문에 조금 더 빠르게 동작할 거라 생각했기 때문이다.
그 결과 메소드를 실행하는데 필요한 시간이 19초에서 1초 미만으로 줄었다.
처음에는 방법이 잘못된 건줄 알았지만 입력값을 처리하는 과정이 이렇게나 오래 걸리는 문제는 처음이라 당황하였다.
그리고 이 문제의 여러가지 풀이법을 보다가 내 코드보다 조금 더 나은 코드가 있어서 소개하려고 한다.
www.acmicpc.net/board/view/62866
글 읽기 - 자바 반례 질문이요ㅜㅜ
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
위 코드는 list형의 sort라는 메소드를 이용하여 정렬하는데 람다식을 사용하여 조금 더 간단히 문제를 풀었다. 위 코드는 2가지 인자 뿐만 2차원 좌표 뿐만 아니라 3차원 좌표, 4차원 좌표에 대해서도 응용하여 사용하면 굉장히 유용할 것 같아서 이곳에 기록해둔다.
'백준 온라인 저지 문제풀이 > JAVA' 카테고리의 다른 글
| [baekjoon 10814번] 정렬 - 나이순 정렬 (0) | 2021.03.27 |
|---|---|
| [baekjoon 1181번] 정렬 - 단어 정렬 (0) | 2021.03.27 |
| [baekjoon 1427번] 정렬 - 소트인사이드 (0) | 2021.03.01 |
| [baekjoon 2108번] 정렬 - 통계학 (0) | 2021.02.27 |
| [baekjoon 1436번] 브루트 포스 - 영화감독 숌 (0) | 2021.02.18 |