2012번 - 등수 매기기

1. 등수 매기기

• 난이도
  • 실버 3
• 시간 제한
  • 2초
• 메모리 제한
  • 256MB
• 출처
  • 2012번: 등수 매기기 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패 - 문제를 잘못 이해함)

def rank():
    answer = 0

    for i in range(1, len(counting_sort)):
        if counting_sort[i] != 1:
            if counting_sort[i] >= 2:
                # 현재 순위 * 순위변경이 필요한 인원 수
                answer += i * (counting_sort[i] - 1)
            elif counting_sort[i] == 0:
                answer -= i

    if answer < 0:
        return -answer
    elif answer >= 0:
        return answer

if __name__ == "__main__":
    n = int(input())
    counting_sort = [0] * (n+1)

    for _ in range(n):
        temp = int(input())
        counting_sort[temp] += 1

    print(rank())

b. 😅 2차 시도 (실패 - 계수 정렬로 풀었으나 실패)

def rank(counting_sort):
    """
    인덱스 에러
    :param counting_sort:
    :return:
    """
    real_rank = []
    predict_rank = []
    answer = 0
    count = 0

    for i in range(1, len(counting_sort)):
        if counting_sort[i] != 1:
            if counting_sort[i] >= 2:
                predict_rank.extend([i] * (counting_sort[i] - 1))
            elif counting_sort[i] == 0:
                real_rank.append(i)
                count += 1

    for i in range(count):
        temp = predict_rank[i] - real_rank[i]
        answer += abs(temp)

    return answer

if __name__ == "__main__":
    n = int(input())
    @@ -30,4 +39,4 @@ def rank():
        temp = int(input())
        counting_sort[temp] += 1

    print(rank(counting_sort))

c. 😊 3차 시도 (성공 - 계수정렬로 풀었다)

def rank(counting_sort):
    """
    인덱스 에러 해결
    :param counting_sort:
    :return:
    """
    global n

    real_rank = []
    predict_rank = []
    answer = 0

    for i in range(1, len(counting_sort)):
        # if counting_sort[i] != 1:
        if counting_sort[i] >= 1 and i > n:
            predict_rank.extend([i] * counting_sort[i])
        elif counting_sort[i] >= 2:
            predict_rank.extend([i] * (counting_sort[i] - 1))
        elif counting_sort[i] == 0:
            real_rank.append(i)

    for i in range(len(predict_rank)):
        temp = predict_rank[i] - real_rank[i]
        answer += abs(temp)

    return answer

if __name__ == "__main__":
    n = int(input())
    counting_sort = [-1] * (500001)

    array = []

    for i in range(1, n+1):
        temp = int(input())
        array.append(temp)
        counting_sort[temp] = 0
        counting_sort[i] = 0

    for a in array:
        counting_sort[a] += 1

    print(rank(counting_sort))

d. 😊 4차 시도 (성공 - 다른 사람의 풀이)

n = int(input())
array = []

for i in range(n):
    array.append(int(input()))

array.sort()
answer = 0

for i in range(1, n+1):
    if i != array[i-1]:
        answer += abs(array[i-1] - i)

print(answer) 

a. 🙄 회고

내 풀이

• 처음에는 계수정렬로 접근했다.

반성

• 문제의 조건이 잘못주어질 수도 있다는 것을 명심하자...

결론

• 문제가 이상해..

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

문제에 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.라고 적혀있어서 입력값의 크기가 N을 벗어나지 않을 것이라 생각했다.

하지만 그렇지 않았다.

그래서 계수 정렬을 50만개 할당하고 (1~N까지, 입력받은 수들)을 0으로 초기화하고 입력받은 수들의 개수를 카운트하였다.

그리고 조건에 맞게 predict과 real을 추출하여 계산하였다.

참고문헌

baekjoon. 2012번: 등수 매기기 (acmicpc.net). Baekjoon. (accessed Dec 14, 2021)