[백준 10775번] 공항

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

방법 1 DSU

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Greedy10775 {
    static int G, P;

    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find(x);
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        parent[rootA] = rootB;
    }

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

        G = Integer.parseInt(br.readLine());
        P = Integer.parseInt(br.readLine());
        int result = 0;
        parent = new int[G+1];

        for (int i = 1; i <= G; i++) {
            parent[i] =i;
        }

        for (int i = 0; i < P; i++) {
            int g = Integer.parseInt(br.readLine());
            int park = find(g);

            if(park ==0) break;
            result++;

            union(park, park-1);
        }

        System.out.println(result);
    }
}

 

방법2 자료구조

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Greedy10775 {
    static int G, P;

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

        G = Integer.parseInt(br.readLine());
        P = Integer.parseInt(br.readLine());
        int result = 0;
        TreeSet<Integer> parks = new TreeSet<>();

        for (int i = 1; i <= G; i++) {
            parks.add(i);
        }

        for (int i = 0; i < P; i++) {
            int park = Integer.parseInt(br.readLine());
            Integer air = parks.floor(park);
            if (air == null) {
                break;
            }

            parks.remove(air);
            result++;
        }

        System.out.println(result);
    }
}

 

문제가 간다하였지만 시간초과가 또 발생!!

TreeSet으로 풀면 엄청 간단하다. 실버인줄 

하지만 DSU 방식으로 풀면 조금 헷갈린 문제였다.