Baseball Game

Q: Baseball Game의 시간 복잡도는 얼마인가요?

각 연산은 스택의 맨 위에서 상수 시간 작업을 수행하므로, n 개의 연산은 O(n) 시간이 걸립니다. 대부분의 연산이 점수를 추가하는 경우 스택은 O(n) 의 공간을 차지합니다.

Q: 야구 게임을 추가 공간 O(1)로 해결할 수 있을까요?

일반적으로는 그렇지 않습니다. 숫자들이 이어진 다음 "C" 항목들이 이어지면 숫자들을 역순으로 취소하므로, 취소될지 알 때까지 모든 숫자를 기억해야 합니다. 최악의 경우 O(n) 의 메모리가 필요합니다.

쉬움스택

+10

특이한 게임의 점수를 기록합니다. operations를 왼쪽에서 오른쪽으로 읽으세요. 각 항목은 점수 기록을 변경합니다. "7" 또는 "-2"와 같은 정수는 해당 점수를 추가합니다. "+"는 가장 최근 점수 두 개의 합을 추가하고, "D"는 가장 최근 점수의 두 배를 추가하며, "C"는 가장 최근 점수를 영구적으로 제거합니다.

마지막 연산 후 기록에 남은 점수의 합을 반환하는 calPoints라는 함수를 작성하세요. 기록이 비어 있으면 합은 0입니다.

함수

calPoints(operations: string-array) → integer

operationsstring-array: 순서대로 주어지는 연산: 텍스트로 된 정수 또는 "+", "D", "C"
반환값integer: 마지막에 기록에 남아 있는 점수의 합계

제약 조건

1 ≤ operations.length ≤ 5000
각 항목은 "+", "D", "C" 또는 -3 × 10⁴ ≤ value ≤ 3 × 10⁴ 범위의 십진수 정수입니다.
모든 연산은 유효합니다. "+"는 기록에 점수가 두 개 이상 있을 때만 나오고, "D"와 "C"는 점수가 하나 이상 있을 때만 나옵니다.
기록의 모든 점수와 최종 합계는 32비트 부호 있는 정수에 들어갑니다.

예제

입력: operations = ["4", "-2", "D", "+", "C", "7"]
출력: 5
설명: 기록은 [4, -2]로 늘어나고, "D"는 -4를 더하며, "+"는 -2 + -4 = -6을 더하고, "C"는 해당 -6을 제거하며, 7은 마지막에 추가됩니다. 기록 [4, -2, -4, 7]의 합은 5입니다.

입력: operations = ["6", "D", "C", "C"]
출력: 0
설명: "D"는 6 뒤에 12를 추가하고, 그다음 두 개의 "C" 항목이 12와 6을 제거합니다. 아무것도 남지 않으므로 답은 0입니다.

입력: operations = ["1", "2", "+", "+", "D"]
출력: 21
설명: 두 개의 "+" 항목은 1 + 2 = 3과 2 + 3 = 5를 더하고, 그다음 "D"는 10을 더합니다. 기록 [1, 2, 3, 5, 10]의 합은 21입니다.

후속 질문

가장 최근의 "C"를 취소해 취소된 점수를 되돌리는 연산을 O(1) 시간에 어떻게 추가할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

각 연산은 가장 최근 점수를 읽으며, "C"는 점수를 하나씩 제거할 수 있으므로 더 오래된 점수가 다시 가장 최근 점수가 됩니다. 이는 후입선출 방식입니다. 새 점수를 각각 푸시하고, "C"에서는 팝한 다음, "D"와 "+"에서는 맨 위의 점수 하나 또는 두 개를 읽습니다.

스택에 기록을 쌓고, 마지막에 합산하세요

핵심 아이디어

기록은 가장 최신 점수가 끝에 오도록 목록으로 유지하여 각 연산이 끝부분에만 적용되게 하세요. "C" 다음에는 두 번째로 최신 점수가 최신 점수가 되며, 이후의 "D" 또는 "+" 연산은 그 점수를 읽어야 합니다. 마지막 항목을 꺼내면 해당 점수가 드러납니다. 첫 번째 예시에서 "C"는 -6을 꺼내고 [4, -2, -4]를 남깁니다.

연산이 모두 끝나면 목록에는 합산 대상인 점수만 정확히 남으므로 모두 더하세요. 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.

알고리즘

빈 스택 record로 시작합니다.
"+"의 경우, 맨 위 두 항목의 합을 푸시합니다. "D"의 경우, 맨 위 항목의 두 배를 푸시합니다.
"C"의 경우, 맨 위 항목을 팝합니다.
그 외의 경우 항목은 숫자입니다. 텍스트를 정수로 변환한 다음 푸시합니다.
스택에 남아 있는 모든 항목의 합을 반환합니다.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

누적 합계를 사용하는 스택

핵심 아이디어

total을 스택의 합과 같게 유지하세요. 새 점수를 푸시할 때마다 더하고, "C"가 나올 때마다 꺼낸 점수를 뺍니다. 취소할 점수를 알아야 하므로 스택은 유지해야 합니다. 첫 번째 예시에서 합계는 4, 2, -2, -8로 변하고, 취소하면 -6을 다시 빼내 -2가 되며, 7을 더하면 5가 됩니다.

이는 O(n) 시간에 한 번 순회하며, 연산의 어떤 접두 부분까지 처리한 뒤에도 답을 구할 수 있습니다. 각 연산이 계속 남아 있는 숫자일 수 있으므로 공간 복잡도는 O(n)입니다.

알고리즘

빈 스택 record와 total = 0으로 시작합니다.
"C"인 경우 맨 위 점수를 꺼내 total에서 뺍니다.
그렇지 않으면 새 점수를 계산합니다. "+"이면 맨 위 두 점수의 합, "D"이면 맨 위 점수의 두 배, 또는 정수 자체입니다.
새 점수를 넣고 total에 더합니다.
total을 반환합니다.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

함정과 경계 사례

누적 합계와 마지막 두 점수만 유지하는 것. ["1", "2", "3", "C", "+"]에서 "+"에는 1과 2가 필요한데, 점수 두 개만 유지하면 1이 사라집니다.
취소된 점수를 누적 합계에서 빼지 않는 것. 두 번째 예시에서는 그 결과 0이 아니라 18이 남습니다.
숫자가 있는지 확인해서 항목이 숫자라고 판단하는 것. "-2"는 마이너스 기호로 시작합니다. 세 가지 기호와 비교하고, 나머지는 모두 해당 언어의 정수 파서로 파싱하세요.
답이 양수라고 가정하는 것. ["-3", "D"]의 합은 -9입니다.

자주 묻는 질문3

Baseball Game의 시간 복잡도는 얼마인가요?

각 연산은 스택의 맨 위에서 상수 시간 작업을 수행하므로, n개의 연산은 O(n) 시간이 걸립니다. 대부분의 연산이 점수를 추가하는 경우 스택은 O(n)의 공간을 차지합니다.

야구 게임에 스택이 적합한 자료 구조인 이유는 무엇인가요?

각 규칙은 가장 최근 점수를 읽거나 제거하고, 취소하면 그 이전 점수가 다시 드러납니다. 이것은 후입선출 방식이며, 스택을 사용하면 O(1) 시간에 푸시, 팝, 피크를 수행할 수 있습니다. 배열의 끝에서만 연산하면 스택처럼 사용할 수 있습니다.

야구 게임을 추가 공간 O(1)로 해결할 수 있을까요?

일반적으로는 그렇지 않습니다. 숫자들이 이어진 다음 "C" 항목들이 이어지면 숫자들을 역순으로 취소하므로, 취소될지 알 때까지 모든 숫자를 기억해야 합니다. 최악의 경우 O(n)의 메모리가 필요합니다.

def calPoints(operations):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

operations = ["4", "-2", "D", "+", "C", "7"]

예상 출력