[백준 18870/2565/2470/4195] 자바

(title: [백준 18770/2565/2470/4195] 자바)

A. 좌표압축 BOJ 18870

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

18870번: 좌표 압축

난이도	Silver 2
풀이 시간	10 분
분류	정렬, Hash map
시간복잡도	1. 입력으로 주어지는 n 개의 숫자를 배열에 저장하는 부분 O(n) 2. 순위 할당을 위한 temp 배열을 정렬하는 부분 O(nlogn) 3. hash map 에 temp 배열의 요소를 추가하면서 중복된 값을 걸러내는 부분은 temp 배열을 처음부터 끝까지 순차탐색하므로 O(n) ▶ O(n+nlogn+n) ~= O(nlogn)
공간복잡도	1. arr 배열 O(n) 2. temp 배열 O(n) 3. hash map O(n) ▶ O(n+n+n) ~= O(n)

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine());
        Map<Integer, Integer> hm = new HashMap<>();
        int [] arr = new int[n];
        Integer [] temp = new Integer[n];
        stk = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            arr[i] = Integer.parseInt(stk.nextToken());
            temp[i] = arr[i];
        }

        Arrays.sort(temp); int rank = 0;
        for(int i = 0; i < n; i++){
            if(hm.containsKey(temp[i])){
                continue;
            } else {
                hm.put(temp[i], rank++);
            }
        }
        for(int i = 0 ; i < n ; i++){
            bw.write(hm.get(arr[i])+" ");
        } bw.write("\n");


        bw.flush();
        bw.close();
    }
}

 

B. 전깃줄 BOJ 2565

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

2565번: 전깃줄

난이도	Gold 5
풀이 시간	30 분
분류	LIS, DP
시간복잡도	O(n^2) ; n <= 100 이라 가능 n 이 크다면, binary search 를 이용한 nlogn LIS 풀이를 사용해야 함.
공간복잡도	O(n)

import java.io.*;
import java.util.*;


public class Main {
    static int n;
    static ArrayList<link> arr;
    static class link implements Comparable<link>{
        int left;
        int right;

        public link(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(link o) {
            if(this.left > o.left)
                return 1;
            else return -1;
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        n = Integer.parseInt(br.readLine());
        arr = new ArrayList<>();
        for(int i = 0 ; i < n; i++){
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            arr.add(new link(a, b));
        }
        int [] dp = new int[n];

        for(int i = 0 ; i < n; i++){
            dp[i] = 1;
        }

        Collections.sort(arr);

        int max = -1;
        for(int i = 0; i <n; i++){
            for(int j = 0 ; j < i ; j++){
                if(arr.get(j).right < arr.get(i).right){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    max = Math.max(max, dp[i]);
                }
            }
        }

        int ans = n-max;
        bw.write(ans+"\n");


        bw.flush();
        bw.close();
    }
}

 

C. 두 용액 BOJ 2470

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

2470번: 두 용액

난이도	Gold 5
풀이 시간	45분
분류	투 포인터
시간복잡도	O(nlogn)
공간복잡도	O(n)

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] ans = new int[2];

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }

        Arrays.sort(arr); // nlogn

        int left = 0;
        int right = n - 1;
        int val = Integer.MAX_VALUE;
        int t = 0;
        while (left < right) {
            t = Math.abs(arr[left]+arr[right]);
            if(t<val){
                val = t;
                ans[0] = arr[left];
                ans[1] = arr[right];
            }
            if(arr[left]+arr[right]<0){
                left++;
            } else {
                right--;
            }
        }

        bw.write(ans[0]+" "+ans[1]+"\n");
        bw.flush();
        bw.close();
    }
}

 

 

D. 친구 네트워크 BOJ 4195

이 문제는 기억해둘만한 포인트가 있다고 생각해서 아래에 상세하게 설명을 추가하였다!

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

4195번: 친구 네트워크

난이도	Gold 2
풀이 시간	50 분
분류	유니온 파인드(Union-Find)
시간복잡도	O(N)
공간복잡도	O(N)

▶ union-find 를 살짝 응용하는 문제이다. 다만, union 을 할 때마다 해당 집합의 크기를 출력해야 하는데 처음에는 단순하게 생각해서 시간초과를 받았다. 😢

 

 

처음에 생각한 방법은 아래와 같다.

 

▶ union(a, b) 를 한다면, a 와 b 를 일단 합치고, parent 배열을 현재 등록된 친구 개수만큼 순회하면서 a 와 같은 조상을 가지고 있는지 ( find(a) == find(iter)? ) 개수를 세어주는 방식을 택하였다. 하지만 이렇게 하면 대충 O(N) 번의 연산이 더 필요하기 때문에 결국 O(N^2) 의 시간복잡도를 가지게 되어 시간 초과가 발생한다.

▶ 즉, 특정 원소가 주어지면 해당 원소가 속한 집합의 크기를 구하는 방법을 보다 효율적으로 개선해야 한다. 

 

 

 

개선한 방법은 다음과 같다.

 

▶ 어차피, 원소가 속한 집합의 크기는 Union 을 할 때에만 변하는 게 맞다.

▶ 그러면 각각의 원소가 속한 집합의 사이즈를 저장할 배열을 따로 선언한 다음에, union 연산이 발생할 때 size 배열을 update 해주면 되지 않을까?

▶ 그렇게 해주면, a 라는 원소가 속한 집합의 사이즈를 구하는 것은 그냥 size[find(a)] 를 꺼내주면 되므로 대략 O(1) 에 해결이 가능하다.

 

 

 

size 배열에 대해서 조금 더 자세하게 설명하면 아래와 같다.

 

▶ 초기에 size 를 모두 1 로 초기화한다. 왜냐면 처음에는 다들 친구가 자기 자신밖에 없으니까! (초기 집합의 원소는 오직 자기 자신 뿐)

▶ union (a, b) 라는 연산이 발생했다고 가정해보자. 대충 러프하게 생각해서 b 라는 집합을 a 집합에 합쳐야 한다는 상황으로 이해해보면, size[b] 를 size[a] 에 축적시키면 될 것 임을 깨달을 수 있다. 그러니까 아래와 같이 union 연산을 수정해주자.

private static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (a < b) {
            parent[b] = a;
            size[a] += size[b];
        } else {
            parent[a] = b;
            size[b] += size[a];
        }
    }
}

이와 같이 해주면 size 배열은 각각의 원소가 속해 있는 집합의 크기를 저장하게 된다. 이와 같은 과정으로, 특정 원소가 속한 집합의 사이즈를 구하는 과정을 O(N) 에서 O(1) 로 최적화할 수 있고, 그러면 최종적인 시간 복잡도가 대략 O(N) 이 되기 때문에 문제를 해결할 수 있다!

 

 

 

전체 코드는 아래와 같다. 

 

 

import java.io.*;
import java.util.*;


public class Main {
    static int id = 1;
    static Map<String, Integer> hm = new HashMap<>();
    static int[] parent;
    static int[] size;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int tc = Integer.parseInt(br.readLine()); // 테스트 케이스
        while (tc > 0) {
            tc--;
            int f = Integer.parseInt(br.readLine()); // 친구 관계의 수

            size = new int[f * 2 + 1];
            parent = new int[f * 2 + 1];
            for (int i = 1; i <= f * 2; i++) {
                parent[i] = i;
                size[i] = 1;
            }

            for (int i = 0; i < f; i++) {
                stk = new StringTokenizer(br.readLine());
                String a = stk.nextToken();
                String b = stk.nextToken();

                edit(a);
                edit(b);

                int aidx = hm.get(a);
                int bidx = hm.get(b);
                if(aidx!=bidx)
                    union(aidx, bidx);
                bw.write(size[find(aidx)]+"\n");
            }
        }
        bw.flush();
        bw.close();
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (a < b) {
                parent[b] = a;
                size[a] += size[b];
            } else {
                parent[a] = b;
                size[b] += size[a];
            }
        }
    }

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

    private static void edit(String name) {
        if (hm.containsKey(name)) {
            hm.get(name);
        } else {
            hm.put(name, id++);
        }
    }
}