🔗 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12909
✅ 풀이
'(' 문자와 ')' 문자가 쌍을 이루어야 하는 문제이다. Stack 자료구조를 사용해서 문제를 풀어야겠다는 생각이 바로 들었다.
⌨️ 첫번째 풀이
func solution(_ s:String) -> Bool {
var ans:Bool = false
var stack: [String] = []
let characters: [Character] = Array(s)
for i in characters {
if i == "(" {
stack.append("(")
} else if i == ")" {
if stack.isEmpty {
ans = false
return ans
} else {
stack.removeLast()
}
}
}
return stack.isEmpty
}Level2 인데 생각보다 쉽네 하면서 Stack 역할을 하는 배열과 문자열 S를 각 단어씩 분리된 characters 배열을 선언해주었다.
왜인지 모르겠지만 split() 메서드를 사용할 때 오류가 발생했고 띄어쓰기가 없는 문자열을 하나씩 분리할때는 다음과 같은 방법으로 손쉽게 분리가 가능했다.
자 이제 우리가 자주 사용했던 Stack 방법을 사용할 차례다!
'(' 문자면 stack에 넣어주고 ')' 문자면 먼저 stack에 값이 있는지 확인하고 '(' 가 stack 에 있어야 하는데 stack 이 비어있다면 순서가 잘못됐기 때문에 false 를 반환시킨다.
만약 값이 있다면 '(' 가 stack 에 있다는 의미이기 때문에 가장 나중에 들어온 값을 제거한다.
그렇게 모든 문자에 대해 과정을 마치고 났는대도 stack 배열에 값이 남아있다면 두개의 문자가 짝을 이루지 않았다는 의미이기 때문에 비어있다면 true 를, 값이 있다면 false 를 반환한다.
😭 왜 틀리는 거지..?
완벽하게 풀었다고 자신만만했는데... 잉 이게 뭐지?
정확성 테스트에서는 모두 통과했지만 효율성 테스트에서는 시간초과가 났다....
왜 이런.. 상황이 벌어지는지.. 이해를 할 수 없었고... 도저히 다른 방법이 생각이 안나 다른 풀이 방법을 보며 조금이나마 해결을 해보았다....
⌨️ 두번째 풀이
func solution(_ s:String) -> Bool
{
var result = 0
let characters: [Character] = Array(s)
for i in characters {
if i == "(" {
result += 1
} else if i == ")" {
result -= 1
}
if result < 0 {
return false
}
}
if result != 0 {
return false
}
return true
}
선언된 변수의 수도 줄어들었고 깔끔해졌다!
입력받은 문자열 S 에 대해서 문자 한개씩 분리 시키는 건 똑같지만 올바른 입력이 됬는지 확인하는 방법이 달라졌다
첫번째는 stack 역할을 하는 배열을 사용하지 않았다.
입력한 문자를 배열에 넣고 빼는 과정을 없애 시간을 줄일 수 있었던거 같다....
두번째는 없어진 stack 을 대신하여 단순히 Int 형 변수을 통해 올바르게 입력되었는지 확인했다.
'('이 들어오면 +1, ')' 이 들어오면 -1 을 하게 되고 만약 result 가 0보다 작으면 ')' 이 먼저 입력이 되었다는 뜻이고 순서가 잘못됐기 때문에 바로 false 를 return 한다.
만약 모든 입력이 다 끝났고 result 가 0이 아닌 경우에는 열고 닫는 문자가 올바르게 짝이 이루어지지 않았다는 것을 의미하기 때문에 false, 0이라면 true 를 반환하도록 했다.
실제 코테를 볼때는 테스트 케이스에 대해서만 통과하는지 확인을 할 수 있어서 효율성 테스트에 대해 확인할 수 없지만...
만약 다음과 같이 간단하게 확인하는 과정이라면 stack 배열로 사용하기 보다 더욱 간단한 방법을 통해 풀어야겠다는 생각이 든다...
이래서... level 2 인가보다......
