문제
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"
}
'코테' 카테고리의 다른 글
[Swift] 백준 4659번 : 비밀번호 발음하기 (0) | 2024.08.29 |
---|