[Swift] [7일차] 짝지어 제거하기

Programmers - 짝지어 제거하기
https://school.programmers.co.kr/learn/courses/30/lessons/12973?language=swift

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →\
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

간단 요약

그냥 2개 붙어있는 친구 지워주고, 나머지 다시 붙이고 지워줘서 이게 다 사라지는지 판단해주면 됨!

맨처음에는 for문 두개로 포인터 두개써서 완전탐색을 할까? 하는 1차원적인 생각을 했는데, 그렇게하면 시간초과가 뜨게 되기 때문에, 반복문 두개를 지양해야했다.

그래서 생각했던 것이
For문을 한번 돌면서 하려면 STACK문제로 접근해서 문자열을 반복문 돌면서 하나씩 스택에 담아주면서 같으면 pop 그렇지 않으면 append를 해주며 배열의 가장 마지막 원소와 현재보고 있는 원소를 비교해주면 될 것 같다고 판단했다.

swift에서 append ? pop?

append는 그대로 쓰면되고, pop은 popLast()를 사용해주면된다.
그리고 원래 .length == 0 , 으로 배열이 비었을때에 대해서는 isEmpty 메소드를 활용해주었다.

import Foundation

func solution(_ s: String) -> Int {
    var beforeElement: [Character] = [s[s.startIndex]
    for item in Array(s).dropFirst() {
        if beforeElement.isEmpty {
            beforeElement.append(item)
        }
        else if beforeElement.last == item {
            beforeElement.popLast()
        }
        else {
            beforeElement.append(item)
        }
    }
    return beforeElement.isEmpty ? 1 : 0
}
print(solution("bcaabaa"))

1. beforeElement에 하나씩 담아준다.
2. beforeElement가 비어있으면 비교할 수 없으니 이때 append로 현재 원소를 추가해주면된다.
3. 혼선을 줄이기 위해 startIndex를 담고시작했는데, beforeElement가 비어있을 때에 대한 처리를 해줬으니 굳이 이렇게까지 해줄 필요는 없을 것 같다.
4. 작성하고 나서 알았는데 첫번째 조건 if beforeElement.isEmpty 와 else 했을때의 로직이 동일한 것을 알았다. 그냥 isEmpty로 판단해줄 필요없이, 그냥 같지않으면 else는 지워도 될 듯하다.

원래는 .last를 했을 때, 배열이 비어있으면 에러가 뜰줄알았는데 nil값을 반환하는 것을 알았다. 그래서 그냥 last==item이 아니라면 전부 append해주는 방식으로 수정해서 로직을 간결화할 수 있었다.

개선안

import Foundation
func solution(_ s: String) -> Int {
    var beforeElement: [Character] = []
    for item in Array(s) {
        if beforeElement.last == item {
            beforeElement.popLast()
        }
        else {
            beforeElement.append(item)
        }
    }
    return beforeElement.isEmpty ? 1 : 0
}

완료 !