[자바] 백준 7578 - 공장 (java)

 문제 : boj7578

---

 

필요 알고리즘 개념

• 제곱근 분할법, 펜윅 트리, 세그먼트 트리 등
  
  • 구간 쿼리 알고리즘(자료구조)를 알고 있어야 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

 

  언제 줄이 꼬일지만 찾는다면 어떻게 해결해야할지 알 수 있다. 아래와 같이 식별번호대신 A에 나열되 있던 순서대로 번호를 매겨서 그걸 B에도 동일한 식별번호에 작성해보자.

 

  만약 B가 A와 동일한 순서대로였다면 0-1-2-3-4가 됬을 것이다. 하지만 B는 현재 1-3-0-2-4이고, 번호가 A의 순서이므로 저 숫자의 나열만 가지고 줄이 꼬인 수를 알 수 있다. 1-3-0-2-4를 순서대로 진행하면서 자신보다 높은 숫자가 나온다면 해당 줄과 꼬이게 된다. 즉 A에서는 앞부분에 나왔는데 B에서는 뒤에 나온다면 당연히 그만큼 줄이 꼬이게 되는 식이다.

 

  예를들어 1-3-0-2-4를 순서대로 진행해보자.

A. 1 : 현재 앞에 나온게 없으므로 줄이 꼬인게 없다.

B. 1-3 : 3보다 큰 번호가 없으므로 줄이 꼬인게 없다. (A에서 1번으로 나온것 보다 3번으로 나온게 뒤에 나오니까)

C. 1-3-0 : A에서 맨 처음에 나온 것 보다 뒤에 나온게 2개나 B에서 먼저 나왔다. 따라서 1,3번 선이 0번 선과 꼬이므로 2개가 꼬인다.

D. 1-3-0-2 : 마찬가지로 2가 나오기 전에 3이 나왔으므로 1개가 꼬이게 된다.

E. 1-3-0-2-4 : 4보다 높은 번호가 없으므로 꼬인게 추가되지 않는다.

최종적으로 C와 D에서 총 3개가 꼬인게 된다.

 

  즉, A 순서대로 B에 번호를 매기고 순서대로 확인해봤을 때, 현재 번호보다 높은 번호가 이전에 몇 개 나왔는지만 알면 풀 수 있는 문제이다.

 

  A와 B를 번호로 짝짓는 부분은 HashMap 등을 사용하면 어렵지 않게 해결할 수 있다. 문제는 현재까지 나온 현재 보고있는 번호보다 높은 번호의 개수를 세는게 그리 쉽진 않다는건데, N이 500,000이나 되므로 매번 확인할 경우 O(N^2)이 되서 시간초과가 나게 된다. 이걸 유효한 시간 내에 해결할 수 있는 자료구조 혹은 방식은 segment tree, fenwick tree(binary indexed tree), sqrt decomposition 등이 있다. 이 중 맘에 드는 걸 공부해서 적용해보면 되겠다.

 

  이하의 코드는 sqrt decomposition와 fenwick tree로 짠 코드이다. 개인적으로 이해하기도 쉽고 구현하기도 편해서 좋아한다.

 

  펜윅 트리의 경우 펜윅 트리 글에서 기본 : 펜윅트리 부분을 읽어보면 이 문제를 풀 수 있다.

 

---

 

코드 (제곱근 분할법) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    int n, sqrtN;
    int[] bucket;
    boolean[] chk;

    private int getAnswer(int idx) {
        int cnt = 0;
        while (idx<n && idx%sqrtN!=0) {
            if (chk[idx])
                cnt++;
            idx++;
        }
        if (idx != n) {
            for (int i = idx/sqrtN; i < bucket.length; i++) {
                cnt += bucket[i];
            }
        }
        return cnt;
    }

    private void add(int idx) {
        chk[idx] = true;
        bucket[idx/sqrtN]++;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(Integer.parseInt(st.nextToken()), i);
        }
        sqrtN = (int)Math.sqrt(n);
        bucket = new int[n/sqrtN+1];
        chk = new boolean[n];

        st = new StringTokenizer(br.readLine());
        long sum = 0;
        for (int i = 0; i < n; i++) {
            int cur = hm.get(Integer.parseInt(st.nextToken()));
            sum += getAnswer(cur);
            add(cur);
        }
        System.out.println(sum);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드 (펜윅 트리) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    int n;
    int[] bit;
    boolean[] chk;

    private int getPrefixSum(int idx) {
        int answer = 0;
        while (idx > 0) {
            answer += bit[idx];
            idx -= idx&-idx;
        }
        return answer;
    }

    private int query(int idx) {
        return getPrefixSum(n) - getPrefixSum(idx);
    }

    private void update(int idx) {
        chk[idx] = true;
        while (idx <= n) {
            bit[idx] += 1;
            idx += idx&-idx;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> hm = new HashMap<>();
        bit = new int[n+1];
        for (int i = 1; i <= n; i++) {
            hm.put(Integer.parseInt(st.nextToken()), i);
        }

        chk = new boolean[n+1];

        st = new StringTokenizer(br.readLine());
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            int cur = hm.get(Integer.parseInt(st.nextToken()));
            sum += query(cur);
            update(cur);
        }
        System.out.println(sum);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}