[백준 16678] 모독

포인터를 두개 놓고 국회의원의 명예 점수가 비어있을때의 경우를 체크해주어야 한다.

 

 

예시를 보자.

1	2	3	4	5	6	7
0	1	1	1	0	1	1

 

국회의원은 5명이고 모독한번으로 모두 박탈시키려면 점수가 1, 2, 3, 4, 5 가 되어야 한다.

먼저, 포인터를 left, right로 두고 left의 초기값은 무조건 1이다.

right의 초기값은 국회의원의 명예점수중 최소값이다. 따라서 left=1, right=2가 된다.

 

left 포인터가 가르치는 곳에 명예점수가 비어있다면 right포인터의 명예점수가 채워져 있을때 그 값을 당겨온다.

a[left] = 0, a[right] = 1 이므로 2에서 1을 빼서 1로 당겨오고 그만큼 해커를 고용한다.

 

1	2	3	4	5	6	7
1	0	1	1	0	1	1

 

left 포인터는 2로 넘어왔고 right=2일때 명예점수가 없으므로 포인터는 한칸 움직인다.

이때도 마찬가지로 3의 값을 2로 당겨온다.

 

위 방법으로 시뮬레이션 하면 1, 2, 3, 4, 5 의 값을 채울수 있다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[100001];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            int temp = sc.nextInt();
            min = Math.min(min, temp);
            max = Math.max(max, temp);
            a[temp]++;
        }
        
        int left = 1;
        int right = min;
        long cnt = 0;
        while(right <= max) {
            if(a[left] > 0) {
                left++;
                if(left > right)
                    right++;
            } else {
                if(a[right] == 0)
                    right++;
                else {
                    a[right]--;
                    a[left]++;
                    cnt += right - left;
                }
            }
        }
        System.out.println(cnt);
    }
}