[Swift] - 프로그래머스 짝지어 제거하기

출처: 프로그래머스 [짝지어 제거하기]

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

프로그래머스

문제

 

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

우선 처음 문제를 접했을 때는 이중 반복문을 돌며 요소들을 제거하려 했으나 시간초과 문제로 실패하고 말았다.

 

그래서 스택을 사용해서 문제를 해결해보았다.

import Foundation

func solution(_ s:String) -> Int{
    var arr = [Character]()  
    for i in s {
         if arr.isEmpty == true { //비어있을 경우
             arr.append(i)
         } else if arr.last == i { //같을 경우
             arr.removeLast()
         } else {
             arr.append(i)
         }
     }

    if arr.count == 0 {
        return 1
    } else {
        return 0
    }
}

 

다음과 같이 s에 있는 문자열을 character 타입으로 받아서 스택처럼 arr이 비어있을 경우 요소를 추가해주었고, 마지막 요소가 다음 들어올 요소와 같을 경우 마지막 요소를 삭제해주었다. 만약 arr에 들어있는 요소와 들어올 요소가 다를 경우 스택에 추가했다.

그러나 정확성 테스트의 경우 문제없이 통과되었으나, 효율성 테스트 3번만 통과가 되지 않아서 이를 알아본 결과 반복문의 속도 차이에 의해서 이러한 현상이 발견한 것이었다.

 

반복문 속도의 순서는 다음과 같다. 

for loop > reduce > forEach > map 

첫번째 풀이의 경우 forEach 반복문을 써서 효율성 테스트가 통과되지 않은 것이라 판단하여 다음과 같이 코드를 작성했다.

 

import Foundation

func solution(_ s:String) -> Int{
    var arr = [Character]()
    var arr2 = [Character]()
    
    for i in s {
        arr2.append(i)
    }

    for i in 0..<s.count {
        if arr.isEmpty == true {
            arr.append(arr2[i])
        } else if arr.last == arr2[i] {
            arr.removeLast()
        } else {
            arr.append(arr2[i])
        }
    }
    
    if arr.count == 0 {
        return 1
    } else {
        return 0
    }
}

이렇게 코드를 for문을 사용해 수정했더니 효율성 테스트를 문제 없이 통과했다.