programmers.co.kr/learn/courses/30/lessons/60058?language=swift
코딩테스트 연습 - 괄호 변환
카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를
programmers.co.kr
괄호는 "(" 로 열리고 ")" 닫혀야 완전하다고 부른다. 이 개념을 이용해서 올바르지 않은 괄호 문자열을 올바른 괄호 문자열로 바꿔주는 로직을 짜보는 문제이다.
pseudo code로 짜져있는 것을 보고 코드로 그대로 옮겨줘도 문제 없이 풀린다!
굳이 추가적인 생각을 하지 않고 풀어도 된다는 것.
근데 처음에는 그런거 모르고 헤맸다...
// pseudo code
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
예시를 두고 케이스를 이해해보자.
| p |
| ()))((() |
p를 원래 문자열이라고 두고 보자.
1) 문자열이 비어있지 않으므로 pass
2) 문자열을 u,v로 분리해주어야한다.
> u는 균형이 잡혀 있어야 한다. 즉 "("의 개수와 ")"의 개수가 같아야 한다는 것이다.
| u | v |
| () | ))((() |
먼저 u에 "("가 붙고 그 다음에 바로 ")"가 붙어서 한 쌍이 생겨 균형이 잡힌 문자열이 되는 것이다.
해당 부분을 먼저 코드로 구현해두자.
func divide(_ p: String) -> [String] {
var cnt = 0
var u = ""
var v = ""
for i in 0..<p.count {
let str = p[p.index(p.startIndex, offsetBy: i)]
cnt += str == "(" ? 1 : -1
if cnt == 0 {
u = String(p.prefix(i+1))
v = String(p.suffix(p.count-i-1))
break
}
}
return [u,v]
}3) u가 올바른 괄호 문자열이라면? solution(v)를 해주어야 한다.
> 즉 v에 대해서 1번으로 돌아가라는 말이다 -> 여기서 재귀적인 개념이 쓰이게 되는 것이다.
3-1) 수행한 문자열을 u에 붙이라고 했으니 u + solution(v) 를 리턴해주면 된다.
4) u가 올바르지 않은 괄호 문자열이라면?
4-1) 빈 문자열(ans)에 "("를 더해주고
4-2) solution(v)를 또 더해주고
4-3) ")"를 붙여 닫아주고
4-4) u의 첫, 끝 문자들을 제거하고 나머지 문자들을 반대로 해서 붙여준다.
4-5) 그리고 반환
> 즉 "(" + "solution(v)" + ")" + "수정된 u"를 반환해야 한다.
3,4번 과정에 이전에 u가 올바른 괄호 문자열인지를 판단해줄 필요가 있다. 이 부분도 코드로 보자.
func ucheck(_ u: String) -> Bool {
var cnt = 0
for str in u {
if cnt < 0 { return false }
cnt += str == "(" ? 1 : -1
}
return cnt == 0
}(대학시절 생각나는 u-check... 짓다보니 그냥 ucheck로...)
이제 핵심 부분인 solution 부분을 짜면 된다!
func solution(_ p:String) -> String {
var ans = ""
if p.isEmpty { return "" }
var u = divide(p)[0]
var v = divide(p)[1]
if ucheck(u) {
return u + solution(v)
} else {
ans += "("
ans += solution(v)
ans += ")"
u.removeFirst()
u.removeLast()
for str in u {
ans += str == "(" ? ")" : "("
}
return ans
}
}
정말 말 그대로 코드를 짰다.
빈 배열을 만들어두고 1번의 케이스도 미리 예외 처리 해두었다.
u와 v를 나누는 2번 테스크를 진행하고, 3번의 bool type 값에 따라 수행된다.
자세한 프로세스는 위 부분 참고하여 예시를 마저 풀이해보자.
2번(분리)까지 했다고 하고 위 케이스에서 u는 현재 "()"로 올바른 배열이니 solution(v)를 해주면 된다.
즉 다시 v를 u와 v로 나누면 된다는 것.
| u | v |
| ))(( | () |
u의 상태가 어때보이는가?
균형만 맞고 올바른 괄호 문자열이라고는 보기가 어렵다.
자 이제 4번으로 이동하면 된다!
| u | ans |
| () | ( + solution(v) + ) |
현재까지는 이전의 u + ans + u가 되는 것이다.
ans안의 solution(v)를 구해보자. 현재 v는 "()"
2번의 과정을 거치면 아래와 같은 결과가 나온다
| u | v |
| () | - |
여기서 u는 올바른 문자열이 되어 u + solution(v)를 반환해주면 되는데, v가 빈 문자열이라 빈 문자열 그대로 반환해주면 된다.
즉, ans의 solution(v)에 들어갈 값은 "()"이다.
아까전에 "이전의 u + ans + u"라고 했었는데 이를 실제 값으로 보면
"() + (()) + ()"가 된다!
그래서 답은 "()(())()"가 되는 것 이다!
- point
: 기능을 분리해서 구현
: 재귀
import Foundation
func solution(_ p:String) -> String {
var ans = ""
if p.isEmpty { return "" }
var u = divide(p)[0]
var v = divide(p)[1]
if ucheck(u) {
return u + solution(v)
} else {
ans += "("
ans += solution(v)
ans += ")"
u.removeFirst()
u.removeLast()
for str in u {
ans += str == "(" ? ")" : "("
}
return ans
}
}
func divide(_ p: String) -> [String] {
var cnt = 0
var u = ""
var v = ""
for i in 0..<p.count {
let str = p[p.index(p.startIndex, offsetBy: i)]
cnt += str == "(" ? 1 : -1
if cnt == 0 {
u = String(p.prefix(i+1))
v = String(p.suffix(p.count-i-1))
break
}
}
return [u,v]
}
func ucheck(_ u: String) -> Bool {
var cnt = 0
for str in u {
if cnt < 0 { return false }
cnt += str == "(" ? 1 : -1
}
return cnt == 0
}