10165번 버스 노선

https://www.acmicpc.net/problem/10165

처음에 정렬을 중심으로 계속 생각했지만(정렬 후 설계 등)

역방향(높은 숫자에서 낮은 숫자로)을 어떻게 처리해야할지 계속 고민했었다.

결국 구글링을 통해 다른 분들의 아이디어를 얻었다.

핵심 : 출발점(s) 기준으로 오름차순, 도착점(e) 기준으로 내림차순, 포함 관계 유추

우선 2개의 그룹으로 나누자.

그룹 A(정방향) : 낮은 숫자에서 높은 숫자

그룹 B(역방향) : 높은 숫자에서 낮은 숫자

그렇다면, 그룹 B는 무조건 (n - 1)번과 0번 사이의 도로를 지나가게 된다.

그렇지만, 그룹 A는 (n - 1)번과 0번 사이의 도로를 절대 지나가지 못 한다.

따라서, 그룹 A의 모든 노선들은 그룹 B의 모든 노선들을 포함하지 못 한다.

그렇다면, 우리가 고려해야할 것은 3가지이다.

1. 그룹 A에 있는 노선들이 그룹 A의 노선들을 포함하는 경우

2. 그룹 B에 있는 노선들이 그룹 A의 노선들을 포함하는 경우

3. 그룹 B에 있는 노선들이 그룹 B의 노선들을 포함하는 경우

1. 그룹 A에 있는 노선들이 그룹 A의 노선들을 포함하는 경우

vector v에 있는 노선들 정보는

출발점(s)를 기준으로 오름차순, 도착점(e) 기준으로 내림차순 되어 있다고 가정하자.

그렇다면 다음과 같은 상황이 올 수 있다.

s e

1 7(앞)

1 6

2 7

2 6

3 4

4 8

4 7(뒤)

위의 상태에서는 선형 탐색을 할 경우 뒤에 나오는 노선이 앞에 나와 있는 노선을 포함하는 경우는 없다.

첫 번째는 그냥 비교할 변수에 도착점(e)을 저장시킨다.

두 번째 부터는 저장한 도착점(e) 기준으로 무조건 큰 경우만 출력할 답에 저장하고 다시 변수에 새로운 도착점(e)를 저장한다.

만약에 저장한 도착점(e)보다 작거나 같다는 것은 무조건 포함되는 경우이므로 그냥 넘어간다. 

이런 식으로 1의 상황을 해결할 수 있다.

2. 그룹 B에 있는 노선들이 그룹 A의 노선들을 포함하는 경우

- 그룹 B의 출발점(s) 중 최솟값(BsMin)과 그룹 A의 출발점(s)을 비교한다.

그룹 B는 무조건 0번 노드 이상으로 가기 때문에, 

그룹 A의 출발점(s)이 BsMin보다 크다는 것은 그림 기준으로도 보아도 포함된다.

- 그룹 B의 도착점(e) 중 최댓값(BeMax)과 그룹 A의 도착점(e)과 비교한다.

그룹 B는 0번 노드 이전부터 출발했기 때문에,

그룹 A의 도착점(e)이 BeMax보다 작다는 것은 그림 기준으로도 보아도 포함된다.

3. 그룹 B에 있는 노선들이 그룹 B의 노선들을 포함하는 경우

1과 같다.

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m, BsMin = Integer.MAX_VALUE, BeMax = Integer.MIN_VALUE;
    static Vector<info> A = new Vector<info>();
    static Vector<info> B = new Vector<info>();
    static boolean[] ans;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        
        ans = new boolean[m + 1];
        int s, e;
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            
            if(s < e) {
                A.add(new info(s, e, i + 1));
            }
            else {
                B.add(new info(s, e, i + 1));
                BsMin = Math.min(BsMin, s); // 그룹 B의 출발점(s)의 최솟값
                BeMax = Math.max(BeMax, e); // 그룹 B의 도착점(e)의 최댓값
            }
        }
        
        Collections.sort(A, new Comparator<info>() {
            public int compare(info a, info b) {
                if(a.s < b.s) {
                    return -1;
                }
                else if(a.s == b.s){
                    if(a.e < b.e) {
                        return 1;
                    }
                    else {
                        return -1;
                    }
                }
                else {
                    return 1;
                }
            }
        });
        
        Collections.sort(B, new Comparator<info>() {
            public int compare(info a, info b) {
                if(a.s < b.s) {
                    return -1;
                }
                else if(a.s == b.s){
                    if(a.e < b.e) {
                        return 1;
                    }
                    else {
                        return -1;
                    }
                }
                else {
                    return 1;
                }
            }
        });
        
        int em = Integer.MIN_VALUE;
        
        for(info i : A) {
            
            // 1. 그룹 A에 있는 노선들이 그룹 A의 노선들을 포함하는 경우
            if(em < i.e) {
                em = i.e;
            }
            else {
                ans[i.idx] = true;
            }
            
            // 2. 그룹 B에 있는 노선들이 그룹 A의 노선들을 포함하는 경우
            // 그룹 B의 출발점(s) 최솟값보다 크거나 같거나
            // 또는
            // 그룹 B의 도착점(e) 최댓값보다 작거나 같으면
            // 무시(포함되기 때문에)
            if(BsMin <= i.s || BeMax >= i.e) {
                ans[i.idx] = true; 
            }
        }
        
        em = Integer.MIN_VALUE;
        
        // 3. 그룹 B에 있는 노선들이 그룹 B의 노선들을 포함하는 경우
        for(info i : B) {
            if(em < i.e) {
                em = i.e;
            }
            else {
                ans[i.idx] = true;
            }
        }
 
        for(int i=1; i<=m; i++) {
            if(!ans[i]) {
                bw.write(String.valueOf(i) + " ");
            }
        }
        
        bw.write(String.valueOf("\n"));
        bw.flush();
        bw.close();
    }
}
 
class info {
    
    int s, e, idx;
    
    info(int s, int e, int idx) {
        this.s = s;
        this.e = e;
        this.idx = idx;
    }
}