#045 · 스택어려움스택

연속 카드 묶음 스코어 (가중치 포함)

문제

카드 배열이 주어집니다. 카드를 왼쪽부터 하나씩 추가할 때마다 다음 규칙으로 스코어를 계산합니다:

[묶음 규칙]

새 카드를 추가할 때, 현재 묶음의 최솟값보다 새 카드가 작거나 같으면 해당 묶음과 병합되고 묶음의 최솟값이 새 카드 값으로 갱신됩니다.
병합은 연쇄적으로 발생할 수 있습니다.
스코어 = 모든 묶음에 대해 (묶음 최솟값 × 묶음 크기)의 합

예시

cards = [3, 1, 4, 2]
 
카드 3 추가: [{min:3, size:1}],          스코어 = 3×1 = 3
카드 1 추가: 1≤3 병합 → [{min:1,size:2}], 스코어 = 1×2 = 2
카드 4 추가: [{min:1,size:2},{min:4,size:1}], 스코어 = 1×2 + 4×1 = 6
카드 2 추가: 2≤4 병합 → [{min:1,size:2},{min:2,size:2}], 스코어 = 1×2 + 2×2 = 6
 
→ [3, 2, 6, 6]

제약 조건

1 ≤ cards.length ≤ 1,000
1 ≤ cards[i] ≤ 10,000

시간 복잡도 목표: O(N)

공간 복잡도 목표: O(N)

테스트 케이스

예시 1: [3,1,4,2] → [3,2,6,6]

입력: input = [3,1,4,2]

출력: [3,2,6,6]

예시 2: 오름차순 → [1,3,6] (병합 없음, 누적)

입력: input = [1,2,3]

출력: [1,3,6]

예시 3: 내림차순 → [3,4,3] (계속 병합)

입력: input = [3,2,1]

출력: [3,4,3]

예시 4: 단일 카드 → [5]

입력: input = [5]

출력: [5]

예시 5: [2,3,1] → [2,5,3]

입력: input = [2,3,1]

출력: [2,5,3]

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.