[Programmer] 짝지어 제거하기 (Swift)

문제 : 

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

 

1. 문제 이해하기

• 문자열이 주어졌을 때, 연속한 두 문자가 동일하면 제거하고, 제거 한 부분을 다시 앞 뒤로 이어주는 과정을 반복합니다.
• 이때, 모든 문자열이 제거되면 1, 하나라도 남아있으면 0
• 문자열의 길이는 1 이상 1,000,000 이하의 자연수

 

2. 문제 풀이 생각하기

1. 문자열의 길이가 최대 1,000,000이 될 수 있기 때문에 절대 중첩 for문으로 풀면 안 된다고 생각했습니다.
2. 그래서 투 포인터로 풀어야겠다고 생각했는데, 연속하는 문자가 발생할 때마다 remove를 진행하니 시간 초과가 발생했습니다.
3. 제거된 자리를 '0'으로 처리하고 풀까도 생각했지만 조건문이 생각보다 많아져서 다른 방법을 생각했습니다.
4. 문자 두 개만 같으면 제거가 되기 때문에, 새로운 배열(nArr)에 값을 넣으면서 nArr의 마지막 문자와 sArrd의 첫 원소가 같으면 nArr의 마지막 값만 제거해야겠다고 생각했습니다. 제거하는 시간 복잡도는 최대(O(n))씩 발생할 수 있는데, 마지막만 지우면 O(1)로 처리할 수 있겠다고 생각했습니다.
5. 먼저 nArr의 크기가 0이면 무조건 값을 넣어줍니다.
6. nArr의 마지막 값과 sArr[i]의 값이 같으면 nArr의 마지막 값 제거
7. 그 이외(nArr의 크기가 1이상이면서 들어오는 값이 마지막 값과 다르다를 때)는 그냥 값을 더해줍니다. (s = "aba" 예외사항 처리)
8. 5 ~ 7 반복

 

3. 차근차근 구현하기

import Foundation

func solution(_ s:String) -> Int{
    let sArr = Array(s).map{String($0)}
    var nArr = [String]()
    
    for i in 0..<sArr.count {
        if nArr.count == 0 {
            nArr.append(sArr[i])
            continue
        }
        if nArr[nArr.count - 1] == sArr[i] {
            nArr.removeLast()
            continue
        }
       else {
           nArr.append(sArr[i])
       }
    }
    return nArr.count == 0 ? 1 : 0
}

// print(solution("baabaa")) // 답 : 1
// print(solution("cdcd")) // 답 : 0
// print(solution("a")) // 답 : 0
// print(solution("aabb")) // 답 : 1
// print(solution("bcaacb")) // 답 : 1
// print(solution("aba")) // 답 : 0

 

4. 피드백

• 투 포인터로만 생각하다가 시간을 많이 사용해서 조금 아쉬웠습니다.
• nArr를 String 배열로 만들지 않고 Character 배열로 만들어서 nArr.last로 마지막 값에 접근하는 방식을 배웠습니다.