BOJ_2012 등수 매기기

• TOC {:toc}

이 글은 백준 온라인 저지의 2012번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.12 (Python)

import sys
input = sys.stdin.readline

N = int(input())
score = sorted([int(input()) for _ in range(N)])
res = 0

for i in range(N):
    res += abs(score[i] - (i + 1))
print(res)

아이디어 & 풀이

입력을 정렬한 뒤 작은 수부터 작은 등수를 매긴다.

• 모든 경우에 최소 불만도를 유지할 수 있다.
  • 현재 값에서 불만도가 최소가 될 값을 양쪽으로 순회하면서 찾기는 너무 번거롭기 때문에.

정렬한 각 원소를 순회하면서 해당 등수 절댓값을 구해서 더한다.

• 해당 인덱스 + 1 값이 그 원소가 받은 등수이다.

디버그

• 시간초과 났다.
  • input() 대신 sys.stdin.readline()을 사용해서 해결했다.

피드백

• 생각보다 enumerate가 인덱스를 순회하면서 각 원소에 접근하는 것과 속도 차이가 거의 없는 것 같다.
  • 앞으로 훨씬 적극적으로 사용해야겠다.
• sort가 sorted보다 약간 더 빠르고 많이 쓰이는 것 같다.
• 리스트를 만들지 않고 바로 iterator를 sum으로 넣으면 사용 메모리를 줄일 수 있다.

2022.04.06 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function main() {
    let dis = 0;
    grade.forEach((g, i) => {
        dis += Math.abs(g - (i + 1));
    });

    return dis;
}

const [N, ...lines] = input;
const grade = lines.map((n) => parseInt(n)).sort((a, b) => a - b);

console.log(main());

참고 답안

# 풀이 1-1
import sys
input = sys.stdin.readline

N = int(input())
score = [int(input()) for i in range(N)]
# sorted 대신에 sort를 이용한다.
score.sort()
# sum을 이용해서 결과를 바로 출력한다.
print(sum(abs(score[i] - i - 1) for i in range(N)))

# 풀이 1-2
import sys
input = sys.stdin.readline

score = sorted([int(input()) for _ in range(int(input()))])
# enumerate로 N 변수를 사용하지 않을 수 있다.
print(sum(abs(x - (i + 1)) for i, x in enumerate(score)))