백준 2012 자바 - 등수 매기기 (BOJ 2012 JAVA)

문제 : boj2012

 

 

1.

  흔히 생각해볼만한게, 예를들어 '1 8 4 5 6'과 같은 입력이 있는 경우 총 1~5등 까지를 매칭시켜야 한다. 그렇다면 1~5등 사이 중 일단 자기가 원한 등수가 가능한 녀석들을 매칭시키자. 그럼 1, 4, 5는 1~5등 내에 매칭이 가능할 것이다. 이제 8과 6이 남는데, 당연하게도 정렬해서 매칭시키는 것이 더 정답에 가까울 것임을 유추할 수 있다. 따라서 정렬 후 차례대로 남는 위치에 매칭시키면 답을 구할 수 있다.

  '1'의 방법을 정리하면

1.1 N을 입력받는다.

1.2 1~N에 바로 매칭이 가능한 예상등수를 매칭시킨다.

1.3 남는 등수를 정렬한 후, 1~N 사이 남는 등수에 매칭시킨다.

 

이 된다.

 

 

2.

  그런데 사실 더 쉬운 방법이 있다. 어차피 (|A-B|)의 합의 최소값을 구하는 것이므로, 그냥 처음부터 전체를 정렬한 후 1~N에 순서대로 매칭시켜도 '1'과 동일한 답을 구할 수 있다. 어차피 1~N까지로 크기가 제한 되는 이상, '1'의 방식에서 서 4와 6, 5와 8을 서로 바꿔도 서로 더해지고 빼지고 하며 결국 |A-B|의 합은 동일하다.

 

  '2'의 방법을 정리하면

2.1 N을 입력받는다.

2.2 전체를 정렬한다.

2.3 그대로 매칭시킨다.

 

 

이하 코드는 '1'과 '2'의 방식으로 각각 짠 코드이다.

 

 

 

[ 설명 '1'의 방식으로 등수 매칭시키는 코드 (github) ]

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        boolean[] arr = new boolean[n+1];
        ArrayList<Integer> remain = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int cur = nextInt();

            if (cur > n || arr[cur]) remain.add(cur);
            else arr[cur] = true;
        }
        Collections.sort(remain);

        int remainIdx = 0;
        long sum = 0;
        for (int i = 1; i <= n && remainIdx != remain.size(); i++) {
            if (arr[i]) continue;
            sum += Math.abs(i-remain.get(remainIdx++));
        }
        for (int i = n; remainIdx != remain.size(); i++) {
            sum += Math.abs(i-remain.get(remainIdx++));
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}

 

 

 

[ 설명 '2'의 방식으로 등수 매칭시키는 코드 (github) ]

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++)
            arr[i] = nextInt();
        Arrays.sort(arr);
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += Math.abs(i-arr[i]);
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}