괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
문제점
- 재귀를 사용해서 풀었는데 결과값이 자꾸 undefined가 나와서 헤맸다.
function solution(s){
if (s.includes('()')){
let listString = s.split("()").join("");
if (listString.length == 0){
return true;
}else{
solution(listString)
}
}else{
return false;
}
}- 위에 문제를 해결했는데 효율성검사에서 탈락했다.
시도해본 것
- 여러군데 콘솔로그 찍어보고 함수 시작하자마자 체크 해보기도했다..
해결 방법
- 7번째 줄에 return을 안해줘서 안됐다
function solution(s){
if (s.includes('()')){
let listString = s.split("()").join("");
if (listString.length == 0){
return true;
}else{
return solution(listString)
}
}else{
return false;
}
}- 다른사람이 스택으로 푼 코드를 보고 새로 짜봤는데 신선했다..
function solution(s){
let cnt = 0
for (i=0; i<s.length; i++){
if (s[i] == '('){
cnt++;
}else{
cnt--;
}
if (cnt < 0){
return false;
}
}
return cnt == 0 ? true : false
}오늘 배운것
Nest.JS
데코레이터 밑에는 꾸며주는 함수나 클래스가 무조건 붙어있어야한다. 한줄이상 띄어쓰면 안됨
알고리즘
- 재귀를 쓸 때 리턴을해주자..
- split과 join을 순차적으로 쓰면 다시 바로 붙일 수 있다. 물론 따로 써도된다.
- 3항 연산자를 시도해봤는데 1번처럼 썼는데 오류가나길래 2번으로 수정했더니 잘 됐다.
[1] cnt == 0 ? return true : return false
[2] return cnt == 0 ? true : false
- 스택을 사용해서 푸는 문제라고 했는데 도무지 감이 잡히지않아서 스플릿으로 제거하면서 재귀로 풀어봤는데, 시간초과가 뜨고 생각해보니까 ((((((((((((((((((((((((((((())))))))))))))))))))))))))))))) 이런식으로 겹쳐있으면 너무 시간이 오래걸리고 겹쳐있지 않더라도 인클루드, 스플릿, 조인하는데 문자열이 길다면시간이 너무많이 소모된다고 생각이든다. 스택을 사용한 코드는 "(" 로 반드시 시작해야하며 ")"와 반드시 한쌍이어야 함을 힌트삼아서 작성했다.
순서대로 탐색했을때 ()) 이런식으로 ")"가 더많은 순간 false를 반환해주기 때문에 처음 코드보다 훨씬 시간이 단축됨을 느꼈다. 그러나 같은코드임에도 시간초과가 뜰 때도 있다..