프로그래머스 155652 - 둘만의 암호

레벨 1 문제를 풀다가 Set 변환 비용에 대해 알게 되어 간단하게 정리해보겠심

🚀 내가 작성한 정답 코드

먼저, 문제를 해결한 코드는 다음과 같음

func solution(_ s: String, _ skip: String, _ index: Int) -> String {
    var result = ""
    
    // 1. skip에 포함된 알파벳 제거
    let alphabet = Array("abcdefghijklmnopqrstuvwxyz").filter { !skip.contains($0) }
    
    // 2. 변환된 알파벳으로 치환
    for char in s {
        if var newIndex = alphabet.firstIndex(of: char) {
            newIndex = (newIndex + index) % alphabet.count
            result += String(alphabet[newIndex])
        }
    }
    
    return result
}

여기서 Set을 사용할지 말지 고민했던 부분은 바로 skip 알파벳을 제거하는 코드였다.

let alphabet = Array("abcdefghijklmnopqrstuvwxyz").filter { !skip.contains($0) }

🤔 고민의 시작

문제를 해결한 후, 다른 사람의 풀이를 보니 Set을 활용하는 코드도 존재했다.
GPT와 대화하던 중 Set을 사용하는 것이 좋다는 답변을 듣고 고민하기 시작했음

Set을 사용하면?

let alphabet = Array("abcdefghijklmnopqrstuvwxyz").filter { !Set(skip).contains($0) }

→ skip 문자열을 Set으로 변환하여, contains 연산을 빠르게 수행하는 방식이다.

Set을 사용해야 하는 이유

Array / String에서 contains 사용 시 시간 복잡도 → O(N)
Set에 contains 사용 시 시간 복잡도 → O(1)

skip 문자열이 길어질수록 Set 변환 후 사용하는 것이 유리함.

⏳ 성능 비교 (프로그래머스에서 테스트)

1️⃣ Set 사용 / String에 contains 사용

2️⃣ Set 사용 안 함 (기존 코드) / Set에 contains 사용

의외로 Set을 사용하지 않은 경우가 더 빠른 경우도 많았다.
그래서skip 길이가 짧기 때문이 아닐까?💭 하는 의문이 생겼다.

🧐 Set이 항상 빠를까?

Set이 오히려 느린 경우

skip 길이가 짧을 때 (N이 작음)

O(N) vs O(1) 차이가 크지 않음.

skip 길이가 작으면 Set 변환 비용이 더 클 수도 있음.
(Set(skip) 과정이 추가되기 때문)

Set 변환 자체가 비용이 든다

Set(skip) 과정이 String.contains()보다 더 비쌀 가능성이 있음.

Set이 유리한 경우

skip 길이가 길 때 (N이 클 때)

Set을 사용하면 contains 연산이 빨라져 성능이 좋아짐.

contains 연산을 여러 번 호출할 때

Set은 O(1),
String.contains는 O(N)이므로 차이가 커짐.

🎯 결론

1. skip 길이가 짧다면?
   → Set 변환 비용이 더 크므로 String.contains를 그대로 사용하는 것이 낫다.

2. skip 길이가 길거나 contains를 여러 번 호출해야 한다면?
   → Set을 활용하는 것이 훨씬 빠르다.

일반적으로 skip 길이가 10~15 이상이면 Set이 유리함.

이렇게 확인하고 나서 문제 조건을 다시 보니

1 ≤ skip의 길이 ≤ 10

👉 이 문제에서는 skip 길이가 최대 10이므로 Set 변환 없이 String.contains($0)을 사용하는 것이 더 적절하다! 🚀