백준 5419번

풀이

첫 번째 시도

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static class Island {
        int x;
        int y;
        public Island(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while(T-->0) {
            int N = Integer.parseInt(br.readLine());
            ArrayList<Island> alist = new ArrayList<>();
            while(N-->0) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                alist.add(new Island(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            Collections.sort(alist, (i1,i2)-> {
                if(i1.x == i2.x) {
                    return i2.y-i1.y;
                }
                return i1.x-i2.x;
            });
            int cnt = 0;
            for(int i = 0; i < alist.size(); i++) {
                Island island = alist.get(i);
                for(int j = i+1; j < alist.size(); j++) {
                    if(island.y >= alist.get(j).y) {
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

우선,

어떤 섬 (x1,y1)에 대해서 어떤 다른 섬 (x2,y2)가 남동쪽에 있다는 것은
x1 <= x2 이며 (동쪽)
y1 >= y2 임을 의미한다.

일단 모든 섬들을 리스트에 저장한 후에 x좌표의 오름차순으로, 같은 x좌표에 대해서는 y좌표의 내림차순으로 정렬하였다.
(따라서 정렬 후, 어떤 인덱스 i에 위치한 섬에 대해서 i보다 작은 인덱스의 섬은 서쪽에 위치함 -> x좌표가 더 작으므로)

이제 자신보다 뒷 인덱스에 있는 섬들을 확인해서 y좌표가 자신의 y좌표보다 작거나 같은 것이 있다면 해당 좌표의 섬으로 이동이 가능한 것을 확인할 수 있다.

그런데 한 인덱스에 대해서 또 뒤의 인덱스들을 순차탐색 하면 O(N^2) ... ㅎ !
이건 아니다..싶은 마음이었지만 다른 방법이 떠오르지 않아 일단 짜봤음.
그랬더니 역시 시간 초과가 났다.

구글링

구글링 해본 결과 다들 하나같이 세그먼트 트리를 이용하신다.
근데 난 세그먼트 트리를 처음 들어본다. (..)

세그먼트 트리 유튜브 강의

ㅎㅎ 세그먼트 트리 공부하고 다시 풀어보자 .. 😇