[리트코드] Remove All Adjacent Duplicates in String II

 

▼ 문제 링크

Remove All Adjacent Duplicates in String II - LeetCode

 

비슷한 유형의 문제가 몇 번 있었는데 계속 틀리는 것 같다.

이번 문제는 보자마자 Stack을 바로 떠올렸어야 하는데 그러지 못하고 빙빙 돌아 비효율적인 방법으로 접근했다.
정답은 맞췄지만, 당연하게도 효율이 좋지 않았고, 결과적으로 아주아주 긴 문자열에서는 시간 초과가 떴다. 

이 문제의 해답은 독특하게도 Stack뿐만 아니라 Tuple을 함께 썼더라.

 

 

# 풀이 1
문자열 접근 및 중복 반복문

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var words: [String] = s.map {String($0)}
        var duplicated: Bool = true
        var count = words.count
        
        repeat {
        	// 남은 words의 개수가 k보다 작으면 반복문 중단
            if words.count < k {
                break
            }
            
            var i = 0
            while i <= words.count-k {
                duplicated = true

                for j in 1..<k {
                	// 연속된 k개의 문자 중 중복되지 않은 문자가 있는 경우
                    if words[i].isEmpty || words[i] != words[i+j] {
                        duplicated = false
                        break
                    }
                }

				// 연속된 k개의 문자가 모두 똑같은 경우
                if duplicated {
                    for j in 0..<k {
                        words[i + j] = ""
                    }
                    i += 3
                } else {
                    i += 1
                }
            }
            
            count = words.count
            words = words.filter { !$0.isEmpty }
          // while 조건: 중복된 값이 제거되어 words의 총 개수가 변했을 때
        } while count != words.count
        
        return words.joined()
    }
}

처음 생각해 낸 코드

1. 주어진 문자열을 처음부터 끝까지 훑는다.
2. 연속된 k개의 문자열이 모두 같은 문자라면 해당 문자를 ""로 치환한다.
3. 마지막 문자열까지 살펴보면 ""로 치환된 문자를 제거한다.
4. 중복되어 제거한 문자열을 대상으로 다시 처음부터 끝까지 훑는다.
5. 더이상 중복되어 제거된 값이 없을 때까지 앞의 과정을 반복한다.

이 과정은 주어진 문자열을 처음부터 끝까지 훑는데, 심지어 그 과정을 중복된 값이 없을 때까지 반복한다는 게 시간 초과에 가장 큰 요인이었던 것 같다.

Stack으로 풀어야 하는데, Discuss에 올라온 글 중에 Stack과 Tuple을 함께 사용한 풀이를 발견했다.

자료 구조 중에서 Tuple은 아직 제대로 활용해 본 적이 없어서 궁금해서 찾아봤는데 정말 흥미로운 풀이법이었다.

 

 

# 풀이 2
Stack과 Tuple을 함께 사용하기

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var stack = [(Character, Int)]() 

        for char in s {
			// Stack이 비었거나 Stack의 가장 마지막 요소 문자와 같지 않을 경우
            if stack.isEmpty || stack.last!.0 != char {
                stack.append((char, 1))
            // Stack의 가장 마지막 요소 문자와 같을 경우
            } else {
                stack[stack.count - 1].1 += 1

                if stack.last!.1 == k {
                    stack.removeLast()                    
                }
            }
        }

        var result = [Character]()
        
        for element in stack {
            for _ in 0..<element.1 {
                result.append(element.0)
            }
        }

        return String(result)
    }
}

Tuple을 이용하며 문자와 문자가 연속해서 나타난 횟수를 저장하는 방법

'Tuple을 잘 활용하면 이렇게도 할 수 있구나' 하고 감탄했던 풀이법이다. Array, Dictionary, Set은 많이 써봤는데 앞으론 Tuple도 활용해봐야겠다.

 

출처: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/discuss/1362869/Swift-stack-with-tuple