이 글에서는 '0'과 '1'로만 구성된 문자열이 주어졌을 때, 두 개의 '0' 사이에 끼어 있는 '1'을 모두 제거하는 방법을 알아봅니다. 최종 결과 문자열에는 양쪽이 '0'으로 둘러싸인 '1'이 하나도 남아 있지 않아야 합니다.
입력 : string = "110010" 출력 : "11000" 설명 : 4번째 인덱스의 '1'이 두 개의 '0' 사이에 위치합니다. 입력 : string = "0010" 출력 : "000" 설명 : 2번째 인덱스의 '1'이 두 개의 '0' 사이에 위치합니다.
문제 해결 접근 방법
가장 간단한 방법은 반복문으로 문자열을 순회하면서 각 위치의 바로 앞과 뒤 문자가 모두 '0'인지 확인하는 것입니다. 조건을 만족하는 위치의 문자가 '1'이라면 해당 문자를 삭제합니다.
여기서 주의할 점은, 문자 하나가 삭제되면 나머지 문자들의 위치가 당겨지면서 새로운 위치의 '1'이 두 '0' 사이에 놓이는 연쇄적인 변화가 일어날 수 있다는 것입니다. 따라서 삭제 후에는 인덱스와 문자열 길이를 적절히 조정해 주어야 합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main () {
string str = "110010";
int length = str.length();
for (int i = 1; i < length - 1; i++) {
// 현재 문자가 '1'이고, 앞뒤 문자가 모두 '0'인지 검사
if (str.at(i) == '1' && str.at(i - 1) == '0' && str.at(i + 1) == '0') {
// 두 0 사이에 있는 '1'을 삭제
str.erase(i, 1);
i--;
if (i > 0 && str.at(i - 1) == '0')
i--;
// 요소 제거 후 문자열 길이 갱신
length = str.length();
}
}
cout << "두 0 사이의 요소를 제거한 후 문자열: " << str;
return 0;
}
실행 결과
두 0 사이의 요소를 제거한 후 문자열: 11000
코드 상세 설명
- 반복문을 사용해 인덱스 1부터 (길이 - 2)까지 문자열을 순회합니다.
- 현재 문자가 '1'이면서, 바로 앞 인덱스와 바로 뒤 인덱스의 문자가 모두 '0'인지 검사합니다. 이때 현재 문자가 '1'인지 함께 확인하는 것이 중요합니다. 이 조건이 없으면 삭제 과정에서 '0' 사이에 놓이게 된 '0'까지 잘못 지워질 수 있습니다.
- 조건을 만족하면
erase()함수로 해당 위치의 문자를 삭제합니다. - 삭제 직후 인덱스를 한 칸 뒤로 옮기고, 앞 문자가 '0'이라면 한 번 더 옮겨서, 삭제로 인해 연쇄적으로 새로 생긴 패턴도 빠짐없이 검사할 수 있도록 합니다.
- 매번 문자열 길이를 갱신하고, 반복문이 종료되면 최종 문자열을 출력합니다.
마무리
이 글에서는 '0'과 '1'로 구성된 문자열에서 두 '0' 사이에 있는 '1'을 제거하는 문제를 살펴보고, 이를 해결하는 C++ 프로그램의 동작 원리를 단계별로 확인했습니다. 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 구현할 수 있으니, 여러분이 익숙한 언어로 직접 작성해 보며 개념을 확실히 다져 보시기 바랍니다.