코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍

코딩기록

알고리즘/백준

2012번 : 등수 매기기

2022. 7. 26. 13:52

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
    '알고리즘/백준' 카테고리의 다른 글
    • 11279번 : 최대 힙
    • 18870번 : 좌표 압축
    • 2839번 : 설탕 배달
    • 18310번 : 안테나
    코딍코딍
    코딍코딍
    ㅎ2

    티스토리툴바