알고리즘/백준
백준 19848 빈 문자열 만들기
6epsilon
2023. 2. 25. 15:32
https://www.acmicpc.net/problem/19848
19848번: 빈 문자열 만들기
0과 1로만 이루어져 있으며, 0의 개수와 1의 개수가 동일한 문자열 S가 주어진다. 당신은 S에 다음과 같은 작업을 여러 번 수행할 수 있다: S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두
www.acmicpc.net
문자열을 앞에서부터 볼 때 0에서 1로 바뀌거나 1에서 0으로 바뀌는 경우의 개수를 보자. 중간에서 부분 문자열을 삭제하면 그 개수가 2 감소한다.
0101->01
0100->00
1101->11
이런 식이기 때문. 즉, 어떻게 삭제 작업을 수행해도 가운데에서만 수행했다면 주어진 문제를 해결하는 최솟값과 같은 횟수만큼 작업을 수행한다. 문자열을 스택에 쌓으면서 맨 처음을 포함하지 않고 지워야 할 때마다 지워주면 문제가 해결된다. 문자가 바뀌거나, 쌓은 1이나 0이 그 앞의 0이나 1보다 많아지는 지점에서 지우면 된다.