[백준] 7578번 공장 문제 풀이

이미지를 클릭하면 문제 페이지로 이동합니다

 

풀이 

고려해야할 점

• 입력 값의 크기가 최대 500,000이므로 시간 복잡도를 고려하면 O(nlogn) 이내로 해결해야 한다.  
• 연결되는 기계의 번호를 기준으로 연결되는 기계의 위치를 저장해야 한다. 

문제의 핵심 포인트

• 첫 번째 줄의 인덱스를 기준으로 두 번째 줄 입력을 인덱스화하여 배열을 생성한다. 
• 두 번째 줄 입력에서 역순으로 정렬되어 있는 쌍들의 개수를 구한다. 
• 케이블이 교차한다는 것은 기계의 위치가 역순으로 존재하는 것이 존재한다는 의미이다. 

 

문제 해결 아이디어

• 병합 정렬을 하면서 역순으로 정렬된 기계의 개수를 센다. (nlogn)
• 또 다른 방법으로 세그먼트 트리를 응용하여 문제를 해결할 수 있다. 

 

코드

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

public class Main {
    // 결과값을 저장할 변수
    static long result;
    // 원본 배열과 임시 배열
    static int[] a, temp;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 배열 크기 입력
        int[] map = new int[1000001]; // 수의 위치를 저장할 배열
        a = new int[n]; // 정렬된 위치를 저장할 배열
        temp = new int[n]; // 병합 정렬 시 사용할 임시 배열
        result = 0;

        // 첫 번째 배열 입력 및 map에 각 수의 위치 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            map[num] = i;
        }

        // 두 번째 배열 입력 및 첫 번째 배열의 인덱스를 기반으로 재배열
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            a[i] = map[num];
        }

        // 병합 정렬을 이용해 역순 쌍의 개수 계산
        merge_sort(0, n - 1);
        System.out.print(result);
    }

    // 병합 정렬 함수 (재귀 호출)
    static void merge_sort(int left, int right) {
        if (left < right) { // 분할 가능할 때만 수행
            int mid = (left + right) / 2; // 중간 지점 계산
            merge_sort(left, mid); // 왼쪽 부분 배열 정렬
            merge_sort(mid + 1, right); // 오른쪽 부분 배열 정렬
            merge(left, mid, right); // 정렬된 부분 배열 병합
        }
    }

    // 병합 및 역순 쌍 개수 계산 함수
    static void merge(int left, int mid, int right) {
        int l = left; // 왼쪽 시작 인덱스
        int m = mid + 1; // 오른쪽 시작 인덱스
        int k = left; // 임시 배열 인덱스

        // 병합 과정에서 역순 쌍 개수 계산
        while (l <= mid && m <= right) {
            if (a[l] <= a[m]) { // 왼쪽이 작으면 그대로 복사
                temp[k++] = a[l++];
            } else { // 오른쪽이 작으면 역순 쌍 발생
                temp[k++] = a[m++];
                result += (long) (mid - l + 1); // 역순 쌍 개수 추가
            }
        }

        // 남은 요소들 병합
        while (l <= mid) temp[k++] = a[l++];
        while (m <= right) temp[k++] = a[m++];

        // 임시 배열을 원본 배열에 복사
        for (int i = left; i <= right; i++) a[i] = temp[i];
    }
}

 

유사한 문제

[백준] 1517번 버블 정렬