오늘의 공부 키워드

1337 The K Weakest Rows in a Matrix

 

1337 The K Weakest Rows in a Matrix

이 문제는 이진 행렬에서 각 행의 군인 수를 계산하고, 주어진 k 값에 따라 가장 약한 행의 인덱스를 반환하는 문제입니다. 주어진 조건에 따라 각 행의 군인 수를 계산하고, 같은 수의 군인을 가진 행은 인덱스 순서대로 정렬합니다. 이를 통해 가장 약한 k개의 행을 구할 수 있습니다.

 

문제를 해결하는 방법은 다음과 같습니다:

  1. 각 행의 군인 수를 계산합니다.
  2. 행의 인덱스와 군인 수를 튜플로 묶어 리스트를 만듭니다.
  3. 이 리스트를 군인 수와 인덱스를 기준으로 정렬합니다.
  4. 정렬된 리스트에서 가장 약한 k개의 행의 인덱스를 추출합니다.

파이썬코드

def kWeakestRows(mat, k):
    # 각 행의 군인 수를 계산하여 리스트 생성
    soldiers_count = [(sum(row), index) for index, row in enumerate(mat)]
    
    # 군인 수와 인덱스를 기준으로 정렬
    soldiers_count.sort()
    
    # 가장 약한 k개의 행의 인덱스를 추출하여 반환
    return [index for _, index in soldiers_count[:k]]

# 예시 입력
mat1 = [
    [1, 1, 0, 0, 0],
    [1, 1, 1, 1, 0],
    [1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [1, 1, 1, 1, 1]
]
k1 = 3

mat2 = [
    [1, 0, 0, 0],
    [1, 1, 1, 1],
    [1, 0, 0, 0],
    [1, 0, 0, 0]
]
k2 = 2

# 결과 출력
print(kWeakestRows(mat1, k1))  # Output: [2, 0, 3]
print(kWeakestRows(mat2, k2))  # Output: [0, 2]

 

이 코드는 각 행의 군인 수를 계산하고, 이를 이용해 행을 정렬한 후 가장 약한 k개의 행의 인덱스를 반환합니다. 행렬의 각 행은 튜플 형태로 군인 수와 인덱스를 가지고 정렬되며, 이를 통해 약한 행을 쉽게 찾을 수 있습니다.

 

 

오늘의 공부 키워드

2500 Delete Greatest Value in Each Row

 

2500 Delete Greatest Value in Each Row

 

 

이 문제에서 주어진 m x n 행렬 grid는 양의 정수로 이루어져 있습니다. 문제에서 요구하는 연산을 수행하여 grid가 빌 때까지 계속 진행해야 합니다.

주어진 연산은 다음과 같습니다:

  1. 각 행에서 가장 큰 값을 삭제합니다. 만약 가장 큰 값이 여러 개 있다면 그 중 하나를 임의로 삭제합니다.
  2. 삭제된 원소들 중 최대값을 결과값(answer)에 더합니다.

이 연산을 모든 열이 삭제될 때까지 반복하고, 최종적으로 answer 값을 반환합니다.

해석 예제 1:

입력: grid = [[1,2,4],[3,3,1]] 출력: 8 설명: 각 단계에서 삭제된 값을 보여줍니다.

  • 첫 번째 연산에서, 첫 번째 행에서 4를 삭제하고 두 번째 행에서 3을 삭제합니다(3이 두 개 있으며 하나를 임의로 삭제할 수 있습니다). 4를 결과에 추가합니다.
  • 두 번째 연산에서, 첫 번째 행에서 2를 삭제하고 두 번째 행에서 3을 삭제합니다. 3을 결과에 추가합니다.
  • 세 번째 연산에서, 첫 번째 행에서 1을 삭제하고 두 번째 행에서 1을 삭제합니다. 1을 결과에 추가합니다. 최종 결과 = 4 + 3 + 1 = 8.

해석 예제 2:

입력: grid = [[10]] 출력: 10 설명: 각 단계에서 삭제된 값을 보여줍니다.

  • 첫 번째 연산에서, 행에서 10을 삭제합니다. 10을 결과에 추가합니다. 최종 결과 = 10.

풀이 방법:

문제의 요구사항을 따르면 각 행에서 최대값을 찾고, 이 중에서 전체의 최대값을 뽑아 더하는 과정을 반복합니다. m이 행의 수, n이 열의 수이므로, 각 단계마다 O(m) 시간이 걸리며, 최대값을 찾는 것은 O(n)이므로 전체 연산은 O(m * n)의 시간 복잡도를 갖습니다. 각 열을 한 번씩 삭제하므로 총 O(n * m * n)의 연산이 필요합니다. 그러나 이는 최악의 경우이며, 일반적인 파이썬의 내장 함수를 사용하여 최적화할 수 있습니다.

 

파이썬 코드

def max_value_removals(grid):
    answer = 0
    while grid[0]:  # 이 반복은 최대 n번 (열의 수 만큼)
        max_vals = []
        for row in grid:
            max_val = max(row)
            max_vals.append(max_val)
            row.remove(max_val)  # 가장 큰 값 하나를 삭제
        answer += max(max_vals)  # 각 행에서 삭제된 값 중 최대값을 더함
    return answer

# 예제 실행
print(max_value_removals([[1,2,4],[3,3,1]]))  # 출력: 8
print(max_value_removals([[10]]))  # 출력: 10

 

오늘의 공부 키워드

682 Baseball Game

 

682 Baseball Game

문제 설명

야구 게임이 시작될 때 기록은 비어 있습니다. 주어진 명령어 리스트를 순서대로 처리하며 점수를 기록합니다. 명령어는 다음과 같습니다:

  • 정수 x: 새로운 점수 x를 기록합니다.
  • '+': 이전 두 점수의 합을 새로운 점수로 기록합니다.
  • 'D': 이전 점수의 두 배를 새로운 점수로 기록합니다.
  • 'C': 이전 점수를 무효화하고 기록에서 제거합니다.

모든 명령어를 처리한 후 기록된 모든 점수의 합을 반환합니다.

예시

예시 1

입력: ops = ["5", "2", "C", "D", "+"] 출력: 30

설명:

  • "5" -> 기록에 5를 추가, 기록: [5]
  • "2" -> 기록에 2를 추가, 기록: [5, 2]
  • "C" -> 마지막 점수 2를 제거, 기록: [5]
  • "D" -> 마지막 점수 5의 두 배인 10을 추가, 기록: [5, 10]
  • "+" -> 마지막 두 점수 5와 10의 합인 15를 추가, 기록: [5, 10, 15]

기록된 점수의 합: 5 + 10 + 15 = 30

예시 2

입력: ops = ["5", "-2", "4", "C", "D", "9", "+", "+"] 출력: 27

설명:

  • "5" -> 기록에 5를 추가, 기록: [5]
  • "-2" -> 기록에 -2를 추가, 기록: [5, -2]
  • "4" -> 기록에 4를 추가, 기록: [5, -2, 4]
  • "C" -> 마지막 점수 4를 제거, 기록: [5, -2]
  • "D" -> 마지막 점수 -2의 두 배인 -4를 추가, 기록: [5, -2, -4]
  • "9" -> 기록에 9를 추가, 기록: [5, -2, -4, 9]
  • "+" -> 마지막 두 점수 -4와 9의 합인 5를 추가, 기록: [5, -2, -4, 9, 5]
  • "+" -> 마지막 두 점수 9와 5의 합인 14를 추가, 기록: [5, -2, -4, 9, 5, 14]

기록된 점수의 합: 5 + (-2) + (-4) + 9 + 5 + 14 = 27

예시 3

입력: ops = ["1", "C"] 출력: 0

설명:

  • "1" -> 기록에 1을 추가, 기록: [1]
  • "C" -> 마지막 점수 1을 제거, 기록: []

기록된 점수의 합: 0

 

해결 방법

  1. 기록을 저장할 빈 리스트를 생성합니다.
  2. 주어진 명령어 리스트를 순차적으로 처리합니다.
  3. 각 명령어에 따라 기록을 업데이트합니다.
  4. 모든 명령어를 처리한 후 기록된 점수의 합을 반환합니다.

 

파이썬 코드

from typing import List

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        record = []
        
        for op in operations:
            if op == "C":
                record.pop()
            elif op == "D":
                record.append(2 * record[-1])
            elif op == "+":
                record.append(record[-1] + record[-2])
            else:
                record.append(int(op))
        
        return sum(record)

# 예시 실행
solution = Solution()

ops1 = ["5", "2", "C", "D", "+"]
print(solution.calPoints(ops1))  # 출력: 30

ops2 = ["5", "-2", "4", "C", "D", "9", "+", "+"]
print(solution.calPoints(ops2))  # 출력: 27

ops3 = ["1", "C"]
print(solution.calPoints(ops3))  # 출력: 0

 

이 코드는 주어진 명령어 리스트를 순차적으로 처리하며 기록을 관리하고, 최종적으로 기록된 점수의 합을 계산하여 반환합니다. 예시 입력값에 대해 메서드를 호출하여 올바른 출력이 나오는지 확인할 수 있습니다.

 

오늘의 공부 키워드

1475 Final Prices With a Special Discount in a Shop

 

1475 Final Prices With a Special Discount in a Shop

문제 설명

주어진 정수 배열 prices에서 각 아이템의 가격이 주어집니다. 특별 할인을 받을 수 있는 조건은 다음과 같습니다:

  • i번째 아이템을 살 때, j가 i보다 크고 prices[j]가 prices[i]보다 작거나 같은 최소의 인덱스를 찾아서 prices[j] 만큼의 할인을 받습니다.
  • 만약 그런 인덱스가 없다면 할인을 받지 못합니다.

주어진 배열 prices에서 각 아이템의 최종 지불 가격을 계산하여 반환하는 정수 배열 answer를 반환하는 문제입니다.

예제

  1. 예제 1:
    • 입력: prices = [8, 4, 6, 2, 3]
    • 출력: [4, 2, 4, 2, 3]
    • 설명:
      • 아이템 0: 가격은 8이고, 최소 인덱스 1에서 4만큼 할인받아 최종 가격은 4입니다.
      • 아이템 1: 가격은 4이고, 최소 인덱스 3에서 2만큼 할인받아 최종 가격은 2입니다.
      • 아이템 2: 가격은 6이고, 최소 인덱스 3에서 2만큼 할인받아 최종 가격은 4입니다.
      • 아이템 3: 할인을 받지 못하여 최종 가격은 2입니다.
      • 아이템 4: 할인을 받지 못하여 최종 가격은 3입니다.
  2. 예제 2:
    • 입력: prices = [1, 2, 3, 4, 5]
    • 출력: [1, 2, 3, 4, 5]
    • 설명: 모든 아이템이 할인을 받지 못합니다.
  3. 예제 3:
    • 입력: prices = [10, 1, 1, 6]
    • 출력: [9, 0, 1, 6]
    • 설명:
      • 아이템 0: 가격은 10이고, 최소 인덱스 1에서 1만큼 할인받아 최종 가격은 9입니다.
      • 아이템 1: 가격은 1이고, 최소 인덱스 2에서 1만큼 할인받아 최종 가격은 0입니다.
      • 아이템 2: 할인을 받지 못하여 최종 가격은 1입니다.
      • 아이템 3: 할인을 받지 못하여 최종 가격은 6입니다.

파이썬코드

def finalPrices(prices):
    n = len(prices)
    answer = [0] * n

    for i in range(n):
        discount = 0
        for j in range(i + 1, n):
            if prices[j] <= prices[i]:
                discount = prices[j]
                break
        answer[i] = prices[i] - discount

    return answer

# 예제 테스트
print(finalPrices([8, 4, 6, 2, 3]))  # 출력: [4, 2, 4, 2, 3]
print(finalPrices([1, 2, 3, 4, 5]))  # 출력: [1, 2, 3, 4, 5]
print(finalPrices([10, 1, 1, 6]))    # 출력: [9, 0, 1, 6]

 

풀이 방법

이 문제를 해결하기 위해 다음과 같은 단계로 접근할 수 있습니다:

  1. prices 배열을 순회하면서 각 아이템의 가격을 확인합니다.
  2. 각 아이템의 가격에 대해 뒤에 나오는 가격 중에서 최소 가격을 찾습니다.
  3. 최소 가격을 찾아서 할인을 적용하고 최종 가격을 계산합니다.
  4. 최종 가격을 answer 배열에 저장합니다.

결론

이 글에서는 파이썬을 사용하여 'Final Prices With a Special Discount in a Shop' 문제를 해결하는 방법에 대해 살펴보았습니다. 각 아이템에 대해 뒤에 나오는 최소 가격을 찾아 할인을 적용하는 방법을 사용하여 문제를 해결할 수 있었습니다. 이 문제를 통해 조건문과 반복문을 활용한 배열 탐색 방법을 익힐 수 있습니다.

 

오늘의 공부 키워드

933 Number of Recent Calls

 

933 Number of Recent Calls

 

문제 설명

RecentCounter 클래스는 특정 시간 프레임 내에서 최근 요청의 수를 카운트하는 클래스입니다. 이 클래스를 구현하세요:

  • RecentCounter(): 초기화 시, 최근 요청의 수를 0으로 설정합니다.
  • int ping(int t): 시간 t에서 새로운 요청을 추가합니다. 여기서 t는 밀리초 단위의 시간을 나타내며, 지난 3000 밀리초 동안(새로운 요청을 포함하여) 발생한 요청의 수를 반환합니다. 구체적으로, [t - 3000, t] 범위에 해당하는 요청의 수를 반환합니다.

각 ping 호출은 이전 호출보다 엄격히 더 큰 값을 사용합니다.

 

예제 1:

입력:

["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

 

출력:

[null, 1, 2, 3, 3]

 

설명:

RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // 요청 = [1], 범위는 [-2999, 1], 반환 값은 1
recentCounter.ping(100);   // 요청 = [1, 100], 범위는 [-2900, 100], 반환 값은 2
recentCounter.ping(3001);  // 요청 = [1, 100, 3001], 범위는 [1, 3001], 반환 값은 3
recentCounter.ping(3002);  // 요청 = [1, 100, 3001, 3002], 범위는 [2, 3002], 반환 값은 3

 

제약 사항:

  • 1 <= t <= 10^9
  • 각 테스트 케이스는 ping을 호출할 때 엄격히 증가하는 값을 사용합니다.
  • 최대 10^4번 ping을 호출할 수 있습니다.

파이썬코드

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        self.queue.append(t)
        # Remove elements that are out of the 3000ms range
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

# Example usage
recentCounter = RecentCounter()
print(recentCounter.ping(1))     # Output: 1
print(recentCounter.ping(100))   # Output: 2
print(recentCounter.ping(3001))  # Output: 3
print(recentCounter.ping(3002))  # Output: 3

 

풀이 방법

이 문제를 해결하기 위해서 RecentCounter 클래스를 큐를 사용하여 구현할 수 있습니다. 큐를 사용하면 가장 오래된 요청을 효율적으로 제거하면서 새로운 요청을 추가할 수 있습니다. 다음은 구체적인 풀이 단계입니다:

  1. 초기화:
    • __init__ 메서드에서 큐를 초기화합니다.
  2. ping 메서드:
    • 새로운 요청이 들어오면 큐에 추가합니다.
    • 큐에서 t - 3000보다 작은 모든 요청을 제거합니다.
    • 큐의 크기를 반환합니다.

이 클래스는 ping 메서드가 호출될 때마다 큐를 업데이트하고, 큐의 크기를 반환함으로써 지난 3000 밀리초 동안의 요청 수를 계산합니다. deque를 사용하여 큐의 앞과 뒤에서 효율적으로 요소를 추가하고 제거할 수 있습니다.

 
 

+ Recent posts