Baseball Game

Q: 야구 게임의 시간 복잡도는 얼마인가요?

각 연산은 스택의 맨 위에서 일정한 양의 작업을 수행하므로, n 개의 연산을 처리하는 데 O(n) 시간이 걸립니다. 마지막에 스택의 값을 모두 더하는 데도 최대 O(n) 이 걸리며, 누적 합계를 사용하면 이 작업조차 없앨 수 있습니다. 대부분의 연산이 점수를 추가하는 경우 스택은 O(n) 의 공간을 사용합니다.

Q: Baseball Game을 추가 공간 O(1)로 해결할 수 있나요?

일반적으로는 그렇지 않습니다. 숫자들이 이어진 뒤 "C" 항목들이 이어지면 숫자들을 역순으로 취소하므로, 각 숫자가 취소될지 알 때까지 모두 기억해야 합니다. 최악의 경우 O(n) 메모리가 필요합니다. 누적 합계를 사용하면 마지막 순회는 생략할 수 있지만, 스택은 대체할 수 없습니다.

Q: 베이스볼 게임에서 숫자와 연산을 어떻게 구분하나요?

먼저 항목을 세 가지 기호 "+" , "D" , "C" 와 비교하고, 그 외의 것은 정수로 처리하세요. 언어의 파서를 사용해 변환하면 앞에 오는 마이너스 기호를 처리하므로 "-30000" 은 -30000 이 됩니다.

쉬움스택

+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입니다.

제출 시 숨은 테스트 +13개

후속 질문

맨 끝의 기록을 더하지 않고 합계를 반환하여, 취소 작업을 포함한 모든 연산이 O(1) 시간에 완료되도록 할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

각 연산은 가장 최근 점수를 살펴보며, "C"는 점수를 한 번에 하나씩 제거할 수 있으므로 취소된 점수 이전의 점수가 다시 가장 최근 점수가 됩니다. 이러한 후입선출 방식이 바로 스택입니다. 새 점수를 하나씩 푸시하고, "C"일 때 팝한 다음, "D"와 "+"일 때 맨 위의 항목 한두 개를 읽으면 됩니다.

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

핵심 아이디어

기록은 가장 최신 점수가 끝에 오도록 목록으로 유지합니다. 그러면 각 연산은 목록의 끝에서만 이루어집니다. 정수는 추가되고, "D"는 마지막 항목의 두 배를 추가하며, "+"는 마지막 두 항목의 합을 추가하고, "C"는 마지막 항목을 제거합니다.

스택만으로 충분한 이유는 다음과 같습니다. "C"를 수행하면 두 번째로 최신이었던 점수가 최신 점수가 되고, 이어지는 "D" 또는 "+"가 읽어야 하는 값이 바로 그 점수입니다. 항목을 제거하면 이 값을 별도의 작업 없이 얻을 수 있습니다. 첫 번째 예시에서 "C"는 -6을 제거하고 [4, -2, -4]를 남기므로, 이후에 "+"가 실행되면 -2 + -4를 다시 더하게 됩니다.

연산이 모두 끝나면 목록에는 계산에 포함되는 점수만 남습니다. 이 점수들을 모두 더합니다. 각 연산은 O(1)이고 최종 합산은 O(n)이므로, 스택에 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 변수를 유지하세요. 값을 스택에 추가할 때마다 새 점수를 total에 더하고, "C"가 나올 때마다 제거되는 점수를 빼세요.

스택은 여전히 필요합니다. 취소할 때는 합계에서 어떤 점수를 빼야 하는지 알아야 하고, "+"와 "D"를 사용할 때는 취소가 발생한 뒤의 가장 최근 점수를 알아야 합니다. 첫 번째 예제에서 합계는 4, 2, -2, -8로 변한 다음, 취소로 -6을 빼서 -2가 되고, 마지막 7을 더하면 5가 됩니다.

한 번 순회하므로 시간 복잡도는 O(n)이며, 연산의 어느 접두 부분까지 처리하더라도 답을 구할 수 있습니다. 점수가 실시간으로 들어오는 경우에 중요합니다. 공간 복잡도는 O(n)입니다. 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

함정과 경계 사례

규칙은 간단하므로 대부분의 버그는 잘못된 점수를 읽거나 텍스트를 파싱하는 데서 발생합니다.

누적 합계와 마지막 두 점수만 유지하는 경우. "C" 뒤에는 그 두 점수보다 앞선 점수가 필요하므로, 취소 후 "+"가 나오면 오래된 값을 읽게 됩니다. 스택 전체를 유지하세요.
취소된 점수가 합계에서 빠진다는 점을 잊는 경우. 누적 합계를 사용한다면 "C"를 처리할 때 꺼낸 점수를 무시하지 말고 빼야 합니다.
음수 점수를 직접 파싱하다가 부호를 놓치는 경우. 언어의 정수 파서를 사용하면 "-2"를 -2로 읽습니다.
항목이 숫자인지 판단하기 위해 숫자인지 확인하는 경우. "-5"는 마이너스 기호로 시작합니다. 세 가지 기호인지 확인하고, 나머지는 모두 숫자로 처리하세요.
답이 양수라고 가정하는 경우. 음수 점수와 취소로 인해 합계가 음수가 될 수 있으며, 모든 점수가 취소되면 0이 될 수도 있습니다.

자주 묻는 질문4

야구 게임의 시간 복잡도는 얼마인가요?

각 연산은 스택의 맨 위에서 일정한 양의 작업을 수행하므로, n개의 연산을 처리하는 데 O(n) 시간이 걸립니다. 마지막에 스택의 값을 모두 더하는 데도 최대 O(n)이 걸리며, 누적 합계를 사용하면 이 작업조차 없앨 수 있습니다. 대부분의 연산이 점수를 추가하는 경우 스택은 O(n)의 공간을 사용합니다.

왜 스택이 야구 게임에 적합한 자료 구조인가요?

각 규칙은 가장 최근의 점수를 읽거나 제거하며, 취소하면 그 이전 점수가 드러납니다. 이는 후입선출 순서이며, 스택은 O(1) 시간에 푸시, 팝, 피크 연산을 제공합니다. 모든 언어에서 끝부분만 사용하는 일반 배열이나 리스트를 스택으로 쓸 수 있습니다.

Baseball Game을 추가 공간 O(1)로 해결할 수 있나요?

일반적으로는 그렇지 않습니다. 숫자들이 이어진 뒤 "C" 항목들이 이어지면 숫자들을 역순으로 취소하므로, 각 숫자가 취소될지 알 때까지 모두 기억해야 합니다. 최악의 경우 O(n) 메모리가 필요합니다. 누적 합계를 사용하면 마지막 순회는 생략할 수 있지만, 스택은 대체할 수 없습니다.

베이스볼 게임에서 숫자와 연산을 어떻게 구분하나요?

먼저 항목을 세 가지 기호 "+", "D", "C"와 비교하고, 그 외의 것은 정수로 처리하세요. 언어의 파서를 사용해 변환하면 앞에 오는 마이너스 기호를 처리하므로 "-30000"은 -30000이 됩니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값