[코딩테스트 재활 프로젝트] 2일차 올바른 괄호 / 주식가격

코딩테스트 재활 프로젝트 Day 2

올바른 괄호

올바른 괄호는 대학교 자료구조 시간에 가장 먼저 Stack을 배우면서 풀어보는 대표적인 문제다.

하지만 사실 스택을 사용하지 않아도 된다. 오늘은 그 점에 착안했다.

결국 중요한 것은 지금까지 닫히지 않은 (가 몇 개인지 확인하는 것이다.

(가 나오면 개수를 하나 늘리고, )가 나오면 하나 줄인다. 이때 개수가 음수가 된다면 지금까지 나온 (보다 )가 많다는 뜻이므로 바로 올바르지 않은 괄호라고 판단할 수 있다.

문자열을 끝까지 확인했을 때 개수가 0이면 모든 괄호가 정상적으로 닫힌 것이다.

처음에는 (와 )를 각각 카운팅했지만, 생각해보면 현재 열려 있는 괄호의 개수 하나만 관리하면 충분하다.

결국 이 문제에서 중요한 것은 스택이라는 자료구조를 떠올리는 것이 아니라, 실제로 필요한 상태가 무엇인지 생각하는 것이었다.

---

주식가격

주식가격 문제는 처음에는 단순하게 이중 포문으로 풀었다.

문제는 결국 현재 가격이 처음으로 떨어지는 시점까지 몇 초가 지났는가를 구하는 문제다.

그러므로 가장 쉬운 방법은 각 가격마다 뒤에 있는 가격을 하나씩 확인하는 것이다.

예를 들어

1 2 3 2 3

이라면 첫 번째 1부터 시작해서 오른쪽을 순회하고, 다음 2도 오른쪽을 순회하고, 그 다음 3도 오른쪽을 순회한다.

이렇게 풀면 정답은 구할 수 있지만 한 가지 문제가 있다.

같은 구간을 계속해서 중복으로 탐색한다.

예를 들어

2 3 4 6 1

이 있다면 2에서는 뒤의 3, 4, 6, 1을 확인하고, 3에서는 다시 4, 6, 1을 확인한다.

4에서도 6, 1을 다시 확인한다.

이미 한 번 확인했던 가격들을 계속 다시 확인하고 있는 것이다.

꼭 그래야 할까?

---

아직 정답을 모르는 가격을 저장하면?

여기서 생각을 조금 바꿔봤다.

각 가격마다 오른쪽을 탐색하는 대신,

아직 가격이 떨어지지 않아서 정답을 확정할 수 없는 가격들을 저장해두면 어떨까?

예를 들어

가격       2  3  4  6  1
인덱스     0  1  2  3  4

순서대로 가격을 확인하면서 아직 떨어지지 않은 인덱스를 스택에 넣는다.

2 → [0]
3 → [0, 1]
4 → [0, 1, 2]
6 → [0, 1, 2, 3]

그리고 마지막으로 1이 등장한다.

현재 가격 1은 스택에 있는 2, 3, 4, 6보다 모두 작다.

따라서 이 순간 이 가격들의 정답을 한꺼번에 확정할 수 있다.

2 → 4초
3 → 3초
4 → 2초
6 → 1초

정답이 확정된 인덱스는 스택에서 제거한다.

이렇게 하면 각각의 가격마다 오른쪽을 다시 탐색할 필요가 없다.

---

단조 스택

이 과정에서 사용한 것이 Monotonic Stack(단조 스택)이다.

단순히 스택을 사용하는 것이 아니라, 스택 안의 원소들이 특정한 순서를 유지하도록 관리한다.

이번 문제에서는 아직 가격이 떨어지지 않은 인덱스를 스택에 저장하고, 현재 가격이 스택의 가격보다 작아지는 순간 해당 인덱스들의 정답을 확정한다.

즉,

현재 값이 등장함으로써 과거 값의 정답을 결정할 수 있는 구조

라고 생각하면 될 것 같다.

---

그런데 for 안에 while이 있는데 왜 O(N)일까?

처음에는 나도 이 부분이 헷갈렸다.

코드를 보면 for문 안에 while문이 있기 때문에 단순히 생각하면 O(N²)처럼 보인다.

하지만 이중 포문과는 다르다.

이중 포문에서는 각 i마다 j가 다시 처음부터 탐색한다.

반면 단조 스택에서는 하나의 인덱스가

스택에 최대 한 번 들어가고, 최대 한 번 빠진다.

따라서 전체적으로 보면

push → 최대 N번
pop  → 최대 N번

만 발생한다.

예를 들어 마지막에 가격이 크게 떨어져서 while문이 여러 번 실행되더라도, 그때 빠져나간 인덱스들은 이미 정답을 구했기 때문에 다시 처리되지 않는다.

따라서 전체 연산량은 N + N 수준이고, 시간복잡도는 O(N)이다.

이번 문제를 통해 반복문이 중첩되어 있다고 무조건 O(N²)은 아니라는 것도 다시 확인했다.