문자열 S가 n개의 문자로 이루어져 있으며, 각 문자는 '+' 또는 '-'라고 가정해 봅시다. 돌 더미가 하나 있고, 총 n번의 연산을 수행하면서 매번 돌을 하나씩 꺼내거나 추가합니다. 단, 돌을 꺼내는 연산을 하기 전에는 반드시 더미가 비어 있지 않아야 합니다. 우리가 구해야 할 것은 이러한 연산들을 모두 수행한 뒤 더미에 남아 있을 수 있는 최소한의 돌 개수입니다. i번째 연산에서 돌을 꺼냈다면 S[i]는 '-', 돌을 추가했다면 S[i]는 '+'입니다.
예를 들어 입력이 S = "++-++"라면 출력은 3이 됩니다. 처음에 돌 더미가 0개였다고 하더라도, 모든 연산을 마친 후 남은 돌의 개수는 3개이기 때문입니다.
문제 해결 접근 방식
이 문제의 핵심은 누적 결과가 음수가 되려는 순간을 처리하는 것입니다. 돌을 꺼낼 때 더미가 비어 있으면 안 되므로, 결과가 음수가 되려 하면 그 값을 0으로 고정(clamp)합니다. 이는 마치 그 시점까지 필요한 만큼의 돌을 처음부터 더미에 넣어 두었다고 가정하는 것과 같습니다. 이렇게 하면 최종적으로 남는 값이 자연스럽게 가능한 최소 돌 개수가 됩니다.
이를 위해 다음 단계를 따릅니다.
n := S의 길이
i := 0부터 시작하여 i < n인 동안 (i를 1씩 증가시키며) 반복:
res := (S[i]가 '-'라면 res - 1과 0 중 최댓값,
그렇지 않으면 res + 1)
return res예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int n = S.size(), res = 0;
for (int i = 0; i < n; i++)
res = (S[i] == '-') ? max(res - 1, 0) : res + 1;
return res;
}
int main(){
string S = "++-++";
cout << solve(S) << endl;
}입력
"++-++"
출력
3
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 단일 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 매우 긴 입력 문자열에 대해서도 효율적으로 동작합니다.