https://www.acmicpc.net/problem/2012
2012번: 등수 매기기
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.
www.acmicpc.net
문제
코드
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 = Integer.parseInt(br.readLine());
ArrayList<Integer>a = new ArrayList<>(n);
for(int i=0;i<n;i++) {
a.add(Integer.parseInt(br.readLine()));
}
Collections.sort(a);
long result=0;
int rank=1;
for(int i=0;i<n;i++) {
result += Math.abs(a.get(i) - (rank++));
}
System.out.println(result);
}
}
해결방법
1 5 3 1 2 예상 등수
1 1 2 3 5 예상 등수 (정렬)
1 2 3 4 5 실제 등수
0 1 1 1 0 불만도
단순히 예상 등수를 오름차순 정렬하여 반복문을 돌려 불만도를 구하면 되는 쉬운 문제이다. 하지만 "틀렸습니다."가 떴다.
반례를 찾으려고 생각을 계속 해봤는데 결국 찾지 못했다.
틀린 이유는 아래와 같이 최악의 해가 들어왔을 때 불만도(result)가 int형 범위를 넘을 수 있기 때문이었다.
input
n = 500,000
a[i] = {1, 1, ..., 1}
result = 0 + 1 + 2 + ... + 499,999
고로 불만도의 타입을 long형으로 바꿔야 했다.
타입을 잘 생각하자..
'알고리즘 > 백준' 카테고리의 다른 글
11279번 : 최대 힙 (0) | 2022.07.28 |
---|---|
18870번 : 좌표 압축 (0) | 2022.07.27 |
2839번 : 설탕 배달 (0) | 2022.07.24 |
18310번 : 안테나 (0) | 2022.07.23 |
10815번 : 숫자 카드 (0) | 2022.07.20 |