[코딩테스트 준비] 백준 실버 2문제(2504 괄호의 값, 2293 동전 1)

2504 괄호의 값

스택 기반 구조 해석 문제

문제 핵심 요약

이 문제는 단순한 괄호 매칭 문제가 아니며, 올바른 괄호열 검증 + 중첩 구조의 값 계산을 동시에 요구한다.

괄호열의 규칙은 다음 두 축으로 나뉜다.

1. 구조 규칙
   • () , [] 는 올바른 괄호열
   • (X), [X] 는 X가 올바르면 올바름
   • XY 는 X, Y가 올바르면 올바름
2. 값 계산 규칙
   • () → 2
   • [] → 3
   • (X) → 2 × 값(X)
   • [X] → 3 × 값(X)
   • XY → 값(X) + 값(Y)

입력 문자열 길이는 최대 30이므로,
모든 경우를 정확히 처리하는 구조적 접근이 필요하다.

접근 전략: 스택

이 문제의 본질은 중첩된 구조를 해석하면서 계산하는 것이다.

괄호는 다음 특성을 가진다.

• 가장 안쪽 괄호부터 값이 확정
• 바깥 괄호는 안쪽 결과를 곱셈
• 형제가 되는 구조는 덧셈

이건 전형적인 LIFO 구조, 즉 스택 문제다.

 

핵심 아이디어

1. 여는 괄호는 스택에 저장

 

(, [ → push

2. 닫는 괄호를 만나면

• 스택이 비어 있으면 → 잘못된 괄호열
• top이 매칭되지 않으면 → 잘못된 괄호열
• 매칭된다면:
  • 내부에 값이 없었다면 → 기본값 (2 또는 3)
  • 내부에 값이 있었다면 → 누적값 × 괄호 계수

3. 계산된 값은 다시 스택에 넣음

• 이후 바깥 괄호나 인접 괄호 계산에 사용

 

구현 관점에서 중요한 포인트

1. 스택에는 두 종류의 정보가 들어간다

• 여는 괄호 문자: '(', '['
• 계산된 값: 정수

즉, 스택에는 타입이 섞여 있다.
보통 stack<int>를 쓰고,
괄호는 음수나 별도 규칙으로 구분하거나
stack<char> + 별도 계산 로직을 둔다.

실무/코테에서는 char 스택 + 즉시 계산 방식이 가장 깔끔하다.

 

2. 내부 값 누적 방식

닫는 괄호를 만났을 때:

• 직전이 여는 괄호라면
  → () 또는 [] → 바로 2 또는 3

직전이 값이라면
→ 값들을 꺼내서 합산 후 곱셈

 

3. 최종 결과 처리

문자열 처리가 끝난 뒤:

• 스택에 괄호 문자가 남아 있다 → 잘못된 괄호열
• 스택에 숫자만 남아 있다 → 전부 합산이 결과

자주 틀리는 포인트 

1. ([)] 같은 교차 구조
   • 단순 개수 체크로는 절대 걸러지지 않음
   • 반드시 스택 top과 매칭 검사 필요
2. 닫는 괄호 먼저 등장
   • 예: ")("
   • 스택이 비어 있는 상태에서 pop 시도 → invalid
3. 마지막에 괄호가 남아 있음
   • 예: "(()"
   • 계산이 끝나도 스택 상태 확인 필수

 

시간·공간 복잡도

• 시간복잡도: O(n)
  (각 문자를 한 번씩 처리)
• 공간복잡도: O(n)
  (최대 스택 깊이)

문제 제한(30)에서는 사실상 최적.

 

문제의 의도 정리

이 문제는 단순 구현 문제가 아니다.

• 구조 해석 능력
• 스택을 이용한 중첩 계산
• 에러 케이스를 빠짐없이 처리하는 정확성

---

 

2293 동전 1

 

dp[x] = x원을 만드는 경우의 수

• 초기값: dp[0] = 1 (아무 동전도 안 쓰는 1가지)
• 각 동전 c에 대해:
  • x = c .. k
  • dp[x] += dp[x - c]

이렇게 하면 동전을 하나씩 추가해가며 조합을 누적해서,
1+2와 2+1 같은 순서만 다른 경우가 중복 카운트되지 않음.

 

왜 코인 루프가 바깥이어야 하냐

• 코인 바깥 / 금액 안쪽 → “조합(combination)” 카운트
• 금액 바깥 / 코인 안쪽 → “순열(permutation)” 카운트(순서 다른 걸 다 세버림)

문제가 원하는 건 조합이니까 코인 먼저.

체크포인트

• dp는 경우의 수라서 long long 권장 (문제에서 2^31 미만이라 int도 되긴 함)
• 동전 가치가 k보다 크면 건너뛰어도 됨
• 시간복잡도: O(n*k) = 최대 100*10000 = 1,000,000 → 0.5초 안에 충분