[백준] no11650: 좌표 정렬하기

문제

: 'X Y'로 구성된 좌표가 N개의 줄만큼 입력된다

: 좌표를 정렬하는데, X의 오름차순으로 정렬한다.

: X값이 같으면 Y의 오름차순으로 정렬한다.

N : 좌표 수

 

문제링크 : https://www.acmicpc.net/problem/11650

 

---

원리

: 우선 앞자리 수를 정렬 하고, 뒷 자리수를 정렬했다

---

풀이방법

: 기존 방법은 Arrays.sort를 사용하는게 일반적이다.

: 필자는 Stream과 Comparator와 이너클래스를 이용해 풀어보고자 한다.

---

나의 코드

: 소기의 목적은 달성했으나, 메모리 차이가 심하다.

 일반적인 풀이의 경우 50000내외의 메모리 / 500내외의 ms이지만, 아래의 경우엔 10만 메모리 / 1000ms가 된다.

public class no11650 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        /**
         * 반복 횟수와 값을 담을 ArrayList. ArrayList에 담을 객체는 이너클래스로 정의했다.
         */
        int N = Integer.parseInt(br.readLine());
        List<Factor> list = new ArrayList<>();

        /**
         * 입력된 값으로 Factor 객체를 만들어 list에 담아준다
         */
        for(int i=0; i<N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            Factor factor = new Factor(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            list.add(factor);
        }

        /**
         * Comparator를 이용해 정렬 조건을 만들어준다.
         * 첫 정렬 조건은 comparing()으로, 다중 정렬조건은 thenComparing()으로 추가시켜준다.
         */
        Comparator<Factor> compare = Comparator
                .comparing(Factor::getX)
                .thenComparing(Factor::getY);

        /**
         * stream을 이용한 list안의 객체를 정렬해줄 것이다.
         * 이때, 정렬 조건으로 Comparator객체를 사용한다.
         */
        List<Factor> list2 = list.stream().sorted(compare).collect(Collectors.toList());

        /**
         * 출력 형식에 맞게 출력해준다.
         */
        for(int i=0; i<list.size() ; i++) {
            bw.write(""+list2.get(i).getX()+" "+list2.get(i).getY()+"\n");
        }
        bw.close();
    }

    /**
     * 이너클래스 부분
     * 좌표값이 될 X와 Y를 필드로 두고, 생성자를 이용해 Factor를 생성해 줄 것이다.
     * Comparator에서 객체 안의 값을 얻어야 하므로 get메서드를 추가로 만들어 준다.
     */
    static class Factor {
        private int X;
        private int Y;

        public Factor(Integer X, Integer Y) {
            this.X = X;
            this.Y = Y;
        }

        public int getX() {
            return this.X;
        }

        public int getY() {
            return this.Y;
        }
    }
}

참고 링크: Comparator https://jinseongsoft.tistory.com/250

---

레퍼런스 코드

참고 링크 : https://st-lab.tistory.com/110