[백준] 1205번 등수 구하기

park geonwoo·2024년 10월 24일

Effective Java

목록 보기

22/56

https://www.acmicpc.net/problem/1205

이번 문제는 디제이맥스(DJMAX) 게임의 랭킹 리스트에 새로운 점수를 추가할 때, 그 점수가 랭킹 리스트에서 몇 등인지 결정하는 문제입니다. 주어진 랭킹 리스트는 비오름차순(내림차순으로 정렬)으로 정렬되어 있으며, 동일한 점수가 있을 경우 가장 작은 등수를 공유합니다. 새로운 점수가 랭킹 리스트에 들어갈 수 있는지 여부를 판단하고, 들어갈 수 있다면 그 등수를 출력하며, 들어갈 수 없을 경우 -1을 출력합니다.

문제 이해

문제 요약

목표:
- 현재 랭킹 리스트에 있는 점수와 새로운 점수가 주어질 때, 새로운 점수가 랭킹 리스트에서 몇 등인지 구합니다.
- 랭킹 리스트가 꽉 찬 경우(점수 개수 N이 최대 랭킹 리스트 크기 P와 같은 경우), 새로운 점수가 마지막 점수보다 클 때만 리스트에 추가할 수 있습니다.
- 동일한 점수가 있을 경우, 해당 점수의 첫 번째 등수를 공유합니다.
- 랭킹 리스트가 꽉 찬 상태에서 새로운 점수가 추가되면, 가장 마지막 점수를 제거합니다.
- 만약 새로운 점수가 랭킹 리스트에 들어갈 수 없으면 1을 출력합니다.
입력:
- 첫 번째 줄: 현재 랭킹 리스트의 점수 개수 N, 새로운 점수 new_score, 랭킹 리스트의 최대 크기 P가 주어집니다.
  - 조건: 10 ≤ P ≤ 50, 0 ≤ N ≤ P
- 두 번째 줄: 현재 랭킹 리스트에 있는 N개의 점수가 비오름차순으로 주어집니다. (N > 0인 경우에만)
  - 각 점수는 0 ≤ score ≤ 2,000,000,000

예제 분석

예제 입력 1:

3 90 10
100 90 80

예제 출력 1:

해석:

현재 랭킹 리스트: [100, 90, 80]
새로운 점수: 90
랭킹 리스트 크기 P=10이므로, 새로운 점수를 추가할 수 있습니다.
새로운 점수를 리스트에 추가하면: [100, 90, 90, 80]
새로운 점수 90은 두 번째 위치에 삽입되므로, 등수는 2입니다.

예제 입력 2:

10 1 10
10 9 8 7 6 5 4 3 2 1

예제 출력 2:

-1

해석:

현재 랭킹 리스트: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
새로운 점수: 1
랭킹 리스트가 이미 꽉 찼으며, 새로운 점수 1은 마지막 점수 1과 같으므로 추가할 수 없습니다.
따라서, 출력은 1입니다.

예제 입력 3:

10 1 10
10 9 8 7 6 5 4 3 3 0

예제 출력 3:

해석:

현재 랭킹 리스트: [10, 9, 8, 7, 6, 5, 4, 3, 3, 0]
새로운 점수: 1
랭킹 리스트가 꽉 찼지만, 새로운 점수 1은 마지막 점수 0보다 크므로 추가할 수 있습니다.
새로운 점수를 추가하면: [10, 9, 8, 7, 6, 5, 4, 3, 3, 1]
새로운 점수 1은 마지막 위치에 삽입되므로, 등수는 10입니다.

예제 입력 4:

0 0 50

예제 출력 4:

해석:

현재 랭킹 리스트가 비어 있습니다.
새로운 점수 0을 추가하면, 리스트는 [0]이 되며, 등수는 1입니다.

해결 방법

이 문제는 새로운 점수를 랭킹 리스트에 추가할 수 있는지 판단하고, 추가할 수 있다면 그 점수가 몇 등인지 계산하는 문제입니다. 이를 효율적으로 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

입력 처리:
- 현재 랭킹 리스트의 점수 개수 N, 새로운 점수 new_score, 랭킹 리스트의 최대 크기 P를 입력받습니다.
- 현재 랭킹 리스트에 있는 N개의 점수를 비오름차순으로 입력받습니다.
랭킹 리스트에 새로운 점수 추가 가능 여부 판단:
- 랭킹 리스트가 비어 있는 경우 (N=0):
  - 새로운 점수를 추가할 수 있으며, 등수는 1입니다.
- 랭킹 리스트가 꽉 차지 않은 경우 (N < P):
  - 새로운 점수를 랭킹 리스트에 추가할 수 있습니다.
  - 새로운 점수가 랭킹 리스트 내에서 몇 등인지 계산합니다.
- 랭킹 리스트가 꽉 찬 경우 (N = P):
  - 새로운 점수가 현재 랭킹 리스트의 마지막 점수보다 클 경우에만 추가할 수 있습니다.
  - 그렇지 않으면, 새로운 점수를 추가할 수 없으므로 1을 출력합니다.
등수 계산:
- 새로운 점수를 랭킹 리스트에 추가할 수 있는 경우, 그 점수가 리스트 내에서 몇 등인지 결정합니다.
- 동일한 점수가 여러 개 있을 경우, 해당 점수의 첫 번째 등수를 사용합니다.

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다.

import sys

def main():
    import sys
    input = sys.stdin.readline

    # 첫 번째 줄: N, new_score, P
    first_line = ''
    while first_line.strip() == '':
        first_line = input()
    parts = first_line.strip().split()
    N = int(parts[0])
    new_score = int(parts[1])
    P = int(parts[2])

    # 두 번째 줄: N개의 점수 (비오름차순), N >0인 경우에만
    scores = []
    if N > 0:
        second_line = ''
        while len(scores) < N:
            second_line = input()
            if not second_line:
                break
            parts = second_line.strip().split()
            scores += list(map(int, parts))
        # Ensure we have exactly N scores
        scores = scores[:N]

    # 함수: 새로운 점수의 등수를 찾는 함수
    def find_rank(scores, new_score):
        for i, score in enumerate(scores):
            if new_score > score:
                return i + 1
            elif new_score == score:
                return i + 1
        return len(scores) + 1

    # 랭킹 리스트가 꽉 차지 않은 경우
    if N < P:
        # 랭킹 리스트에 새로운 점수를 추가
        # Find the rank
        rank = find_rank(scores, new_score)
        print(rank)
    else:
        # 랭킹 리스트가 꽉 찬 경우
        # Check if new_score > last score
        if new_score > scores[-1]:
            # Insert the new_score and remove the last score
            # Find the rank
            rank = find_rank(scores, new_score)
            print(rank)
        else:
            # 새로운 점수를 추가할 수 없음
            print(-1)

if __name__ == "__main__":
    main()

코드 분석

1. 입력 처리

# 첫 번째 줄: N, new_score, P
first_line = ''
while first_line.strip() == '':
    first_line = input()
parts = first_line.strip().split()
N = int(parts[0])
new_score = int(parts[1])
P = int(parts[2])

# 두 번째 줄: N개의 점수 (비오름차순), N >0인 경우에만
scores = []
if N > 0:
    second_line = ''
    while len(scores) < N:
        second_line = input()
        if not second_line:
            break
        parts = second_line.strip().split()
        scores += list(map(int, parts))
    # Ensure we have exactly N scores
    scores = scores[:N]

설명:
- 첫 번째 줄에서 현재 랭킹 리스트의 점수 개수 N, 새로운 점수 new_score, 랭킹 리스트의 최대 크기 P를 입력받습니다.
- 두 번째 줄부터 N개의 점수를 입력받아 scores 리스트에 저장합니다.
  - 입력이 여러 줄에 걸쳐 주어질 수 있으므로, while 루프를 사용하여 필요한 만큼 반복적으로 입력을 받습니다.
  - scores 리스트가 정확히 N개의 점수를 가지도록 잘라줍니다.

2. 등수 계산 함수

def find_rank(scores, new_score):
    for i, score in enumerate(scores):
        if new_score > score:
            return i + 1
        elif new_score == score:
            return i + 1
    return len(scores) + 1

설명:
- scores 리스트와 new_score를 인자로 받아, 새로운 점수가 리스트 내에서 몇 등인지 계산합니다.
- 리스트를 앞에서부터 순회하면서, new_score가 현재 점수보다 클 경우 그 위치가 새로운 점수의 등수가 됩니다.
- new_score가 현재 점수와 같을 경우, 그 위치가 새로운 점수의 등수가 됩니다.
- 모든 점수를 순회한 후에도 new_score가 가장 낮다면, len(scores) + 1을 반환합니다.

3. 랭킹 리스트에 새로운 점수 추가 가능 여부 판단 및 등수 출력

# 랭킹 리스트가 꽉 차지 않은 경우
if N < P:
    # 랭킹 리스트에 새로운 점수를 추가
    # Find the rank
    rank = find_rank(scores, new_score)
    print(rank)
else:
    # 랭킹 리스트가 꽉 찬 경우
    # Check if new_score > last score
    if new_score > scores[-1]:
        # Insert the new_score and remove the last score
        # Find the rank
        rank = find_rank(scores, new_score)
        print(rank)
    else:
        # 새로운 점수를 추가할 수 없음
        print(-1)

설명:
- 랭킹 리스트가 꽉 차지 않은 경우 (N < P):
  - 새로운 점수를 추가할 수 있으므로, find_rank 함수를 호출하여 새로운 점수의 등수를 계산하고 출력합니다.
- 랭킹 리스트가 꽉 찬 경우 (N = P):
  - 새로운 점수가 현재 랭킹 리스트의 마지막 점수보다 클 경우에만 추가할 수 있습니다.
    - 이 경우, find_rank 함수를 호출하여 새로운 점수의 등수를 계산하고 출력합니다.
  - 그렇지 않으면, 새로운 점수를 추가할 수 없으므로 1을 출력합니다.

4. 전체 코드 실행 예제

예제 입력 1:

3 90 10
100 90 80

실행 과정:

N=3, new_score=90, P=10
scores = [100, 90, 80]
N < P이므로, find_rank(scores, 90) 호출
- i=0, score=100: 90 < 100 → 계속
- i=1, score=90: 90 == 90 → 등수 2 반환
출력: 2

예제 입력 2:

10 1 10
10 9 8 7 6 5 4 3 2 1

실행 과정:

N=10, new_score=1, P=10
scores = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
N == P이므로, new_score=1과 scores[-1]=1 비교
- 1 > 1 → 거짓
출력: 1

예제 입력 3:

10 1 10
10 9 8 7 6 5 4 3 3 0

실행 과정:

N=10, new_score=1, P=10
scores = [10, 9, 8, 7, 6, 5, 4, 3, 3, 0]
N == P이므로, new_score=1과 scores[-1]=0 비교
- 1 > 0 → 참
find_rank(scores, 1) 호출
- i=0, score=10: 1 < 10 → 계속
- i=1, score=9: 1 < 9 → 계속
- i=2, score=8: 1 < 8 → 계속
- i=3, score=7: 1 < 7 → 계속
- i=4, score=6: 1 < 6 → 계속
- i=5, score=5: 1 < 5 → 계속
- i=6, score=4: 1 < 4 → 계속
- i=7, score=3: 1 < 3 → 계속
- i=8, score=3: 1 < 3 → 계속
- i=9, score=0: 1 > 0 → 등수 10 반환
출력: 10

예제 입력 4:

0 0 50

실행 과정:

N=0, new_score=0, P=50
scores = []
N < P이므로, find_rank(scores, 0) 호출
- 리스트가 비어있으므로, len(scores) + 1 = 1 반환
출력: 1

시간 복잡도 및 효율성

시간 복잡도

입력 처리:
- N과 P를 읽는 데 O(1)
- N개의 점수를 읽는 데 O(N)
등수 계산 (find_rank):
- find_rank 함수는 최대 N번 비교를 수행합니다.
- 따라서, O(N)
전체 알고리즘:
- if N < P 조건에서 find_rank 호출 → O(N)
- else 조건에서 find_rank 호출 또는 1 출력 → O(N) 또는 O(1)
- 따라서, 전체 시간 복잡도는 O(N)
- 비고: N의 최대 값은 50이므로, 실제로는 매우 빠르게 동작합니다.

공간 복잡도

점수 리스트 (scores):
- O(N)
기타 변수:
- O(1)
전체 공간 복잡도:
- O(N)
- 비고: N의 최대 값이 50이므로, 공간 사용량은 매우 작습니다.

알고리즘 및 자료구조 설명

알고리즘: 선형 탐색 (Linear Search)

특징:
- 주어진 리스트를 앞에서부터 순차적으로 탐색합니다.
- 특정 조건을 만족하는 첫 번째 요소를 찾으면 탐색을 중단합니다.
이 문제에서의 적용:
- 새로운 점수가 리스트 내에서 몇 등인지 결정하기 위해 리스트를 순차적으로 탐색합니다.
- 동일한 점수가 여러 개 있을 경우, 첫 번째 등수를 반환하여 점수가 같은 모든 위치에서 동일한 등수를 공유하게 합니다.

자료구조: 리스트 (List)

특징:
- 파이썬의 리스트는 순차적으로 데이터를 저장하고, 인덱스를 통해 빠르게 접근할 수 있습니다.
이 문제에서의 적용:
- 현재 랭킹 리스트를 저장하기 위해 리스트를 사용합니다.
- 리스트의 인덱스를 활용하여 새로운 점수의 등수를 계산합니다.

결론

제공된 파이썬 코드는 선형 탐색(Linear Search)을 사용하여, 새로운 점수가 랭킹 리스트 내에서 몇 등인지 효율적으로 계산합니다. 시간 복잡도는 O(N), 공간 복잡도는 O(N)으로, 주어진 문제의 제한 사항 (N ≤ 50) 내에서 매우 효율적으로 동작합니다.

알고리즘: 선형 탐색을 통한 새로운 점수의 등수 결정
자료구조: 리스트(List)를 사용하여 랭킹 리스트 관리
시간 복잡도: O(N)
공간 복잡도: O(N)

이 접근 방식은 랭킹 리스트가 비교적 작고, 리스트 내에서의 순차적인 탐색이 필요한 상황에서 매우 효과적입니다. 또한, 동일한 점수가 있을 때 첫 번째 등수를 공유하는 요구 사항을 간단하게 만족시킬 수 있습니다.

park geonwoo

이전 포스트

Effective Java 4강 ITEM20 추상 클래스 보다는 인터페이스를 우선하라

다음 포스트

[백준] 1205번 등수 구하기

Effective Java

문제 이해

문제 요약

예제 분석

해결 방법

코드 구현

코드 분석

1. 입력 처리

2. 등수 계산 함수

3. 랭킹 리스트에 새로운 점수 추가 가능 여부 판단 및 등수 출력

4. 전체 코드 실행 예제

시간 복잡도 및 효율성

시간 복잡도

공간 복잡도

알고리즘 및 자료구조 설명

알고리즘: 선형 탐색 (Linear Search)

자료구조: 리스트 (List)

결론

Effective Java 4강 ITEM20 추상 클래스 보다는 인터페이스를 우선하라

Effective Java 4강 ITEM21 인터페이스는 구현하는 쪽을 생각해 설계하라

0개의 댓글