[프로그래머스] 괄호 회전하기

문제 주소

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 1 이상 1,000 이하입니다.

입출력 예

s result

"{}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

입출력 예 설명

입출력 예 #1

다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

0	"{}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}"	O
5	"}{"	X

올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"{}"	O
5	"{}]()["	X

올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

※ 공지 - 2021년 4월 16일 테스트케이스가 추가되었습니다.

제출 코드

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        
        for(int i = 0; i<s.length(); i++){
            
            Stack<Character> stack = new Stack<Character>();
            
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            boolean noReverse = true;
            
            for(int j = 0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                
                if(c=='('||c=='{'||c=='['||stack.size()==0){
                    stack.push(c);
                }else{
                    char pop = stack.pop();
                    
                    if(c==')'){
                        if(pop!='('){
                            noReverse=false;
                            break;
                        }
                    }else if(c==']'){
                        if(pop!='['){
                            noReverse=false;
                            break;
                        }
                    }else if(c=='}'){
                        if(pop!='{'){
                            noReverse=false;
                            break;
                        }
                    }
                }
            }
            if(noReverse == true && stack.size() == 0){
                answer++;
            }

        }
        return answer;
    }
}

풀이 과정

회전의 의미 : 왼쪽으로 민다

올바른 괄호 문자열이 괄호가 열리면 닫혀야 하는거네

s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        boolean roundR = false;
        boolean roundL = false;
        boolean squareR = false;
        boolean squareL = false;
        boolean curlyR = false;
        boolean curlyL = false;
        boolean allOk = true;
        //R이 L보다 먼저 나오면 일단 망한거

        for(int i=0; i<s.length(); i++){
            //왼쪽으로 밀어보자
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            for(int j=0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                if(c == '('){
                    if(roundR==true){
                        allOk=false;
                        break;
                    }
                    roundL = true;
                }else if(c == '['){
                    if(squareR==true){
                        allOk=false;
                        break;
                    }
                    squareL = true;
                }if(c == '{'){
                    if(curlyR==true){
                        allOk=false;
                        break;
                    }
                    curlyL = true;
                }if(c == ']'){
                    squareR=true;
                }if(c == ')'){
                    roundR=true;
                }if(c == '}'){
                    curlyR=true;
                }
            }
            if(allOk==true){
                answer++;
            }
            
        }
        return answer;
    }
}

테스트 1
입력값 〉	"[](){}"
기댓값 〉	3
실행 결과 〉	실행한 결괏값 1이 기댓값 3과 다릅니다.
테스트 2
입력값 〉	"}]()[{"
기댓값 〉	2
실행 결과 〉	실행한 결괏값 0이 기댓값 2과 다릅니다.
테스트 3
입력값 〉	"[)(]"
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 4
입력값 〉	"}}}"
기댓값 〉	0
실행 결과 〉	실행한 결괏값 3이 기댓값 0과 다릅니다.

생각해보니 초기화를 안 한거 같아서

큰 for문 끝나고 false다 넣으려다가 걍

지역변수로 바꿔봄

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        
        //R이 L보다 먼저 나오면 일단 망한거

        for(int i=0; i<s.length(); i++){
            
            boolean roundR = false;
            boolean roundL = false;
            boolean squareR = false;
            boolean squareL = false;
            boolean curlyR = false;
            boolean curlyL = false;
            boolean allOk = true;
            //왼쪽으로 밀어보자
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            for(int j=0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                if(c == '('){
                    if(roundR==true){
                        allOk=false;
                        break;
                    }
                    roundL = true;
                }else if(c == '['){
                    if(squareR==true){
                        allOk=false;
                        break;
                    }
                    squareL = true;
                }if(c == '{'){
                    if(curlyR==true){
                        allOk=false;
                        break;
                    }
                    curlyL = true;
                }if(c == ']'){
                    squareR=true;
                }if(c == ')'){
                    roundR=true;
                }if(c == '}'){
                    curlyR=true;
                }
            }
            if(allOk==true){
                answer++;
            }
            
        }
        return answer;
    }
}

테스트 1
입력값 〉	"[](){}"
기댓값 〉	3
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	"}]()[{"
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
테스트 3
입력값 〉	"[)(]"
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 4
입력값 〉	"}}}"
기댓값 〉	0
실행 결과 〉	실행한 결괏값 3이 기댓값 0과 다릅니다.

테스트 4가 반례네….

코드 전면 뜯어고쳐야 할듯 ㅎㅎ…

int로 세는 아이디어 해봄

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        
        //R이 L보다 먼저 나오면 일단 망한거

        for(int i=0; i<s.length(); i++){
            
            int roundR = 0;
            int roundL = 0;
            int squareR = 0;
            int squareL = 0;
            int curlyR = 0;
            int curlyL = 0;
            boolean allOk = true;
            //왼쪽으로 밀어보자
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            for(int j=0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                if(c == '('){
                    if(roundL<=roundR){
                        allOk=false;
                        break;
                    }
                    roundL++;
                }else if(c == '['){
                    if(squareL<=squareR){
                        allOk=false;
                        break;
                    }
                    squareL++;
                }if(c == '{'){
                    if(curlyL<=curlyR){
                        allOk=false;
                        break;
                    }
                    curlyL++;
                }if(c == ']'){
                    squareR++;
                }if(c == ')'){
                    roundR++;
                }if(c == '}'){
                    curlyR++;
                }
            }
            if(allOk==true){
                answer++;
            }
            
        }
        return answer;
    }
}

테스트 1
입력값 〉	"[](){}"
기댓값 〉	3
실행 결과 〉	실행한 결괏값 0이 기댓값 3과 다릅니다.
테스트 2
입력값 〉	"}]()[{"
기댓값 〉	2
실행 결과 〉	실행한 결괏값 0이 기댓값 2과 다릅니다.
테스트 3
입력값 〉	"[)(]"
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 4
입력값 〉	"}}}"
기댓값 〉	0
실행 결과 〉	실행한 결괏값 3이 기댓값 0과 다릅니다.

=을 포함시키면 0일때 걍 다 break되니까 =을 빼봄

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        
        //R이 L보다 먼저 나오면 일단 망한거

        for(int i=0; i<s.length(); i++){
            
            int roundR = 0;
            int roundL = 0;
            int squareR = 0;
            int squareL = 0;
            int curlyR = 0;
            int curlyL = 0;
            boolean allOk = true;
            //왼쪽으로 밀어보자
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            for(int j=0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                if(c == '('){
                    if(roundL<roundR){
                        allOk=false;
                        break;
                    }
                    roundL++;
                }else if(c == '['){
                    if(squareL<squareR){
                        allOk=false;
                        break;
                    }
                    squareL++;
                }if(c == '{'){
                    if(curlyL<curlyR){
                        allOk=false;
                        break;
                    }
                    curlyL++;
                }if(c == ']'){
                    squareR++;
                }if(c == ')'){
                    roundR++;
                }if(c == '}'){
                    curlyR++;
                }
            }
            if(allOk==true){
                answer++;
            }
            
        }
        return answer;
    }
}

if(allOk==true){
                answer++;
            }

테스트 4
입력값 〉	"}}}"
기댓값 〉	0
실행 결과 〉	실행한 결괏값 3이 기댓값 0과 다릅니다.

저부분이 테스트4를 검증할 수 있도록 바뀌어야 할듯

            if(allOk==true){
                if((roundR==roundL)&&(squareL==squareR)&&(curlyL==curlyR)){
                    answer++;
                }
            }

이렇게 검증해봄

테스트 1 〉 통과 (15.73ms, 77.6MB)

테스트 2 〉	통과 (8.36ms, 79.3MB)
테스트 3 〉	통과 (7.93ms, 85.2MB)
테스트 4 〉	통과 (9.94ms, 76.6MB)
테스트 5 〉	통과 (13.06ms, 77.2MB)
테스트 6 〉	통과 (11.76ms, 76.3MB)
테스트 7 〉	통과 (9.66ms, 79MB)
테스트 8 〉	통과 (10.56ms, 78.5MB)
테스트 9 〉	통과 (16.74ms, 77.6MB)
테스트 10 〉	통과 (24.66ms, 78.6MB)
테스트 11 〉	통과 (30.95ms, 80.2MB)
테스트 12 〉	통과 (1.74ms, 75.4MB)
테스트 13 〉	통과 (1.68ms, 73.9MB)
테스트 14 〉	실패 (1.32ms, 76.7MB)

ㅋㅋㅋㅋㅋㅋㅋㅋ 실패 뭐임

반례를 생각해봄

아예 아무것도 안 들어온 케이스 어때

            if(allOk==true){
                if((roundR==roundL)&&(squareL==squareR)&&(curlyL==curlyR)){
                    if(roundR==0&&squareR==0&&curlyR==0){
                        //이게 반례인가
                    }else{
                        answer++;
                    }
                    
                }
            }

ㅋㅋ 아니었음 14번 아직도 실패임

테스트 5
입력값 〉	"[[["
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 6
입력값 〉	""
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.

테스트케이스 추가해봤는데 다 됨 ㅋㅋㅋㅋ

1.괄호 순서 역전되는거 allOk로 일단 거름

2.괄호 열긴 열었는데 안 닫아진거 if((roundR==roundL)&&(squareL==squareR)&&(curlyL==curlyR)){ 이걸로 거름

3.”” 빈게 들어오는거 if((roundR==0)&&(squareR==0)&&(curlyR==0)){ 이걸로 거름

이외에 뭐가 있냐고요

입력으로 "[{]}"이 주어진 경우 정답은 0이 나와야 하는데 1이 나옵니다. 위 방식으로는 괄호가 열린 괄호부터 나오고 열린괄호와 닫는 괄호의 갯수만 체크하는 것이지 올바른 것인지는 체크하지 않습니다.

오 맞네

저렇게 풀면서 저거 체크하기는 힘들듯함 케이스분류를 엄청나게 다시해야할듯,,,

걍 stack으로 푸는게 제일 나을듯함

java stack

Stack

import java.util.Stack;

Stack<Integer> stack = new Stack<Integer>();
stack.push(value);//Pushes an element on the top of the stack.
int position = stack.search(value);//If the element is found, returns the position of the element from the top of the stack. Else, it returns -1.
stack.pop();//Removes and returns the top element of the stack. An ‘EmptyStackException’ is thrown if we call pop() when the invoking stack is empty.
stack.peek();//Returns the element on the top of the stack, but does not remove it.
stack.empty(); //It returns true if nothing is on the top of the stack. Else, returns false.

⚠️stack search는 0이 아니라 1부터 세어줌

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i<s.length(); i++){
            
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            boolean noReverse = true;
            
            for(int j = 0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                
                if(c==')'){
                    if(stack.pop()!='('){
                        noReverse=false;
                        break;
                    }
                }else if(c==']'){
                    if(stack.pop()!='['){
                        noReverse=false;
                        break;
                    }
                }else if(c=='}'){
                    if(stack.pop()!='{'){
                        noReverse=false;
                        break;
                    }
                }
                stack.push(c);
            }
            if(noReverse == true && stack.size() == 0){
                answer++;
            }
            stack.empty();

        }
        return answer;
    }
}

Exception in thread "main" java.util.EmptyStackException

at java.base/java.util.Stack.peek(Stack.java:101)

at java.base/java.util.Stack.pop(Stack.java:83)

at Solution.solution(Unknown Source)

at SolutionTest.lambda$main$0(Unknown Source)

at SolutionTest$SolutionRunner.run(Unknown Source)

at SolutionTest.main(Unknown Source)

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i<s.length(); i++){
            
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            
            boolean noReverse = true;
            
            for(int j = 0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                
                if(c==')'&&stack.size()>0){
                    if(stack.pop()!='('){
                        noReverse=false;
                        break;
                    }
                }else if(c==']'&&stack.size()>0){
                    if(stack.pop()!='['){
                        noReverse=false;
                        break;
                    }
                }else if(c=='}'&&stack.size()>0){
                    if(stack.pop()!='{'){
                        noReverse=false;
                        break;
                    }
                }
                stack.push(c);
            }
            if(noReverse == true && stack.size() == 0){
                answer++;
            }
            stack.empty();

        }
        return answer;
    }
}

테스트 1
입력값 〉	"[](){}"
기댓값 〉	3
실행 결과 〉	실행한 결괏값 0이 기댓값 3과 다릅니다.
테스트 2
입력값 〉	"}]()[{"
기댓값 〉	2
실행 결과 〉	실행한 결괏값 0이 기댓값 2과 다릅니다.
테스트 3
입력값 〉	"[)(]"
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 4
입력값 〉	"}}}"
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 5
입력값 〉	"[[["
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.
테스트 6
입력값 〉	""
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.

출력하려고 ifelse 구조 바꿔봄

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i<s.length(); i++){
            
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            System.out.println(pushed);
            
            boolean noReverse = true;
            
            for(int j = 0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                
                if(c=='('||c=='{'||c=='['||stack.size()==0){
                    stack.push(c);
                }else{
                    char pop = stack.pop();
                    System.out.println("c " +c+ "pop "+pop);
                    
                    if(c==')'){
                        if(pop!='('){
                            noReverse=false;
                            break;
                        }
                    }else if(c==']'){
                        if(pop!='['){
                            noReverse=false;
                            break;
                        }
                    }else if(c=='}'){
                        if(pop!='{'){
                            noReverse=false;
                            break;
                        }
                    }
                }
            }
            if(noReverse == true && stack.size() == 0){
                System.out.println("answer++");
                answer++;
            }
            stack.empty();

        }
        return answer;
    }
}

테스트 1
입력값 〉	"[](){}"
기댓값 〉	3
실행 결과 〉	실행한 결괏값 1이 기댓값 3과 다릅니다.
출력 〉	
[](){}
c ]pop [
c )pop (
c }pop {
answer++ -> 맞지

](){}[
c )pop (
c }pop {

(){}[]
c )pop (
c }pop {
c ]pop [-> answer 왜 안함? ㅋㅋ

){}[](
c )pop [

{}[]()
c }pop {
c ]pop [
c )pop (-> answer 왜 안함

}[](){
c }pop ]

테스트 2
입력값 〉	
"}]()[{"
기댓값 〉	2
실행 결과 〉	
실행한 결괏값 0이 기댓값 2과 다릅니다.
출력 〉	

}]()[{
c ]pop }

]()[{}
c )pop (
c }pop {

()[{}]
c )pop (
c }pop {
c ]pop [

)[{}](
c )pop [

[{}]()
c }pop {
c ]pop [
c )pop (

{}]()[
c }pop {
c ]pop ]

stack.empty()가 안 되나 싶어서 그냥 지역변수로 만들어봄

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        
        for(int i = 0; i<s.length(); i++){
            
            Stack<Character> stack = new Stack<Character>();
            
            String leftout = s.substring(0,i);
            String right = s.substring(i,s.length());
            String pushed = right+leftout;
            System.out.println(pushed);
            
            boolean noReverse = true;
            
            for(int j = 0; j<pushed.length(); j++){
                char c = pushed.charAt(j);
                
                if(c=='('||c=='{'||c=='['||stack.size()==0){
                    stack.push(c);
                }else{
                    char pop = stack.pop();
                    System.out.println("c " +c+ "pop "+pop);
                    
                    if(c==')'){
                        if(pop!='('){
                            noReverse=false;
                            break;
                        }
                    }else if(c==']'){
                        if(pop!='['){
                            noReverse=false;
                            break;
                        }
                    }else if(c=='}'){
                        if(pop!='{'){
                            noReverse=false;
                            break;
                        }
                    }
                }
            }
            if(noReverse == true && stack.size() == 0){
                System.out.println("answer++");
                answer++;
            }

        }
        return answer;
    }
}

해결됨

저작자표시

'Coding Test' 카테고리의 다른 글

[프로그래머스] n^2 배열 자르기 (0)	2024.02.29
[프로그래머스] 연속 부분수열 (1)	2024.02.29
[프로그래머스]귤 고르기 (1)	2024.01.08
[프로그래머스] 카펫 (1)	2024.01.08
[프로그래머스]피보나치 수 (1)	2024.01.08

Greedeveloper

[프로그래머스] 괄호 회전하기

문제 주소

문제 설명

문제 설명

제한사항

입출력 예

입출력 예 설명

제출 코드

풀이 과정

Stack

'Coding Test' 카테고리의 다른 글

티스토리툴바

[프로그래머스] 괄호 회전하기

문제 주소

문제 설명

문제 설명

제한사항

입출력 예

입출력 예 설명

제출 코드

풀이 과정

Stack

'Coding Test' 카테고리의 다른 글

관련글

티스토리툴바