공부블로그

TODAY TIL

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 일정 기준 이상으로 만들고 싶어합니다. 이 문제를 해결하기 위해 Python에서 **우선순위 큐(Priority Queue)**를 사용하여 효율적으로 푸는 방법을 소개합니다.

문제 설명

Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 아래의 규칙을 사용해 음식을 섞습니다:

1. 스코빌 지수가 가장 낮은 두 개의 음식을 선택합니다.
2. 이 두 음식을 섞어 새로운 음식의 스코빌 지수를 계산합니다: 섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)\text{섞은 음식의 스코빌 지수} = \text{가장 낮은 스코빌 지수} + (\text{두 번째로 낮은 스코빌 지수} \times 2)섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)
3. 모든 음식의 스코빌 지수가 K 이상이 될 때까지 위 과정을 반복합니다.

입력 조건:

• scoville: 각 음식의 스코빌 지수가 담긴 배열 (길이: 2 이상 1,000,000 이하).
• K: 목표 스코빌 지수 (0 이상 1,000,000,000 이하).

출력 조건:

• 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환합니다.
• 불가능한 경우 -1을 반환합니다.

문제 해결 접근법

이 문제는 최소값과 두 번째 최소값을 반복적으로 선택하는 작업이 필요하므로, **우선순위 큐(Priority Queue)**를 사용하는 것이 효율적입니다. Python에서는 heapq 모듈을 사용해 이를 간단히 구현할 수 있습니다.

풀이 과정

1. 힙으로 변환
   • heapq.heapify()를 사용해 입력 배열을 최소 힙으로 변환합니다.
   • 힙 구조를 사용하면 최소값을 빠르게 추출할 수 있습니다.
2. 반복 작업
   • 가장 작은 두 값을 추출하여 새로운 값을 계산합니다.
   • 계산된 값을 다시 힙에 삽입하고, 섞은 횟수를 증가시킵니다.
3. 종료 조건
   • 힙에서 가장 작은 값이 K 이상이면 작업을 종료하고 섞은 횟수를 반환합니다.
   • 힙에 하나의 값만 남았는데도 K 이상이 되지 않으면 불가능하므로 -1을 반환합니다.

Python 코드

import heapq

def solution(scoville, K):
    # 1. 배열을 최소 힙으로 변환
    heapq.heapify(scoville)
    mix_count = 0

    # 2. 반복적으로 가장 작은 두 값을 섞음
    while len(scoville) > 1:
        # 최소 두 개 값을 꺼내 섞기
        first = heapq.heappop(scoville)  # 가장 작은 값
        if first >= K:
            return mix_count  # 모든 값이 K 이상이므로 종료
        second = heapq.heappop(scoville)  # 두 번째로 작은 값
        new_scoville = first + (second * 2)
        heapq.heappush(scoville, new_scoville)  # 섞은 값 삽입
        mix_count += 1

    # 3. 힙에 하나만 남은 경우 확인
    if scoville[0] >= K:
        return mix_count
    else:
        return -1  # 모든 값을 K 이상으로 만들 수 없는 경우

예제 실행

입력

scoville = [1, 2, 3, 9, 10, 12]
K = 7

실행 과정

1. 초기 힙 구성: [1, 2, 3, 9, 10, 12]
2. 첫 번째 섞기:
   • 선택: 1, 2
   • 새 값: 1 + (2 * 2) = 5
   • 힙 상태: [3, 5, 9, 10, 12]
   • 섞은 횟수: 1
3. 두 번째 섞기:
   • 선택: 3, 5
   • 새 값: 3 + (5 * 2) = 13
   • 힙 상태: [9, 10, 12, 13]
   • 섞은 횟수: 2
4. 세 번째 섞기:
   • 선택: 9, 10
   • 새 값: 9 + (10 * 2) = 29
   • 힙 상태: [12, 13, 29]
   • 섞은 횟수: 3
5. 종료 조건 확인: 힙의 최솟값이 12로 K 이상이므로 종료.

출력

solution(scoville, K)  # 결과: 3

결과 및 시간 복잡도 분석

1. 결과: 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 최소 3번 섞어야 합니다.
2. 시간 복잡도:
   • 힙 연산(삽입, 삭제)의 시간 복잡도: O(log⁡N)O(\log N)O(logN)
   • 최대 N번 반복하므로 총 시간 복잡도: O(Nlog⁡N)O(N \log N)O(NlogN)

핵심 포인트 정리

• 힙 사용의 효율성: 최소값과 두 번째 최소값을 빠르게 추출하고 삽입.
• 종료 조건의 이해: 모든 값이 K 이상이 되는 순간 종료.
• 예외 처리: 모든 값을 K 이상으로 만들 수 없는 경우 -1 반환.

이 풀이를 통해 효율적인 문제 해결 방법과 Python에서 힙을 사용하는 기법을 배울 수 있었습니다. Leo의 매운맛 도전, 이제 여러분도 성공시켜 보세요! 🔥

TODAY TIL

다솜이는 사람의 마음을 읽는 기계를 이용해 국회의원 선거에서 자신을 찍지 않을 사람들을 매수하려고 합니다. 목표는 다른 후보들의 득표수를 초과하는 것입니다. 이 글에서는 다솜이가 최소 몇 명을 매수해야 당선될 수 있는지를 계산하는 방법을 설명합니다.

문제 설명

1. 입력 조건:
   • 후보 수 NNN이 주어집니다.
   • 각 후보의 득표수가 순서대로 입력됩니다.
   • 기호 1번 후보가 다솜이입니다.
2. 출력 조건:
   • 다솜이가 매수해야 하는 사람의 최소 수를 출력합니다.
3. 제약 조건:
   • 후보 수 NNN: 최대 50
   • 각 후보의 득표수: 최대 100
4. 예제 입력/출력

입력:

3
5
7
7

출력:

2

해결 방법

문제를 해결하기 위해 다음과 같은 단계로 접근합니다:

1. 입력 데이터를 읽기:
   • 후보 수와 각 후보의 득표수를 리스트로 저장합니다.
   • 다솜이의 득표수는 따로 저장하고, 나머지 후보들의 득표수를 관리합니다.
2. 매수 작업 반복:
   • 다른 후보들의 득표수를 내림차순으로 정렬합니다.
   • 가장 많은 득표수를 가진 후보를 매수하여 다솜이의 득표수를 증가시킵니다.
   • 다솜이의 득표수가 다른 모든 후보보다 많아질 때까지 이 작업을 반복합니다.
3. 매수 횟수 계산:
   • 매수 횟수를 카운트하면서, 다솜이의 득표수가 다른 후보들보다 많아질 때 결과를 출력합니다.

Python 코드

# 입력받기
N = int(input())  # 후보 수
votes = [int(input()) for _ in range(N)]  # 각 후보의 득표수

# 초기 설정
dasom_votes = votes[0]  # 다솜이의 득표수
other_votes = votes[1:]  # 다른 후보들의 득표수
bribes = 0  # 매수한 사람 수

# 매수 작업
while other_votes and max(other_votes) >= dasom_votes:
    # 가장 많은 득표수를 가진 후보의 표를 매수
    max_index = other_votes.index(max(other_votes))  # 최대값의 인덱스 찾기
    other_votes[max_index] -= 1  # 표 매수 (1 감소)
    dasom_votes += 1  # 다솜이의 표 증가
    bribes += 1  # 매수 횟수 증가

# 결과 출력
print(bribes)

코드 설명

1. 입력 처리:
   • 후보 수 NNN과 각 후보의 득표수를 입력받아 리스트로 저장합니다.
   • 다솜이의 득표수는 dasom_votes에, 나머지 후보들의 득표수는 other_votes 리스트로 관리합니다.
2. 매수 작업:
   • while 루프를 통해 다솜이의 득표수가 다른 후보들의 최대 득표수를 초과할 때까지 반복합니다.
   • 가장 많은 득표수를 가진 후보의 표를 하나 매수하고, 다솜이의 득표수를 증가시킵니다.
3. 결과 출력:
   • 매수 횟수는 bribes 변수에 저장되며, 반복이 끝나면 최솟값이 출력됩니다.

예제 실행

입력

3
5
7
7

출력

2

추가 설명

이 코드의 핵심은 다솜이의 득표수가 다른 후보들보다 많아질 때까지 반복적으로 매수하는 것입니다. 가장 득표수가 많은 후보를 우선 매수하는 전략을 사용하여 최솟값을 계산합니다.

최적화 고려사항

• 후보 수 NNN이 최대 50이므로, 매수 작업의 복잡도는 적절한 수준입니다.
• max\text{max}max 연산을 사용하는 만큼, 리스트 길이에 따라 작업 시간이 영향을 받을 수 있습니다.

마무리

이 문제는 그리디 알고리즘을 활용하여 반복적으로 최대값을 줄이는 전략을 사용합니다. 매수 전략을 효율적으로 구현하여 다솜이가 국회의원에 당선되도록 만드는 과정을 함께 배웠습니다.

코드와 예제 실행 결과를 참고하여 자신만의 해결 방법을 구현해 보세요! 😊

TODAY TIL

안녕하세요 오늘은 grid라는 2차원 배열에서 각 행의 최대 값을 제거하고, 그 값들 중 가장 큰 값을 누적하여 최종 결과를 반환하는 문제를 다루어 보겠습니다. 문제를 단계별로 설명하고, Python 코드와 풀이 과정을 함께 살펴보겠습니다.

문제 설명

주어진 grid는 다음과 같은 2차원 리스트입니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

이제 각 반복 단계마다 각 행의 최대 값을 제거한 후, 그 값들 중 가장 큰 값을 누적해 나가는 과정을 반복해야 합니다. grid의 모든 행이 비어 있을 때까지 이 작업을 수행한 후 누적된 값을 반환합니다.

풀이 순서

1. answer라는 변수를 초기화하여 결과를 저장합니다.
2. grid[0]이 비어있지 않을 동안 반복문을 실행합니다.
3. 각 행(row)에서 max() 함수를 사용해 가장 큰 값을 찾습니다.
4. 찾은 값을 max_vals 리스트에 추가하고, 해당 값을 해당 행에서 제거합니다.
5. max_vals 리스트에서 가장 큰 값을 찾아 answer에 더합니다.
6. 모든 행이 비어있으면 반복문을 종료하고, 최종 answer를 반환합니다.

코드 설명

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

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        answer = 0  # 결과를 저장할 변수 초기화
        # grid[0]이 비어있지 않을 동안 반복
        while grid[0]:
            max_vals = []  # 각 행에서 찾은 최대 값을 저장할 리스트
            for row in grid:
                max_val = max(row)  # 각 행에서 최대 값을 찾음
                max_vals.append(max_val)  # 최대 값을 리스트에 추가
                row.remove(max_val)  # 행에서 최대 값을 제거
            answer += max(max_vals)  # 최대 값들 중에서 가장 큰 값을 answer에 더함
        return answer  # 최종 결과 반환

단계별 예제

입력 예제

grid가 다음과 같다고 가정합니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

실행 단계 설명

1. 첫 번째 반복:
   • 각 행에서 최대 값을 찾습니다: [3, 6, 9]
   • 가장 큰 값은 9이며, answer는 9가 됩니다.
   • 업데이트된 grid:
      

grid = [
    [1, 2],
    [4, 5],
    [8, 7]
]

두 번째 반복:

• 각 행에서 최대 값을 찾습니다: [2, 5, 8]
• 가장 큰 값은 8이며, answer는 9 + 8 = 17이 됩니다.
• 업데이트된 grid:
   

grid = [
    [1],
    [4],
    [7]
]

세 번째 반복:

• 각 행에서 최대 값을 찾습니다: [1, 4, 7]
• 가장 큰 값은 7이며, answer는 17 + 7 = 24가 됩니다.
• 업데이트된 grid는 비어 있습니다:
   

grid = [
    [],
    [],
    []
]

최종 결과

모든 행이 비어 있으므로 반복을 종료하고, answer는 24입니다.

시간 복잡도 분석

• 각 행에서 최대 값을 찾는 작업은 O(n)O(n)O(n)이며, 이를 mmm개의 행에 대해 수행하므로 시간 복잡도는 O(m×n)O(m \times n)O(m×n)입니다.
• m은 행의 수, n은 열의 수입니다.

결론

이 문제는 반복문과 리스트 연산을 활용해 각 행의 최대 값을 계속 제거하면서 누적 합을 구하는 문제입니다. 문제의 핵심은 각 반복마다 각 행의 최대 값을 효율적으로 찾고 제거하는 것입니다.

이 코드와 풀이가 여러분의 이해에 도움이 되었기를 바랍니다. 궁금한 점이나 다른 해석이 있다면 댓글로 남겨주세요!

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 모듈을 적절히 사용하여 최대값을 찾고 갱신하는 과정을 손쉽게 구현할 수 있습니다.

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

TODAY TIL

안녕하세요, 오늘은 재미있는 코딩 문제를 함께 풀어보겠습니다. 이 문제는 센티라는 캐릭터가 마법의 뿅망치를 사용하여 자신보다 키가 큰 거인들을 줄여야 하는 상황입니다. 어떤 전략을 세우고 어떻게 코드를 구현했는지 차근차근 설명하겠습니다.

문제 설명

센티는 여행 중 거인의 나라에 도착했습니다. 그곳에는 자신보다 키가 크거나 같은 거인들이 많았는데, 센티는 이들을 마법의 뿅망치를 이용해 키를 줄이려 합니다. 마법의 뿅망치에 맞으면 키는 ⌊현재 키 / 2⌋로 줄어듭니다. 단, 키가 1이면 더 이상 줄어들지 않습니다. 이 마법의 뿅망치는 사용 횟수 제한이 있습니다.

목표: 센티가 마법의 뿅망치를 전략적으로 사용해 모든 거인이 센티보다 키가 작아지게 할 수 있는지를 판단하고, 그 과정에서 최소 사용 횟수를 출력합니다.

입력 형식

• 첫 번째 줄에 거인의 수 N, 센티의 키 HcentiH_{\text{centi}}Hcenti​, 마법의 뿅망치 사용 제한 T가 주어집니다.
• 두 번째 줄부터 N개의 줄에 각 거인의 키가 주어집니다.

출력 형식

• 마법의 뿅망치를 사용하여 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작다면 "YES"와 사용한 횟수를 출력합니다.
• 그렇지 않다면 "NO"와 뿅망치 사용 후 가장 큰 거인의 키를 출력합니다.

문제 풀이 접근법

1. 최대 힙을 이용한 거인 선택:
   • 거인들 중 가장 키가 큰 거인을 빠르게 선택하기 위해 최대 힙을 사용합니다.
   • Python의 heapq 모듈은 기본적으로 최소 힙이므로, 음수로 변환하여 최대 힙처럼 사용합니다.
2. 마법의 뿅망치 사용 전략:
   • 가장 키가 큰 거인을 때리고 줄어든 키를 다시 최대 힙에 넣습니다.
   • 키가 1인 경우는 줄일 수 없으므로 무시합니다.
   • 제한된 사용 횟수 T를 초과하지 않도록 합니다.
3. 결과 판단:
   • 마법의 뿅망치를 사용한 후, 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작으면 성공이고, 그렇지 않다면 실패입니다.

코드 구현

import heapq

# 입력 처리
N, H_centi, T = map(int, input().split())
giants = []

for _ in range(N):
    height = int(input())
    heapq.heappush(giants, -height)  # 최대 힙을 위해 음수로 저장

# 마법의 뿅망치 사용 횟수 카운트
use_count = 0

# 뿅망치 사용
while use_count < T and -giants[0] >= H_centi:
    tallest = -heapq.heappop(giants)
    
    if tallest == 1:
        # 키가 1이면 더 이상 줄어들 수 없음
        heapq.heappush(giants, -tallest)
        break
    
    # 뿅망치를 사용하여 키 줄이기
    new_height = tallest // 2
    heapq.heappush(giants, -new_height)
    use_count += 1

# 결과 확인
if -giants[0] < H_centi:
    print("YES")
    print(use_count)
else:
    print("NO")
    print(-giants[0])

코드 설명

1. 입력 처리:
   • 첫 번째 줄에서 거인의 수, 센티의 키, 마법의 뿅망치 사용 제한을 읽어옵니다.
   • 각 거인의 키를 음수로 변환하여 최대 힙에 저장합니다.
2. 반복문:
   • 최대 TTT번의 반복 동안 가장 키가 큰 거인을 선택하여 키를 절반으로 줄입니다.
   • 줄어든 키는 다시 힙에 삽입하여 다음 최댓값을 구할 수 있도록 합니다.
   • 키가 1인 거인은 더 이상 줄일 수 없으므로 바로 종료합니다.
3. 출력:
   • 모든 거인의 키가 센티보다 작아졌다면 YES와 사용 횟수를 출력합니다.
   • 그렇지 않다면 NO와 가장 큰 거인의 키를 출력합니다.

시간 및 공간 복잡도

• 시간 복잡도: O((T+N)log⁡N)O((T + N) \log N)O((T+N)logN)
• 공간 복잡도: O(N)O(N)O(N)

결론

이 문제는 우선순위 큐를 이용하여 가장 큰 값을 효율적으로 처리하는 방법과 제한된 자원을 최적화하여 사용하는 전략을 익히는 데 유용합니다. 블로그 포스팅을 통해 이와 같은 문제의 해결 방법을 체계적으로 학습해 보세요!

이제 여러분도 센티와 함께 거인의 나라를 정복해 보세요! 😊

TODAY TIL

안녕하세요! 여러분이 코딩 테스트에서 마주할 수 있는 흥미로운 문제를 소개합니다. 이 문제는 주어진 N×N  크기의 표에서 N번째로 큰 수를 찾아내는 것입니다. 표의 숫자들은 각자의 위에 있는 숫자보다 크도록 구성되어 있습니다. 예를 들어, N=5N = 5N=5일 때 다음과 같은 표가 있을 수 있습니다

12  7   9  15  5
13  8  11  19  6
21 10  26  31 16
48 14  28  35 25
52 20  32  41 49

이 표에서 다섯 번째로 큰 수를 찾아야 합니다.

입력 설명

• 첫 번째 줄에는 정수 NNN이 주어집니다 (1≤N≤1,5001 \leq N \leq 1,5001≤N≤1,500).
• 그 다음 NNN개의 줄에는 각 줄마다 NNN개의 정수가 주어집니다.
• 숫자들은 −109-10^9−109 이상 10910^9109 이하의 범위를 가지며, 모두 다릅니다.

출력 설명

• 프로그램은 NNN번째로 큰 수를 출력해야 합니다.

해결 전략

이 문제는 단순히 표를 정렬하여 NNN번째로 큰 수를 찾는 방식으로는 효율적이지 않습니다. NNN의 최대값이 1,500이므로 표에 있는 요소의 수는 최대 2,250,000개가 됩니다. 이 큰 데이터를 다룰 때 메모리와 시간 복잡도를 고려해야 합니다.

최적의 해결책은 다음과 같습니다:

1. 최소 힙(min-heap)을 사용하여 NNN개의 가장 큰 수를 유지합니다.
2. 한 줄씩 입력을 받아 즉시 처리하여 메모리 사용을 줄입니다.

코드 설명

이제 문제를 해결하는 코드를 단계별로 설명하겠습니다.

import sys
import heapq

# 입력을 빠르게 받기 위해 sys.stdin을 사용
input = sys.stdin

# N을 입력받음
N = int(input.readline().strip())
min_heap = []  # 최소 힙을 저장할 리스트

# N개의 행에 대해 각 숫자를 읽어들임
for _ in range(N):
    row = map(int, input.readline().split())  # 한 줄의 숫자를 공백 기준으로 분리하여 처리
    for num in row:
        # 힙의 크기가 N보다 작은 경우 숫자를 추가
        if len(min_heap) < N:
            heapq.heappush(min_heap, num)
        else:
            # N개의 숫자가 이미 힙에 있으면, 새로운 숫자가 최소값보다 큰 경우 교체
            if num > min_heap[0]:
                heapq.heappushpop(min_heap, num)

# 힙의 최솟값이 N번째로 큰 수가 됨
print(min_heap[0])

코드 설명 (더 자세히)

• heapq 모듈은 Python에서 힙 자료구조를 다룰 수 있는 모듈입니다. 이 문제에서는 최소 힙을 사용해 NNN개의 가장 큰 수를 유지합니다.
• sys.stdin.readline(): 표의 크기가 크기 때문에, 입력을 빠르게 받기 위해 input() 대신 sys.stdin.readline()을 사용했습니다. 이는 큰 입력을 더 효율적으로 처리합니다.
• 히프 유지: 힙에 NNN개의 요소만 유지하여 메모리를 절약합니다. 새로운 숫자가 힙의 최솟값보다 클 경우에만 추가하고 기존 최소값을 제거합니다.

예제 실행

입력 예시

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

이 경우, 다섯 번째로 큰 수는 35입니다. 프로그램은 이 값을 올바르게 출력합니다.

시간 및 공간 복잡도 분석

• 시간 복잡도: O(N2log⁡N)O(N^2 \log N)O(N2logN). 각 숫자마다 힙 연산이 O(log⁡N)O(\log N)O(logN)이고 총 N2N^2N2개의 숫자를 처리합니다.
• 공간 복잡도: O(N)O(N)O(N). 힙의 크기는 항상 NNN으로 유지되므로 메모리 사용량이 제한적입니다.

결론

이 접근법은 메모리와 시간 효율성을 모두 고려하여 NNN번째로 큰 수를 찾는 데 적합합니다. 만약 여러분이 비슷한 문제나 더 좋은 최적화 방법을 알고 있다면 댓글로 알려주세요!

이제 이 코드와 설명을 통해 여러분도 이 문제를 해결할 수 있기를 바랍니다. 코딩 테스트나 실무 프로젝트에서도 도움이 되길 바랍니다!

TODAY TIL

안녕하세요! 이번 블로그 포스팅에서는 학교 식당 줄 서기 문제를 해결하는 파이썬 코드와 문제 해결 과정을 공유해보려고 합니다. 이 문제는 많은 학생들이 식당에서 줄을 서고, 식사가 준비되는 과정을 처리하면서 최대 대기 인원을 기록하는 문제입니다. 특히, 입력의 개수가 많기 때문에 효율적인 구현이 필요합니다. 함께 문제를 이해하고 해결해봅시다!

문제 설명

학생들이 학교 식당에 도착하고, 식사가 준비되는 총 n개의 정보가 주어집니다. 이 정보는 두 가지 유형으로 이루어져 있습니다:

1. 학생 도착 (유형 1 a): 학생 번호 a가 식당에 도착하여 줄을 섭니다.
2. 식사 준비 (유형 2): 줄의 맨 앞 학생이 식사를 시작합니다.

식당에 도착한 학생은 줄의 맨 뒤에 서게 되며, 식사가 준비되면 줄의 맨 앞에 있는 학생이 식사를 하러 들어갑니다. 우리는 이 과정에서 줄에 서 있는 학생 수가 최대가 되었을 때, 그 순간 줄의 맨 뒤에 있는 학생 번호를 출력해야 합니다.

문제 해결 접근법

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용했습니다:

• 큐(Queue) 자료구조를 활용해 학생들이 줄을 서고, 식사를 하러 들어가는 과정을 구현합니다. deque 모듈을 사용하면 큐의 양쪽에서 삽입과 삭제가 빠르게 이루어지므로 적합합니다.
• 최대 대기 인원과 그 순간의 줄 맨 뒤 학생 번호를 추적하여 결과를 계산합니다.

코드 구현

아래는 문제를 해결하기 위한 파이썬 코드입니다:

from collections import deque
import sys

n = int(input())
queue = deque()
max_wait = 0
last_student = 100001

for _ in range(n):
    action = sys.stdin.readline().strip()
    if action[0] == '1':  # 학생 도착 (유형 1)
        _, student_number = action.split()
        student_number = int(student_number)
        queue.append(student_number)

        if len(queue) > max_wait:
            max_wait = len(queue)
            last_student = queue[-1]
        elif len(queue) == max_wait:
            if queue[-1] < last_student:
                last_student = queue[-1]

    elif action[0] == '2' and queue:  # 식사 준비 (유형 2)
        queue.popleft()

if max_wait == 0:
    last_student = -1

코드 설명

1. 입력 처리 및 초기화
   • n은 총 명령어의 개수를 의미합니다.
   • queue는 학생들이 줄을 서는 대기열을 나타내며, deque()로 초기화됩니다.
   • max_wait는 대기 중인 최대 학생 수를 저장하며, last_student는 그때 줄의 맨 뒤에 있는 학생 번호를 기록합니다.
2. 학생 도착 처리 (유형 1)
   • 학생 번호가 주어지면 해당 번호를 큐의 맨 뒤에 추가합니다.
   • 대기열 길이가 max_wait보다 크다면 이를 갱신하고, last_student를 현재 줄의 맨 뒤 학생 번호로 업데이트합니다.
   • 만약 대기열 길이가 max_wait와 같다면, 줄의 맨 뒤 학생 번호가 더 작은 경우로 갱신합니다.
3. 식사 준비 처리 (유형 2)
   • 식사가 준비되면 큐의 맨 앞에 있는 학생을 제거합니다.
4. 결과 계산
   • 만약 최대 대기 인원이 0이라면, 대기 중인 학생이 없다는 의미로 last_student를 -1로 설정합니다.

문제 해결의 어려움과 해결 방법

이 문제는 주어진 입력의 개수가 최대 100,000개일 수 있기 때문에 효율적인 입력 처리와 큐의 사용이 필수적입니다. sys.stdin.readline()을 사용하여 입력을 빠르게 처리하고, deque를 활용하여 큐 연산을 효율적으로 구현함으로써 런타임 에러를 피할 수 있었습니다.

마무리

이번 포스팅에서는 학생들이 식당에서 줄을 서는 문제를 해결하는 파이썬 코드를 다뤄보았습니다. 큐 자료구조를 사용해 효율적으로 줄 서기와 식사 과정을 처리하고, 최대 대기 인원과 그때의 학생 번호를 찾는 과정에서 발생할 수 있는 여러 가지 상황들을 고려했습니다. 이 코드가 여러분의 이해에 도움이 되었기를 바랍니다!

TODAY TIL

안녕하세요! 오늘은 게임 내에서 연계 기술의 발동 조건을 다루는 흥미로운 문제를 풀어볼 거예요. 임스가 플레이 중인 게임에서는 몇 가지 규칙에 따라 기술이 발동됩니다:

• 연계 기술은 사전 기술과 본 기술의 조합입니다.
• 사전 기술 없이 본 기술을 사용하면 기술이 비정상적으로 발동됩니다.
• 사전 기술은 L, S, 본 기술은 R, K입니다.
• 숫자 1부터 9까지의 기술은 언제나 단독으로 발동할 수 있습니다.

예를 들어, L을 사용한 후에 R을 사용하면 정상 발동되지만, R만 있으면 발동되지 않아요.

문제 해결 아이디어

이 문제를 해결하려면, 사전 기술이 사용되었는지 확인하면서 본 기술이 발동될 수 있는지를 검토하면 됩니다.

주요 아이디어

• 사전 기술(L, S)이 나오면 리스트에 저장해두고, 본 기술(R, K)이 나올 때 이 리스트를 확인해 발동 여부를 결정합니다.
• 숫자 기술(1~9)은 특별한 조건 없이 바로 발동할 수 있습니다.

코드 설명

# 기술의 개수 입력받기 (사용하지 않지만 문제의 형식에 맞추어 필요)
N = int(input())  

# 기술 순서를 문자열로 입력받고 리스트로 변환
skill = list(str(input()))

# 정상적으로 발동된 기술의 개수를 세는 변수
num = 0

# 사용된 사전 기술을 추적하는 리스트
used_list = []

# 기술을 하나씩 확인하며 발동 여부 판단
for i in skill:
    # 사전 기술 'L' 또는 'S'가 나오면 used_list에 추가
    if i == 'L' or i == 'S':
        used_list.append(i)
    
    # 본 기술 'K'가 나왔을 때
    elif i == 'K':
        # 사전 기술 'S'가 있다면 발동 가능
        if 'S' in used_list:
            used_list.remove('S')  # 사용한 'S'는 리스트에서 제거
            num += 1  # 발동된 기술 수 증가
        else:
            break  # 사전 기술 없으면 반복 종료 (스크립트 꼬임)
    
    # 본 기술 'R'이 나왔을 때
    elif i == 'R':
        # 사전 기술 'L'이 있다면 발동 가능
        if 'L' in used_list:
            used_list.remove('L')  # 사용한 'L'은 리스트에서 제거
            num += 1  # 발동된 기술 수 증가
        else:
            break  # 사전 기술 없으면 반복 종료 (스크립트 꼬임)
    
    # 숫자 기술 '1'~'9'는 조건 없이 발동 가능
    else:
        num += 1

# 최종 발동된 기술의 개수 출력
print(num)

설명

• L이 나오면 사전 기술로 저장됩니다.
• 1은 사전 기술이 필요 없는 숫자 기술이므로 바로 발동됩니다.
• S가 나오면 사전 기술로 저장됩니다.
• 2도 숫자 기술이라 바로 발동됩니다.
• R이 나오면 L이 사전 기술로 사용되었으므로 발동됩니다.
• K도 S가 사용된 상태이므로 발동됩니다.

발동된 기술은 총 4개입니다.

결론

이 문제는 리스트를 사용해 사전 기술의 사용 상태를 관리하면서 본 기술 발동 여부를 체크하는 방식으로 해결할 수 있었습니다. 코드의 각 부분을 이해하고, 예제를 실행해보며 학습하면 확실히 이해할 수 있을 거예요!

TODAY TIL

안녕하세요! 오늘은 n개의 숫자가 적힌 카드를 이용해 특정 규칙에 따라 카드를 처리하는 Python 코드에 대해 설명해드리겠습니다. 이 코드는 카드 게임의 시뮬레이션으로, 주어진 카드가 한 장 남을 때까지의 과정을 출력합니다.

문제 설명

사용자는 n개의 카드(숫자 1부터 n까지)를 갖고 있으며, 다음의 규칙을 반복해서 카드가 한 장 남을 때까지 진행합니다:

1. 제일 위에 있는 카드를 버립니다.
2. 그다음 제일 위에 있는 카드를 제일 아래로 옮깁니다.

코드 설명

n = int(input())
card = [i for i in range(1, n + 1)]
discard = []

while len(card) != 1:
    discard.append(card.pop(0)) # 제일 위에 있는 카드를 버린다.
    card.append(card.pop(0))    # 제일 위에 있는 카드를 제일 아래로 옮긴다.

for c in discard:
    print(c, end=' ')
print(card[0])

코드 단계별 분석

1. 입력받기: n은 카드의 개수를 나타내며, 사용자가 입력합니다.
2. 카드 리스트 생성: card는 1부터 n까지의 숫자가 순서대로 저장된 리스트입니다. 예를 들어, n=7일 경우 card = [1, 2, 3, 4, 5, 6, 7]입니다.
3. 버려진 카드 리스트 초기화: discard는 게임 중 버려진 카드를 저장하기 위한 빈 리스트입니다.
4. 메인 로직:
   • while len(card) != 1: 조건을 만족할 때까지 반복합니다.
   • discard.append(card.pop(0)): 카드의 맨 위에 있는 카드를 discard에 추가합니다.
   • card.append(card.pop(0)): 카드의 맨 위에 있는 카드를 제거하고, 이를 카드 리스트의 맨 아래로 보냅니다.
5. 출력:
   • discard 리스트의 내용을 순서대로 출력합니다.
   • 마지막으로 남은 한 장의 카드를 출력합니다.

동작 예시

입력: n = 7

초기 상태:

• card = [1, 2, 3, 4, 5, 6, 7]
• discard = []

게임 과정:

1. discard = [1], card = [3, 4, 5, 6, 7, 2]
2. discard = [1, 3], card = [5, 6, 7, 2, 4]
3. discard = [1, 3, 5], card = [7, 2, 4, 6]
4. discard = [1, 3, 5, 7], card = [4, 6, 2]
5. discard = [1, 3, 5, 7, 4], card = [2, 6]
6. discard = [1, 3, 5, 7, 4, 2], card = [6]

출력:

1 3 5 7 4 2
6

결과 해석: 버려진 카드의 순서를 출력한 후, 마지막으로 남은 카드를 출력합니다.

이 코드의 핵심은 리스트의 pop(0) 메서드와 append() 메서드를 사용하여 카드의 순서를 처리하는 것입니다. 이를 통해 카드 게임의 규칙을 간단하게 구현할 수 있습니다.

결론

이 코드 예제는 Python의 리스트 메서드를 활용하여 간단한 카드 게임을 시뮬레이션하는 방법을 잘 보여줍니다. 다양한 카드 처리 문제에 응용할 수 있는 좋은 연습이 될 것입니다.

다음에도 재미있는 코드 설명으로 찾아오겠습니다. 읽어주셔서 감사합니다!

TODAY TIL

안녕하세요! 오늘은 배열에서 연속으로 나타나는 숫자를 제거하는 문제를 해결하는 방법을 소개하겠습니다. 이 문제는 배열 arr에 연속으로 나타나는 숫자가 있을 때, 중복된 숫자를 하나만 남기고 제거하여 반환하는 문제입니다. 문제 풀이를 단계별로 설명하겠습니다.

문제 설명

• 배열 arr가 주어집니다.
• 배열의 각 원소는 0부터 9까지의 숫자로 이루어져 있습니다.
• 연속적으로 나타나는 숫자를 하나만 남기고 제거한 배열을 반환합니다.
• 예를 들어:
  • arr = [1, 1, 3, 3, 0, 1, 1]이면 [1, 3, 0, 1]을 반환해야 합니다.
  • arr = [4, 4, 4, 3, 3]이면 [4, 3]을 반환해야 합니다.

제한사항

• 배열 arr의 크기: 최대 1,000,000
• 배열 arr의 원소: 0 이상 9 이하의 정수

문제 해결 접근법

1. 문제 이해 및 계획

• 주어진 배열을 순회하면서 연속된 숫자가 중복인지 확인하고, 중복이 아니면 결과 배열에 추가합니다.
• 각 숫자를 이전 숫자와 비교하여 중복 여부를 판단합니다.

2. 구현 단계

• 빈 배열 result를 초기화하여 중복되지 않은 숫자를 저장합니다.
• previous 변수로 이전 숫자를 저장합니다.
• arr의 각 원소를 순회하며, previous와 비교해 다를 경우에만 result에 추가합니다.

3. 코드 구현

다음은 문제를 해결하는 Python 코드입니다:

def solution(arr):
    result = []  # 결과를 저장할 배열
    previous = None  # 이전 원소를 저장할 변수

    for num in arr:
        # 이전 원소와 다를 때만 결과 배열에 추가
        if num != previous:
            result.append(num)
            previous = num  # 현재 숫자를 이전 숫자로 갱신

    return result

# 테스트 케이스
print(solution([1, 1, 3, 3, 0, 1, 1]))  # 출력: [1, 3, 0, 1]
print(solution([4, 4, 4, 3, 3]))        # 출력: [4, 3]

4. 코드 설명

• result 배열은 중복이 제거된 숫자들을 저장합니다.
• previous 변수는 이전 숫자를 저장해 연속 중복을 판단합니다.
• arr의 각 숫자를 순회하며 previous와 비교해 다르면 result에 추가하고, previous를 현재 숫자로 갱신합니다.

5. 시간 및 공간 복잡도

• 시간 복잡도: O(n)O(n)O(n) — 배열을 한 번 순회하므로 매우 효율적입니다.
• 공간 복잡도: O(n)O(n)O(n) — 중복이 제거된 결과 배열을 저장하기 때문입니다.

마무리

이 코드로 연속된 중복 숫자를 손쉽게 제거할 수 있습니다. 배열의 길이가 최대 1,000,000인 경우에도 효율적으로 동작합니다. 문제를 풀면서 알고리즘의 효율성과 Python의 기본 문법을 함께 이해할 수 있는 좋은 예제였습니다.