[230419] 괄호 회전하기

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

 

 

풀이

첫 풀이 (실패)

아.. 생각이 안 떠올라서.. 코드 더럽게 노가다로 짜긴 했는데..

function solution(s) {
    if(s.length % 2 === 1) return 0;
    
    let answer = 0;
    
    for(let i = 0; i < s.length; i++) {
        let A = 0;
        let B = 0;
        let C = 0;
        for(let j = 0; j < s.length; j++) {
            const idx = (i + j) % s.length;
             
            if(s[idx] === '(') A++;
            if(s[idx] === '[') B++;
            if(s[idx] === '{') C++;
            if(s[idx] === ')') A--;
            if(s[idx] === ']') B--;
            if(s[idx] === '}') C--;
            
            if(A < 0 || B < 0 || C < 0) break;
        } 
        if(A !== 0 || B !== 0 || C !== 0) continue;
        answer++;
    }
    return answer;
}

일단 이렇게 푸니까, 테스트 14에서 실패한다.

도움을 구하고자 질문하기의 힘을 빌리니까 아래와 같다고 함.

 

 

그리고 약간의 검색의 힘을 빌려보니 (…)

자료구조 스택을 이용해서 푸는 것이 정석이라 한다.

 

 

 

스택으로 풀기

🧸 스택으로 풀기

1. ([{ 가 나오면 모두 스택에 넣고,
2. )]} 가 나오면 스택의 제일 위에 있는 놈의 짝인지 본다.
3. 짝이면 pop! 아니면 continue;

 

function solution(s) {
    if(s.length % 2 === 1) return 0;
    
    let answer = 0;
    
    for(let i = 0; i < s.length; i++) {
        if(check(s, i)) answer++;
    }
    return answer;
}

const check = (s, i) => { 
    const stack = [];
        
    for(let j = 0; j < s.length; j++) {
        const idx = (i + j) % s.length;  
        if('({['.includes(s[idx])) {
            stack.push(s[idx]);
        } else {
            if(!stack.length) return false;

            const last = stack[stack.length - 1]; 
            if((last === '(' && s[idx] === ')') || (last === '{' && s[idx] === '}') || (last === '[' && s[idx] === ']')) {
                stack.pop();  
            }
            else return false;
        }
    } 
    if(stack.length === 0) return true;
}

 

 

다른 풀이

다른 풀이를 봤을 때 모두 스택을 접근한 것은 동일했다.

다만 풀이 방법에서 차이가 있을 뿐이었다.

function solution(s) {
	if(s.length % 2 === 1) return 0;

	let answer = 0;
	const mapping = { "}" : "{", "]" : "[", ")" : "("};

	for(let i = 0; i < s.length; i++) {
		const stack = [];
		const rotate = s.slice(i) + s.slice(0, i);
		**let flag = true;** 

		for(let j = 0; j < s.length; j++) {
			if(rotate[j] === "[" || rotate[j] === "(" || rotate[j] === "{" )
          stack.push(rotate[j]);
      **else {
          const last = stack.pop();
          if(last !== mapping[rotate[j]]) {
              flag = false
              break;
          }
      }
			if(flag) answer++;**
	}
	return answer;
} 

flag를 두고 false일 때 break하는 방법도 괜찮아보인다.

또 어차피 짝이 안맞으면 다음 턴으로 넘길테니 stack.pop해서 꺼내버리는 방법이 더 좋은 것 같다.

object table을 만들어서 바로 짝이 맞는지 확인하는 방법도 훨씬 깔끔하다.

 

 

 

 

 

---

참고 자료

https://velog.io/@munang/프로그래머스괄호-회전하