[Programers] 카드 뭉치

문제

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

프로그래머스

 

 

첫번째 풀이 : removeFirst() 이용 -> 타임아웃

import Foundation

func solution(_ cards1:[String], _ cards2:[String], _ goal:[String]) -> String {
    var set1 = cards1
    var set2 = cards2
    for i in 0...goal.count-1 {
        if goal[i] == set1.first {
            set1.removeFirst()
        }
        else if goal[i] == set2.first {
            set2.removeFirst()
        }
        else {
            return "No"
        }
    }
    return "Yes"
}

 

위 풀이로 풀었더니 하나의 예시에서 타임아웃이 되었습니다. 흑흑

더 빠르게 수행하기 위해 알고리즘을 바꿔봐야겠다...

 

우선 현재 코드의 시간복잡도는 O(n) 입니다. 크게 문제될 시간복잡도는 아닌 것 같은데... 해서 내가 사용한 함수들의 시간복잡도를 찾아보았습니다.

 

removeFirst()

• 시간 복잡도 : O(n)
• 맨 처음 원소를 삭제

맨 첫번째 원소를 제거한 후 뒤에 있는 원소들을 앞으로 당겨줘야 하기 때문에 O(n) 시간이 걸린다고 하네요

 

 

그리고 원소를 지울 수 있는 다른 함수인 remove 또한 찾아보았습니다

 

remove(at:)

• 시간 복잡도 : O(n)
• 원하는 위치의 원소를 삭제

똑같이 O(n) 시간이지만 한번 바꿔서 써보면 어떨까하여 바꾸고 다시 실행해 보았는데... 왠걸 타임아웃없이 잘 실행이 되었네요?!

아니 이러면 안되는데.... 왜 되지?

 

실행 코드는 다음과 같습니다. remove 함수만 바꾸고 나머지는 모두 동일합니다.

 

두번째 풀이 : remove(at:) 이용

import Foundation

func solution(_ cards1:[String], _ cards2:[String], _ goal:[String]) -> String {
    var set1 = cards1
    var set2 = cards2
    for i in 0...goal.count - 1 {
        if goal[i] == set1.first {
            set1.remove(at: 0)
        }
        else if goal[i] == set2.first {
            set2.remove(at: 0)
        }
        else {
            return "No"
        }
    }
    return "Yes"
}

 

 

 

그렇다면 removeFirst(_:) 함수를 써보면 어떨까?

 

removeFirst(_:)

• 시간복잡도 : O(n)
• 맨 앞에서부터 입력한 개수만큼의 원소를 삭제해준다

신기하게도 해당 함수를 이용한 코드 역시 타임아웃 없이 잘 통과가 되었습니다.

그럼 문제는 removeFirst() 함수에 있었다는 의미인데, 해당 내용은 열심히 찾아보았으나 정보가 없더군요 ㅠ

 

자세히 알게 되면 removeFirst() vs removeFirst(_:) vs remove(at:) 이라는 주제로 포스팅을 할 수 있을 것 같습니다.

 

세번째 풀이 : removeFirst(_:) 이용

import Foundation
import Foundation

func solution(_ cards1:[String], _ cards2:[String], _ goal:[String]) -> String {
    var set1 = cards1
    var set2 = cards2
    for i in 0...goal.count - 1 {
        if goal[i] == set1.first {
            set1.removeFirst(1)
        }
        else if goal[i] == set2.first {
            set2.removeFirst(1)
        }
        else {
            return "No"
        }
    }
    return "Yes"
}