공부블로그

TODAY TIL

파이썬으로 점수 순위 매기기 - 쉬운 풀이 가이드

안녕하세요, 이번 블로그 포스트에서는 파이썬을 이용해 점수 배열을 받아 선수들의 순위를 매기는 문제를 해결해보려고 합니다. 점수에 따라 메달을 부여하고 순위를 매기는 알고리즘 문제를 쉽게 이해할 수 있도록 차근차근 설명드릴게요. 이 포스트를 통해 여러분이 코드 작성 과정을 이해하고, 직접 문제를 풀어볼 수 있도록 돕겠습니다!

문제 설명

우리는 각 선수의 점수가 담긴 배열을 받습니다. 이 배열에는 각 선수의 점수가 고유하게 담겨 있으며, 높은 점수가 높은 순위를 의미합니다. 각 선수는 다음과 같은 순위에 따라 메달 또는 순위 번호를 부여받습니다.

• 1등: "Gold Medal"
• 2등: "Silver Medal"
• 3등: "Bronze Medal"
• 4등 이후: 해당 순위 숫자

예를 들어, 입력 배열이 [10, 3, 8, 9, 4]이라면 결과는 ['Gold Medal', '5', 'Bronze Medal', 'Silver Medal', '4']가 되어야 합니다.

해결 방법

이 문제를 해결하기 위해 다음과 같은 단계를 거칠 것입니다.

1. 점수 배열과 인덱스 묶기: 각 점수와 인덱스를 묶어 리스트로 만듭니다. 이렇게 하면 점수를 정렬한 후에도 각 점수가 원래 어디에 있었는지 알 수 있습니다.
2. 점수 정렬하기: 점수들을 높은 순서대로 정렬합니다. 정렬된 순서에서 1등, 2등, 3등을 각각 메달로 처리하고 나머지 순위를 숫자로 기록합니다.
3. 결과 배열 생성: 원래 배열에 맞는 순위를 기록한 결과 배열을 반환합니다.

코드 구현

이제 파이썬 코드로 이 문제를 해결하는 방법을 알아보겠습니다. 코드가 이해하기 쉽게 클래스 형태로 작성되어 있습니다.

class Solution:
    def findRelativeRanks(self, score):
        # 점수 배열과 각 인덱스를 묶어 (점수, 인덱스) 형태로 리스트 생성 후 내림차순 정렬
        sorted_score = sorted(enumerate(score), key=lambda x: x[1], reverse=True)

        # 결과 배열 초기화
        ranks = [""] * len(score)

        # 순위에 따라 메달 혹은 순위 번호를 할당
        for i, (idx, value) in enumerate(sorted_score):
            if i == 0:
                ranks[idx] = "Gold Medal"
            elif i == 1:
                ranks[idx] = "Silver Medal"
            elif i == 2:
                ranks[idx] = "Bronze Medal"
            else:
                ranks[idx] = str(i + 1)

        return ranks

# 예제 입력 테스트
solution = Solution()
score1 = [5, 4, 3, 2, 1]
print(solution.findRelativeRanks(score1))  # 출력: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

score2 = [10, 3, 8, 9, 4]
print(solution.findRelativeRanks(score2))  # 출력: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

코드 설명

• 점수 정렬하기: enumerate(score)를 사용해 점수와 인덱스를 함께 묶은 후, 점수를 기준으로 내림차순 정렬했습니다. 이렇게 하면 각 점수가 원래 어느 위치에 있었는지 알 수 있게 됩니다.
• 결과 배열 생성: 정렬된 점수에 따라 순위를 매기고, 그에 맞는 메달 혹은 순위 숫자를 원래 인덱스 위치에 기록합니다.
• 메달 할당: 1, 2, 3등에 해당하는 선수에게 각각 "Gold Medal", "Silver Medal", "Bronze Medal"을 부여하고, 나머지는 순위 숫자를 할당합니다.

예제 테스트

• 입력: [5, 4, 3, 2, 1]
  • 출력: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
• 입력: [10, 3, 8, 9, 4]
  • 출력: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

마무리

이렇게 해서 점수 배열을 받아 선수들의 순위를 메달 및 숫자로 표현하는 방법을 알아보았습니다. 간단한 정렬과 반복문을 이용해 문제를 해결할 수 있었죠. 이 문제는 파이썬의 정렬 기능과 인덱스 활용을 배울 수 있는 좋은 예제입니다.

여러분도 비슷한 문제를 풀 때 이런 방식으로 접근해 보세요! 질문이나 궁금한 점이 있으면 언제든지 댓글로 남겨주세요.

TODAY TIL

안녕하세요! 오늘은 선물 더미에서 가장 많은 선물을 가져가고 남은 선물을 계산하는 문제를 풀어보겠습니다. 이 문제는 선물 더미 중 가장 큰 값을 선택하고, 해당 더미에서 ⌊제곱근⌋만 남기고 나머지를 가져가는 과정을 k초 동안 반복한 후 남은 선물의 총합을 구하는 문제입니다.

문제 설명

문제

주어진 정수 배열 gifts는 다양한 더미에 있는 선물의 개수를 나타냅니다. 매초마다 가장 많은 선물이 있는 더미를 선택하여 ⌊제곱근⌋만 남겨두고 나머지를 가져갑니다. k초 동안 이 작업을 반복하고 최종적으로 남은 모든 선물의 총합을 반환합니다.

예시

입력

gifts = [25, 64, 9, 4, 100]
k = 4

출력

29

설명

• 첫 번째 초: 100을 선택하여 ⌊√100⌋ = 10을 남김 → [25, 64, 9, 4, 10]
• 두 번째 초: 64를 선택하여 ⌊√64⌋ = 8을 남김 → [25, 8, 9, 4, 10]
• 세 번째 초: 25를 선택하여 ⌊√25⌋ = 5를 남김 → [5, 8, 9, 4, 10]
• 네 번째 초: 10을 선택하여 ⌊√10⌋ = 3을 남김 → [5, 8, 9, 4, 3]
• 최종 남은 선물의 총합: 29

문제 풀이

접근 방법

• gifts 배열을 최대 힙(max heap)으로 변환하여 가장 큰 값을 효율적으로 가져옵니다.
• k번 동안 가장 큰 값의 선물을 가져가고 남은 ⌊제곱근⌋ 값을 다시 힙에 넣습니다.
• heapq 모듈을 활용해 효율적으로 최대값을 찾고, ⌊제곱근⌋을 계산하여 힙을 업데이트합니다.

코드 구현

다음은 문제를 해결하기 위한 Python 코드입니다.

import heapq
import math

def remaining_gifts(gifts, k):
    # 최대 힙으로 변환하기 위해 음수로 저장
    max_heap = [-gift for gift in gifts]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # 가장 큰 값 꺼내기
        max_gift = -heapq.heappop(max_heap)
        # 제곱근을 구해 남은 선물 수 계산
        remaining_gift = math.floor(math.sqrt(max_gift))
        # 남은 선물 다시 힙에 삽입
        heapq.heappush(max_heap, -remaining_gift)
    
    # 남은 선물의 총합 구하기
    return -sum(max_heap)

# 예시 실행
print(remaining_gifts([25, 64, 9, 4, 100], 4))  # 출력: 29
print(remaining_gifts([1, 1, 1, 1], 4))  # 출력: 4

코드 설명

1. gifts 배열을 최대 힙으로 변환합니다. Python의 heapq는 최소 힙만 지원하므로 음수로 값을 넣어 최대 힙처럼 사용합니다.
2. k번 반복하며, 가장 큰 값을 꺼내 ⌊제곱근⌋을 계산한 후 다시 힙에 넣습니다.
3. 모든 작업이 끝난 후 힙에 남은 값들을 합산하여 반환합니다.

시간 복잡도

• 힙을 사용하는 삽입 및 삭제의 시간 복잡도는 O(log n)이며, 이를 k번 반복하므로 전체 시간 복잡도는 O(k log n)입니다.

결론

이 코드는 주어진 문제 조건을 충족하면서 효율적으로 풀 수 있는 방법을 제시합니다. heapq와 math 모듈을 적절히 사용하여 최대값을 찾고 갱신하는 과정을 손쉽게 구현할 수 있습니다.

이 글이 여러분의 문제 해결에 도움이 되었기를 바랍니다. 질문이나 추가적인 설명이 필요하면 댓글로 남겨주세요!

오늘의 공부 키워드

1700. Number of Students Unable to Eat Lunch

1700. Number of Students Unable to Eat Lunch

문제 설명

학교 급식실에서는 점심시간에 원형과 사각형 샌드위치를 제공합니다. 각각 0과 1로 표현됩니다. 모든 학생들은 줄을 서서 각자 원형 또는 사각형 샌드위치를 선호합니다.

샌드위치의 수는 학생들의 수와 같습니다. 샌드위치는 스택에 쌓여 있습니다. 각 단계에서 다음이 이루어집니다:

• 줄의 맨 앞 학생이 스택 맨 위의 샌드위치를 선호하면 샌드위치를 가져가고 줄에서 나갑니다.
• 그렇지 않으면, 샌드위치를 두고 줄의 끝으로 갑니다.

이 과정은 더 이상 줄의 학생들이 스택 맨 위의 샌드위치를 원하지 않아 먹지 못하는 상황이 될 때까지 계속됩니다.

두 개의 정수 배열 students와 sandwiches가 주어집니다. sandwiches[i]는 스택의 i번째 샌드위치의 타입(0이 맨 위)이고, students[j]는 줄의 j번째 학생의 선호도(0이 맨 앞)입니다. 먹지 못하는 학생의 수를 반환하세요.

예제

예제 1

• 입력: students = [1,1,0,0], sandwiches = [0,1,0,1]
• 출력: 0
• 설명:
  1. 맨 앞 학생이 맨 위의 샌드위치를 두고 줄 끝으로 가서 students = [1,0,0,1]이 됩니다.
  2. 맨 앞 학생이 맨 위의 샌드위치를 두고 줄 끝으로 가서 students = [0,0,1,1]이 됩니다.
  3. 맨 앞 학생이 맨 위의 샌드위치를 가져가서 students = [0,1,1]이 되고 sandwiches = [1,0,1]이 됩니다.
  4. 맨 앞 학생이 맨 위의 샌드위치를 두고 줄 끝으로 가서 students = [1,1,0]이 됩니다.
  5. 맨 앞 학생이 맨 위의 샌드위치를 가져가서 students = [1,0]이 되고 sandwiches = [0,1]이 됩니다.
  6. 맨 앞 학생이 맨 위의 샌드위치를 두고 줄 끝으로 가서 students = [0,1]이 됩니다.
  7. 맨 앞 학생이 맨 위의 샌드위치를 가져가서 students = [1]이 되고 sandwiches = [1]이 됩니다.
  8. 맨 앞 학생이 맨 위의 샌드위치를 가져가서 students = []이 되고 sandwiches = []이 됩니다.
  9. 따라서 모든 학생들이 샌드위치를 먹을 수 있습니다.

예제 2

• 입력: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
• 출력: 3

해결책

이 문제를 해결하기 위해서 다음 단계를 따라갈 수 있습니다:

1. 각 샌드위치 타입의 수와 학생들의 선호도를 셉니다.
2. 학생들이 줄을 돌면서 샌드위치를 가져가거나 줄 끝으로 가는 과정을 시뮬레이션합니다.
3. 만약 더 이상 어떤 학생도 맨 위의 샌드위치를 원하지 않으면, 남은 학생 수를 반환합니다.

코드

def count_students_unable_to_eat(students, sandwiches):
    count0 = students.count(0)
    count1 = students.count(1)
    
    for sandwich in sandwiches:
        if sandwich == 0 and count0 > 0:
            count0 -= 1
        elif sandwich == 1 and count1 > 0:
            count1 -= 1
        else:
            break
            
    return count0 + count1

# 예제 입력
students1 = [1, 1, 0, 0]
sandwiches1 = [0, 1, 0, 1]

students2 = [1, 1, 1, 0, 0, 1]
sandwiches2 = [1, 0, 0, 0, 1, 1]

# 출력
print(count_students_unable_to_eat(students1, sandwiches1))  # 출력: 0
print(count_students_unable_to_eat(students2, sandwiches2))  # 출력: 3