문제 설명
별표 *를 포함한 문자열 s가 주어졌을 때, 별표가 남아 있지 않을 때까지 다음 작업을 수행할 수 있습니다: 문자열 s에서 별표를 선택합니다. 별표의 왼쪽에 가장 가까운 별표가 아닌 문자를 제거하고, 별표 자체도 제거합니다. 모든 별표가 제거된 후의 문자열을 반환합니다. 참고: 작업이 항상 가능하도록 입력이 생성됩니다. 결과 문자열은 항상 유일함을 보일 수 있습니다.
예제
예제 1
예제 2
⚠️제약 조건
- •
1 ≤ s.length ≤
105 - •
s는 소문자 영어 알파벳과 별표 *로 구성됩니다.
- •
연산은 s에 대해 수행될 수 있습니다.
해결 방법
🎯접근 방식
이 문제는 스택 자료구조를 사용하여 해결할 수 있습니다. 문자열을 왼쪽에서 오른쪽으로 순회하면서, 문자가 ''가 아닐 경우 스택에 추가하고, ''일 경우 스택에서 가장 최근의 문자를 제거합니다. 핵심 아이디어는 스택을 사용하여 '*'의 왼쪽에 있는 가장 가까운 문자를 효율적으로 제거하는 것입니다.
솔루션 코드
복잡도 분석
O(n)O(n)💡상세 설명
이 문제는 주어진 문자열에서 별표(*)를 처리하여 특정 규칙에 따라 문자를 제거한 후 최종 문자열을 반환하는 문제입니다. 이 문제를 해결하기 위해 스택 자료구조를 사용한 알고리즘을 구현했습니다. 이제 이 코드의 작동 원리와 각 단계에 대해 자세히 설명하겠습니다.
1. 알고리즘의 핵심 아이디어
이 문제의 핵심은 문자열을 왼쪽에서 오른쪽으로 순회하면서 별표(*)가 나타날 때마다 그 왼쪽에 있는 가장 가까운 문자를 제거하는 것입니다. 이 작업을 효율적으로 수행하기 위해 스택을 사용합니다. 스택은 후입선출(LIFO, Last In First Out) 구조이기 때문에 가장 최근에 추가된 문자를 쉽게 제거할 수 있습니다.
2. 코드의 주요 로직 설명
- 스택 초기화: 먼저 빈 스택을 생성합니다. 이 스택은 별표가 아닌 문자를 저장하고, 별표가 나타날 때마다 가장 최근의 문자를 제거하는 데 사용됩니다.
- 문자열 순회: 문자열의 각 문자를 순회하면서 다음과 같은 작업을 수행합니다:
- 문자가 별표가 아닐 경우: 스택에 해당 문자를 추가합니다.
- 문자가 별표일 경우: 스택에서 가장 최근에 추가된 문자를 제거합니다.
- 결과 반환: 모든 문자를 순회한 후, 스택에 남아 있는 문자들을 합쳐 최종 문자열을 반환합니다.
3. 각 단계별 동작 과정
stack변수를 빈 배열로 초기화합니다.- 문자열
s의 각 문자를 하나씩 확인합니다.char가 별표(*)가 아닐 경우:stack.push(char)를 호출하여 스택에 문자를 추가합니다.char가 별표(*)일 경우: 스택이 비어 있지 않다면stack.pop()을 호출하여 스택의 맨 위에 있는 문자를 제거합니다.
- 문자열 순회가 끝나면,
stack.join('')을 호출하여 스택에 남아 있는 문자들을 하나의 문자열로 합쳐 반환합니다.
4. 핵심 변수들의 역할
stack: 별표가 아닌 문자를 저장하는 배열입니다. 별표가 나타날 때마다 가장 최근의 문자를 제거하는 데 사용됩니다.char: 문자열s를 순회하면서 각 문자를 나타내는 변수입니다.
5. 왜 이 방법이 효과적인지
이 방법이 효과적인 이유는 스택을 사용하여 별표를 처리할 때마다 O(1) 시간 복잡도로 가장 최근의 문자를 제거할 수 있기 때문입니다. 문자열을 한 번만 순회하면서 모든 연산을 수행하므로 전체 알고리즘의 시간 복잡도는 O(n)입니다. 이는 매우 효율적이며, 문제의 조건을 만족하는 최적의 해결 방법입니다.
이와 같은 방식으로 문제를 해결하면, 별표에 의해 제거되어야 하는 문자들을 정확하고 효율적으로 처리할 수 있습니다. 결과적으로, 최종적으로 남는 문자열을 빠르게 얻을 수 있습니다.