오늘은 백준 3986 - 좋은 단어 문제를 풀었습니다.
처음에는 어려워 보였지만, 시간을 두고 천천히 고민한 결과 해결할 수 있었습니다.
❌ 첫 번째 시도: 인덱스 기반 접근
처음에는 인덱스를 활용한 방법을 시도했습니다:
- 바로 옆의 문자가 같으면 패스
- 아니면 짝수 번째 인덱스들을 검사
하지만 이 방법은 복잡도가 높고 구현이 어려웠습니다.
🔍 해결 방법 탐색: 스택 활용
어제 99클럽 온라인 특강에서 배운 스택 자료구조를 떠올렸고, 이를 활용한 해결책을 찾았습니다.
func isBeautyNums(_ target: String) -> Bool {
guard target.count % 2 == 0 else { return false }
var targetArray = target.map { String($0) }
let aCountsIsEven = targetArray.filter { $0 == "A" }.count % 2 == 0
guard aCountsIsEven else { return false }
var stack = [String]()
for char in targetArray {
if char == stack.last {
stack.removeLast()
} else {
stack.append(char)
}
}
return stack.isEmpty
}이 방법은 스택을 사용하여 짝을 이루는 문자를 효율적으로 처리할 수 있었습니다.
✅ 최적화된 해결책: 스택 사용
스택을 사용하여 문제를 해결하니 코드가 훨씬 단순하고 명확해졌습니다.
우선 짝이 맞아야 하니 문자열의 길이가 짝수여야 하고, A 문자도 짝수여야 합니다.
전체가 짝수고 A가 짝수면 B도 짝수이니 B에 대한 검증은 하지 않아도 되겠죠.
이런 생각을 하면서 문제를 풀어가니, 마치 퍼즐을 맞추는 기분이었습니다.
⏱ 시간 복잡도 분석
이 알고리즘의 시간 복잡도를 분석해보면 다음과 같습니다:
count는 O(1)입니다. 이는 배열의 길이를 가져오는 연산으로, 상수 시간에 수행됩니다.filter는 O(n)입니다. 이는 배열의 각 요소를 검사하기 때문에 입력 크기 n에 비례합니다.for문은 O(n)입니다. 이는 배열의 각 요소를 순회하기 때문에 입력 크기 n에 비례합니다.append와removeLast()는 O(1)입니다. 이는 스택의 끝에 요소를 추가하거나 제거하는 연산으로, 상수 시간에 수행됩니다.
결국 이 알고리즘의 전체 시간 복잡도는 가장 높은 차수의 연산인 O(n)입니다.
🎓 오늘의 교훈
- 문제 해결 시간 관리의 중요성
- 처음에 바로 풀지 않고 시간을 두고 고민한 것이 좋은 결정이었습니다.
- 중간중간 생각할 시간을 가지니 더 좋은 해결책이 떠올랐습니다.
- 자료구조의 활용
- 스택이라는 자료구조를 떠올리니 복잡해 보이던 문제가 단순해졌습니다.
- 어제 배운 내용을 오늘 활용할 수 있어서 좋았습니다.
- 단순화의 힘
- 처음에는 복잡한 인덱스 계산을 시도했지만
- 스택을 사용하니 코드가 훨씬 단순하고 명확해졌습니다.
iOS 개발자입니다.