문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()"는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
제한사항
| s | answer |
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
풀이
스택&큐 파트의 문제
효율성 검증 테스트가 등장한다.
이런저런 방법으로 많이 풀어봤는데 항상 시간 초과가 계속 발생해서 머리 굴려가면서 풀었는데,
최종적으로 풀어서 성공한 방식도 결국 스택은 아니었다.ㅋㅋ
첫 번째 오답
const solution = (s) => {
let open = {
opened: false,
count: 0
}
for(let i = 0; i < s.length; i ++){
if([...s][i] === "("){
open.opened = true;
open.count ++;
}else{
if(open.opened){
open.count --;
if(open.count === 0){
open.opened = false;
}
}else{
return false;
}
}
}
if(open.opened) return false;
else return true;
}for문으로 문자열을 순회하며 괄호를 확인하는 방식이었다.
문자열 s를 순회하면서 문자열을 조작하고 있다. 문자열 조작은 시간 복잡도가 O(n)이므로,
결국 전체 시간 복잡도는 O(n**2)가 되어 효율성 테스트에서 실패하게 된다.
(매번 반복문마다 문자열 s를 배열로 치환해 가면서 조작함.)
효율성 테스트 결과는 둘 다 실패
두 번째 오답
const solution = (s) => {
let result = s;
let count = 0;
if(s.length % 2 !== 0) return false;
while(true){
count ++;
if(result[0] === ")" || result[result.length - 1] === "(") return false;
result = result.replace(/(\(\))/g, "")
if(result === "") return true;
}
return true
}이번엔 문자열을 result로 저장하는 영특함을 보여줬지만, 결국 while문 안에서 문자열을 정규식으로 치환한다.
결국 또 O(n**2)
효율성 테스트는 둘 다 실패
세 번째 오답
const solution = (s) => {
let result = s;
let count = 0;
if(s.length % 2 !== 0) return false;
const charLength = [...result].reduce((acc, cur) => {
if(cur === "(") acc.open += 1;
else acc.close += 1;
return acc;
}, {
"open": 0,
"close": 0
})
if(charLength.open !== charLength.close) return false;
while(true){
count ++;
if(result[0] === ")" || result[result.length - 1] === "(") return false;
result = result.replace(/(\(\))/g, "")
if(result === "") return true;
}
return true
}이번엔 내가 사랑하는 reduce()를 이용해 보았다.
결론부터 말하자면 결과는 실패, 통과 -> 하나만 통과했다.
while문 내부에서 또 문자열의 치환을 했기 때문에,
O(n**2)가 되어 효율성 테스트에서 실패했다.
하나는 통과한 이유는 뭐지?
아마 초반부에 )로 시작하거나, (로 끝나는 것들을 제외시키고,
(와 )의 개수가 맞지 않는 경우를 미리 처리하는 부분에서 통과된 거 같다.
그 외 반복 과정에서는 실패한 듯.
네 번째 오답
const solution = (s) => {
const result = [...s].reduce((acc, cur) => {
if(cur === "("){
acc.isOpen = true;
acc.openCount ++;
}else{
if(!acc.isOpen) return false;
else {
acc.openCount --;
if(acc.openCount === 0) acc.isOpen = false;
}
}
return acc;
},{
isOpen: false,
openCount: 0,
})
if(!result.isOpen && result.openCount === 0) return true;
else return false;
}아무리 생각해도 while문이 문젠거 같아 while 문을 제거했다.
대신 reduce()로, s문자열을 순회해 가면서 isOpen과 openCount를 이용했다.
이 코드 같은 경우엔 효율성은 O(n)인데 결과는 실패, 통과
아니 대체 왜?.. 모르겠다. 하지만 전체적인 원리는 스택을 사용한 풀이법과 점점 가까워지고 있다.
다섯 번째 - 정답
const solution = (s) => {
let openCnt = 0;
for(let i = 0; i < s.length; i ++){
if(s[i] === "(") openCnt ++;
else openCnt --;
if(openCnt < 0) return false;
if(i === s.length - 1 && openCnt !== 0) return false;
}
return true;
}reduce()를 포기했다. 또 isOpen도 굳이 알 필요가 없을 것 같아서,
그냥 openCnt(괄호가 열린 횟수) 만을 판단했고,
( 라면 열린 횟수를 올려주고, 그게 아니라면 빼줬다.
그다음 openCnt가 음수값이 되면 false를 리턴해주었다.
최종적으로 ( 로 끝나게 되면 return false가 안되어서
i === s.length, 마지막 원소이면서 openCnt가 0이 아닌 경우 (열린 게 안 닫힌 경우)
false를 리턴해주었다.
시간 복잡도는 O(n)으로 둘 다 통과했.. 지만 스택을 이용한 풀이가 아니어서 쫌 찜찜했는데,
추후 스택 부분을 따로 학습 후 적용해 보니 원리는 거의 같았다.
그냥 배열을 썼냐 안 썼냐.. 그 정도 차이?
후속 처리 - 스택을 이용한 풀이
const solution = (s) => {
let result = [];
for(let i = 0; i < s.length; i ++){
if(s[i] === "(") result.push("(")
else
if(result.length === 0) return false;
else result.pop();
}
return result.length === 0;
}배열을 하나 만들고, ( 는 추가하고, ) 일 때는 배열에서 (를 pop()으로 빼준다. (후입선출)
) 일때 result의 개수가 0개가 아니면 false를 리턴해준다,
마지막으로 result 배열의 길이가 0인지를 판단해서 리턴.
근데 스택이라는 게.. 꼭 배열을 써야 하는 게 아니고
그냥 추상적인 - 후입선출의 요소 추가와 요소 제거 부분을 구현한다면 스택이라고 하는 것 같다.
그러니까, 정리해 보면 스택은 후입선출
큐는 선입선출이라고 생각하면 될 거 같고,
굳이 배열이 아니더라도, 그 개념을 구현할 수 있다면 스택/큐라고 부르는 듯
비전공자는 이렇게 또 하나 알아간다.
