여러 방법으로 풀어보는 것에 집중한 문제
문제: 스택/큐 - 올바른 괄호
| 문제 링크 |
|---|
 |
import Foundation
func solution(_ s:String) -> Bool
{
var ans:Bool = false
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("Hello Swift")
return ans
}접근법 1
문제 접근
import Foundation
func solution(_ s: String) -> Bool
{
guard s.first == "(" && s.last == ")" else { // 조건 1: Early Exit - '('로 시작해서 ')'로 끝나야 한다.
return false
}
var leftBracketCount = 0, rightBracketCount = 0
for char in s {
if char == "(" {
leftBracketCount += 1
} else {
rightBracketCount += 1
}
}
return leftBracketCount == rightBracketCount // 조건 2: '('와 ')'의 각 개수는 같다.
}고려한 조건
조건 내용 조건 1 Early Exit - '('로 시작해서 ')'로 끝나야 한다. 조건 2 '('와 ')'의 각 개수는 같다.
| 일부 테스트에서 오류 |
|---|
 |
반례
입력값 기댓값 "())(()"false
수정한 조건
조건 내용 조건 2' '('에는 대응하는 ')'가 있어야 한다.
문제 해결
import Foundation
func solution(_ s: String) -> Bool
{
guard s.first == "(" && s.last == ")" else { // 조건 1 : Early Exit - '('로 시작해서 ')'로 끝나야 한다.
return false
}
var bracketMatchingCount = 0
for char in s {
guard bracketMatchingCount >= 0 else { return false } // Early Exit (조건 2')
if char == "(" {
bracketMatchingCount += 1
} else if char == ")" {
bracketMatchingCount += -1
}
}
return bracketMatchingCount == 0 // 조건 2': '('에는 대응하는 ')'가 있어야 한다.
}테스트 결과:
통과 (메모리: 16.4 MB, 시간: 5.29 ms)
접근법 2
문제 접근
import Foundation
func solution(_ s: String) -> Bool
{
guard s.first == "(" && s.last == ")" else { return false } // Early Exit
var _s = s
repeat {
_s.replace(of: "()", with: "")
} while _s.contains("()")
return _s == ""
}// 테스트 결과 /Solution/Sources/Solution/Solution.swift:10:13: error: value of type 'String' has no member 'replace' _s.replace("()", with: "") ~~ ^~~~~~~
Playground에서는 멀쩡히 잘 돌아가는 코드인데 해당 사이트에서는 String이 replace 메서드를 가지고 있지 않다고 한다. replacingOccurrences를 사용하면 되겠지만, 사용해봤더니 문자열을 일일히 반환해서 그런지 효율성 테스트를 통과하지 못했다.
무척 의문이지만, String 공식 문서를 살펴봤더니replacingOccurrences 메서드만 있고 replace 메서드는 보이지 않는다:
replace 메서드를 공식 문서에서 찾아보니 대상이 RangeReplaceableCollection이거나, SubSequence가 Substring일 때만 가능하다고 한다. 분명 String도 이에 포함될 것으로 보인다:
- Collections/Sequence and Collection Protocols/RangeReplaceableCollection/replace(_:with:maxReplacements:)
- Foundation/Numbers, Data, and Basic Values/Data/replace(_:with:maxReplacements:)
그럼에도 불구하고 해당 사이트에서 코드가 작동하지 않는 이유는, 추측하기에 다음과 같다:
- Swift의 정규식 활용
Swift 5.7 이상에서는 기본적으로 정규 표현식(Regex)을 지원하며, 이를 통해 문자열의 특정 패턴을 효율적으로 처리할 수 있다. 하지만 이 기능은 일부 코딩 테스트 플랫폼에서는 사용할 수 없는 경우가 많다.
- 제네릭 및 RegexComponent
Swift의 RegexComponent는 정규식을 기반으로 한 타입이다. 이를 활용하면 매우 강력한 문자열 처리가 가능하지만, 복잡도가 높아질 수 있다. 또한, 이런 고급 기능은 코딩 테스트 플랫폼에서 지원되지 않을 가능성이 크다.
이 접근법에서는 이 정도의 인사이트만 얻도록 하고, 다른 접근법을 찾아보기로 했다.
접근법 3
문제 접근
import Foundation
func solution(_ s: String) -> Bool
{
guard s.first == "(" && s.last == ")" else { return false } // Early Exit
var stack: [Character] = [] {
didSet {
if oldValue.last == "(" && stack.last == ")" {
stack.removeLast()
stack.removeLast()
}
}
}
for char in s {
stack.append(char)
}
return stack.isEmpty
}스택 구조를 활용하기 위해 배열과 프로퍼티 옵저버를 사용해봤지만, 효율성 테스트를 통과하지 못했다.
| 효율성 테스트 통과 실패 |
|---|
 |
문제점으로 보이는 것들:
1. stack의 잦은 didSet 호출:stack의 모든 변경마다 동작함
2. 배열의 동적 크기 증가:stack의 capacity가 초과될 때마다 메모리가 할당됨
문제 해결
import Foundation
func solution(_ s: String) -> Bool
{
guard s.first == "(" && s.last == ")" else { return false } // Early Exit
var stack: [Character] = []
stack.reserveCapacity(s.count)
for char in s {
if char == ")" && stack.last == "(" {
stack.removeLast()
} else {
stack.append(char)
}
}
return stack.isEmpty
}테스트 결과:
통과 (메모리: 16.6 MB, 시간: 24.16 ms)
What I've learned:
Array의 capacity를 미리 할당하는 법
미리 할당 후 값 수정
Array(repeating:count:) 초기화를 통해 배열을 미리 초기화한 뒤 특정 인덱스에 값을 할당할 수 있다.
var array = Array(repeating: 0, count: 10)
// 인덱스 0과 1의 값 수정
array[0] = 5
array[1] = 10
// 결과: [5, 10, 0, 0, 0, 0, 0, 0, 0, 0]
print(array)Array의 크기만 고정하고 값을 나중에 채우기
초기값이 필요 없다면, Swift에서 기본적으로 특정 용량(capacity)을 가진 배열을 만들 수는 없지만, 대신 reserveCapacity를 사용할 수 있다. 이는 배열의 용량을 미리 예약해 추가적인 메모리 할당을 줄여준다.
var array: [Int] = []
array.reserveCapacity(10)
// 용량 예약 후 값을 추가
array.append(1)
array.append(2)
// 용량은 10으로 예약되었으나, 실제 크기는 2
print(array) // [1, 2]reserveCapacity를 사용하면 실제 배열의 크기를 고정하지는 않지만, 배열의 성능을 최적화하는 데 도움이 된다.
정리
- 배열의 고정된 초기값이 필요할 때는
Array(repeating:count:)사용. - 성능 최적화를 위해 많은 추가 작업이 예상되면
reserveCapacity사용.
