[알고리즘] 백준 16678 모독 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 골드5
링크 : https://www.acmicpc.net/problem/16678

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 10만
O(nlogn) 풀이 (정렬): 시간제한 ok
자료형 : 10만*10만 = long형 사용
＊모든 국회의원(10만)이 명예점수 10만을 가질 경우, "제이나"는 각각을 1,2,3,4,5... 로 떨어뜨려야 하므로, 대략 10만＊10만이 필요

풀이

1. InputData를 입력받는다.
2. 오름차순으로 정렬한다.
3. 첫번째 데이터가 1이 아니라면, 첫번째 데이터를 1로 만들고, 그 차이를 sum("제이나"가 해킹해야 하는 횟수)에 더한다.
4. 두번째 데이터 ~ 마지막 데이터까지 for문을 돌리면서, i번째 데이터가 i-1번째 데이터보다 클 경우, 그 차이만큼을 sum에 더하고, 해당 데이터를 i-1번째 데이터 + 1로 변경한다.

만약 명예 점수가 3 2 7 6 7 이라면, 2. (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.를 수행하기 위해, 최소한 한명의 점수를 1로 만들어야한다. 그러기 위해 2. 오름차순으로 정렬한다. 그러면 Input Data는 2 3 6 7 7이 될 것이다.
이후에, 첫 번째 사람을 1로 만들고, 이후에는 이전 사람과 같거나 1만큼만 높으면 연쇄적으로 상쇄된다. 만약 이전 사람과 같으면 작업을 수행할 필요가 없고, 이전 사람보다 크다면 1만큼만 차이나도록 하는 것이 최선의 방법이다.

코드

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = stoi(br.readLine());
		long sum = 0;
		int[] arr = new int[n];
		for(int i = 0; i < n; i++)
			arr[i] = stoi(br.readLine());
		//2. 오름차순으로 정렬한다.
		Arrays.sort(arr);
		//3. 첫번째 데이터가 1이 아니라면, 첫번째 데이터를 1로 만들고,
		//   그 차이를 sum("제이나"가 해킹해야 하는 횟수)에 더한다.
		if(arr[0] != 1) {
			sum += (arr[0] - 1);
			arr[0] = 1;
		}
		//4. 두번째 데이터 ~ 마지막 데이터까지 for문을 돌리면서,
		//   i번째 데이터가 i-1번째 데이터보다 클 경우, 그 차이만큼을 sum에 더하고,
		//   해당 데이터를 i-1번째 데이터 + 1로 변경한다.
		for(int i = 1; i < n; i++) {
			if(arr[i] > arr[i-1]) {
				sum += arr[i] - (arr[i-1] + 1);
				arr[i] = arr[i-1]+1;
				
			}				
		}
		System.out.println(sum);
		br.close();
	}
	public static int stoi(String str) {return Integer.parseInt(str);}

}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.