11650에 해당하는 글 1

백준 알고리즘 11650 - 좌표 정렬하기

JAVA/알고리즘|2018. 10. 4. 00:45

문제
입력된 좌표를 정렬해서 보여주는 문제이다.


코드

좌표를 담는 하나의 DTO 객체를 만들어서 comparable을 정의해서 사용해도 되나 좀 다르게 해보고 싶었다. 각 x좌표를 키로 사용하는 map을 만들고 각 x좌표마다 y좌표들을 담는 리스트가 존재한다. y좌표값이 채워질때는 정렬이 된 상태로 삽입된다. insertSort 메소드는 ATM 알고리즘에서 사용했던 것 가져왔다.

그리고 Map을 출력할 때는 Key를 기준으로 정렬한 후 forEach를 사용하여 정렬한다.

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
import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int count = sc.nextInt();
        Map<Integer, List<Integer>> datas = new LinkedHashMap<>();
 
        for (int i = 0; i < count; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            // x 좌표를 키로 y 좌표들을 보관하고 있는 List를 value로 사용함.
            if (datas.containsKey(x)) {
                insertSort(datas.get(x), y);
            } else {
                List<Integer> dataList = new LinkedList<>();
                insertSort(dataList, y);
                datas.put(x, dataList);
            }
        }
 
        // 키 값들을 정렬한 후 stream에 foreach를 사용하여 정렬
        datas.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(e -> {
            int key = e.getKey();
            for (Integer value : e.getValue()) {
                System.out.println(key + " " + value);
            }
        });
    }
 
    /**
     * 데이터를 정렬하면서 삽입
     *
     * @param list
     * @param insertData
     */
    private static void insertSort(List<Integer> list, int insertData) {
        for (int index = 0; index < list.size(); index++) {
            if (list.get(index) > insertData) {
                list.add(index, insertData);
                return;
            }
        }
 
        list.add(insertData);
    }
 
}
 
cs
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
import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int count = sc.nextInt();
        Map<Integer, List<Integer>> datas = new LinkedHashMap<>();
 
        for (int i = 0; i < count; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            // x 좌표를 키로 y 좌표들을 보관하고 있는 List를 value로 사용함.
            if (datas.containsKey(x)) {
                insertSort(datas.get(x), y);
            } else {
                List<Integer> dataList = new LinkedList<>();
                insertSort(dataList, y);
                datas.put(x, dataList);
            }
        }
 
        // 키 값들을 정렬한 후 stream에 foreach를 사용하여 정렬
        datas.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach(e -> {
            int key = e.getKey();
            for (Integer value : e.getValue()) {
                System.out.println(key + " " + value);
            }
        });
    }
 
    /**
     * 데이터를 정렬하면서 삽입
     *
     * @param list
     * @param insertData
     */
    private static void insertSort(List<Integer> list, int insertData) {
        for (int index = 0; index < list.size(); index++) {
            if (list.get(index) > insertData) {
                list.add(index, insertData);
                return;
            }
        }
 
        list.add(insertData);
    }
 
}
 
cs


자세한 소스코드는 github참고


https://github.com/weduls/algorithm/blob/master/%EC%A0%95%EB%A0%AC/%EC%A2%8C%ED%91%9C%20%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0/wedul/Main.java

댓글()