프로그래머스 - 괄호 회전하기 (Level 2)

주먹구구식 풀이

그러나 14번이 계속 틀림

이유를 알아보니

{[}] 이런 것도 맞게 처리되기 때문.

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        char check='O';
        LinkedList <Character> linked_list=new LinkedList<>();
        Stack <Character> stack1=new Stack<>();
        Stack <Character> stack2=new Stack<>();
        Stack <Character> stack3=new Stack<>();
        for(char ch:s.toCharArray()){
            linked_list.add(ch);
        }
        int len=s.length();
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                
               char c=linked_list.get(j);
                
                if(c=='[')
                    stack1.push(c);
                else if(c=='(')
                    stack2.push(c);
                else if(c=='{')
                    stack3.push(c);
                else if(c==']'){
                    if(stack1.isEmpty()){
                        check='X';
                        break;
                    }
                    stack1.pop();
                }
                else if(c==')'){
                    if(stack2.isEmpty()){
                        check='X';
                        break;
                    }
                    stack2.pop();
                }
                else if(c=='}'){
                    if(stack3.isEmpty()){
                        check='X';
                        break;
                    }
                    stack3.pop();
                }
                else
                    ;
            }
            if(stack1.isEmpty() && stack2.isEmpty() &&
                        stack3.isEmpty()) {
                if(check=='O'){
                    answer++;
                }
                    
            }
            check='O';    
            linked_list.addLast(linked_list.get(0));
            linked_list.removeFirst();
        }
        
        return answer;
    }
}

 

---

해결방안

: 예를 들어 '('를 만나면 ')'를 넣어버리고

')'를 만나면 peek 했을 때 ')'인지 확인 후 아니라면 X로 바꾸기.

또한 각 짝이 순서대로 맞아야 하므로 스택을 3개 쓸 이유가 없음 

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        char check='O';
        LinkedList <Character> linked_list=new LinkedList<>();
        Stack <Character> stack=new Stack<>();
        
        for(char ch:s.toCharArray()){
            linked_list.add(ch);
        }
        int len=s.length();
        
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                
               char c=linked_list.get(j);
                
                if(c=='[')
                    stack.push(']');
                else if(c=='(')
                    stack.push(')');
                else if(c=='{')
                    stack.push('}');
                else if(c==']'||c==')'||c=='}'){
                    if(stack.isEmpty()||stack.peek()!=c){
                        check='X';
                        break;
                    }
                    stack.pop();
                }
                
                else
                    ;
            }
            if(stack.isEmpty()) {
                if(check=='O'){
                    answer++;
                }
                    
            }
            check='O';    
            linked_list.addLast(linked_list.get(0));
            linked_list.removeFirst();
        }
        
        return answer;
    }
}

 

LinkedList 메서드들

1. 담기

: add()

 

2. 원소 가져오기

: get()

 

3. 마지막에 원소 추가하기

: addLast()

 

4. 첫 번째 원소 삭제하기

: removeFirst()

 

---

간결하게 풀기

: 코드를 다듬어보자

 

import java.util.*;

class Solution {
    public Boolean isCorrect(LinkedList <Character> linked_list,
                            Stack <Character> stack, int len){
        for(int i=0;i<len;i++){
            char c=linked_list.get(i);
            switch(c){
                case '{' -> stack.push('}');
                case '[' -> stack.push(']');
                case '(' -> stack.push(')');
                case '}',']',')' -> {
                    if(stack.isEmpty())
                        return false;
                    if(stack.pop()!=c)
                        return false;
                }  
            }
        }
        return stack.isEmpty();
    }
    public int solution(String s) {
        int answer = 0;
        LinkedList <Character> linked_list=new LinkedList<>();
        Stack <Character> stack=new Stack<>();
        
        for(char ch:s.toCharArray()){
            linked_list.add(ch);
        }
        int len=s.length();
        
        for(int i=0;i<len;i++){
           if(isCorrect(linked_list, stack,len))
               answer++;
            linked_list.addLast(linked_list.get(0));
            linked_list.removeFirst();
        }
        
        return answer;
    }
}

 

 

---

LinkedList 쓰지 않고 배열로 풀이해 보기

 

import java.util.*;
class Solution {
    public Boolean isCorrect(char[] ch,Stack <Character> stack, int offset){
        int len=ch.length;
        for(int i=0;i<len;i++){
            char c=ch[(i+offset)%len];
            switch(c){
                case '{' -> stack.push('}');
                case '[' -> stack.push(']');
                case '(' -> stack.push(')');
                case '}',']',')' -> {
                    if(stack.isEmpty())
                        return false;
                    if(stack.pop()!=c)
                        return false;
                }  
            }
        }
        return stack.isEmpty();
    }
    public int solution(String s) {
        int answer = 0;
        
        Stack <Character> stack=new Stack<>();
        char[] ch=s.toCharArray();
        int len=s.length();
        
        for(int offset=0;offset<len;offset++){
           if(isCorrect(ch,stack,offset))
               answer++;
        }
        
        return answer;
    }
}

 

1. 배열의 원소를 왼쪽으로 한 칸씩 회전시키는 공식

 

: offset= 왼쪽으로 회전시킬 칸 개수

i=현재 인덱스

len=배열의 길이

(i+offset) % len  -> 회전시킨 후의 인덱스 반환 

 

2. 배열의 원소를 오른쪽으로 한 칸씩 회전시키는 공식

 

: (i-offset+len) % len

 

---

배열로 바꾸지도 않고 

문자열 메소드로 사용하기

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;

        for (int i = 0; i < s.length(); i++) {
            Stack<Character> stack = new Stack<>();
            boolean isCorrect = true;

            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt((i + j) % s.length());

                if (c == '[' || c == '(' || c == '{') {
                    stack.push(c);
                } else {
                    if (stack.isEmpty()) {
                        isCorrect = false;
                        break;
                    }
                    char open = stack.pop();
                    //짝이 맞는지 확인
                    if ((open == '[' && c != ']') || (open == '(' && c != ')') || (open == '{' && c != '}')) {
                        isCorrect = false;
                        break;
                    }
                }
            }
            if (!stack.isEmpty()) isCorrect = false;
            if (isCorrect) answer++;
        }

        return answer;
    }
}

 

 

혹은 문자열을 두번 이어붙혀 계산하는 방법도 가능.

 

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        String doubledS = s + s;

        for (int i = 0; i < s.length(); i++) {
            Stack<Character> stack = new Stack<>();

            for (int j = 0; j < s.length(); j++) {
                char c = doubledS.charAt(i + j);

                if (c == '[' || c == '(' || c == '{') {
                    stack.push(c);
                } else if (stack.isEmpty()) {
                    stack.push(c);
                    break;
                } else {
                    char open = stack.pop();

                    if ((open == '[' && c != ']') || (open == '(' && c != ')') || (open == '{' && c != '}')) {
                        stack.push(c);
                        break;
                    }
                }
            }
            if (stack.isEmpty()) answer++;
        }

        return answer;
    }
}