[프로그래머스][Java] Lv.2 괄호 회전하기

문제 정리 : 문자열 s를 왼쪽으로 한 칸씩 회전하면서 해당 문자열이 올바른 괄호 문자열인지 검사해 

                    몇 개의 문자열이 올바른 괄호 문자열인지 return합니다.

---

풀이과정

1. 문자열 s을 왼쪽으로 한 칸 씩 회전시키기 위해 Queue에 Character형으로 문자 하나씩 넣습니다.

Queue<Character> string = new LinkedList<>();
        for(int i=0;i<s.length();i++)
            string.add(s.charAt(i));

2. 반복문으로 Queue에 있는 문자를 하나씩 뽑아 다시 넣는 방식으로 회전 시킵니다.

3. 올바른 괄호 문자열인지 확인하기 위해 Queue를 잠시 복사합니다.

Queue<Character> tempQ = new LinkedList<>(string);

Queue 복사시 주의할 점...

Queue를 복사할 때 처음에 

Queue<Character> string = new LinkedList<>();
Queue<Character> temp = string;

위와 같은 방식으로 복사했는데 이렇게 하면 temp 를 사용했는데도 원본 Queue인 string 까지 영향이 가게 됩니다.

찾아보니, 간접 복사(Shallow Copy)와 깊은 복사(Deep Copy)의 문제 때문이라고 합니다.

 

얕은 복사는 '값'이 아닌 '주소 값'을 복사하기 때문에 복사한 후에 원본 값이 변경되면서 복사한 값도 변경됩니다.

깊은 복사는 '값'을 새로운 메모리 공간에 복사하므로 복사한 후에 원본 값이 변경되어도 복사한 값은 유지됩니다.

 

이부분을 몰라서 얕은 복사(=)로 복사를 했다가 엄청 헤맸네요....

List 또한 마찬가지라고 하니, 복사할 때는 이 부분을 유의해서 복사해야 겠습니다.

4. 올바른 괄호 문자열을 검사하기 위해 Stack을 사용할 것입니다.

5. Queue에 들어있는 문자들을 하나씩 검사하는데 stack이 비어있거나, 열린 괄호가 들어오면 stack 에 push합니다.

6. 닫힌 괄호가 들어온다면 stack에 가장 위의 문자와 같은 괄호인지 확인하고, 같은 괄호이면 stack에서 pop합니다.

7. 만약 다른 괄호라면 올바른 괄호 문자열이 아니라고 판단하고, 해당 반복문을 종료합니다.

for(int j=0;j<string.size();j++){
	char ch = tempQ.poll();
                
    if(stack.isEmpty() || ch=='(' || ch=='{' || ch=='['){
		stack.push(ch);
        continue;
	}
    //stack이 비어있지 않고, 닫는 괄호가 들어온다면
    //괄호가 짝이 맞는지 검사한다.
	char chStack = stack.peek();
                
	//괄호가 짝이 맞으면 pop
	if(chStack=='[' && ch==']')
		stack.pop();
	else if(chStack=='{' && ch=='}')
		stack.pop();
	else if(chStack=='(' && ch==')')
		stack.pop();
        
	//짝이 맞지 않으면 종료.
    else
    	break;
}

8. 해당 문자열이 올바른 괄호 문자열이면 answer+1해주고, 문자를 왼쪽으로 회전시킵니다.

//반복문 검사가 끝나고
//올바른 괄호 문자열이면 answer+1
if(tempQ.isEmpty() && stack.isEmpty())
	answer++;
            
//문자열 회전
string.add(string.poll());

9. 문자열 길이만큼 회전시킨 후, 올바른 괄호 문자열의 개수answer를 return합니다.

---

전체코드

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        
        //문자열 s를 Queue에 넣기.
        Queue<Character> string = new LinkedList<>();
        for(int i=0;i<s.length();i++)
            string.add(s.charAt(i));
        
        //s를 왼쪽으로 한칸씩 회전시킨다. -> 문자열 길이만큼 돌며 검사.
        for(int i=0;i<string.size();i++){
            
            Queue<Character> tempQ = new LinkedList<>(string);
            //tempQ = string; //이렇게 복사하면 원본 값 건드려짐.
            //깊은 복사, 얕은 복사
            //System.out.println(string);
            
            Stack<Character> stack = new Stack<>();//괄호 검사
            
            for(int j=0;j<string.size();j++){
                char ch = tempQ.poll();
                
                //스택이 비어있거나 괄호가 열린 문자가 들어오면, stack에 넣어주고 다음 반복문.
                if(stack.isEmpty() || ch=='(' || ch=='{' || ch=='['){
                    stack.push(ch);
                    continue;
                }
                
                //stack이 비어있지 않고, 닫는 괄호가 들어온다면
                //괄호가 짝이 맞는지 검사한다.
                char chStack = stack.peek();
                
                //괄호가 짝이 맞으면 pop
                if(chStack=='[' && ch==']')
                    stack.pop();
                else if(chStack=='{' && ch=='}')
                    stack.pop();
                else if(chStack=='(' && ch==')')
                    stack.pop();
                //짝이 맞지 않으면
                else
                    break;
            }
            //반복문 검사가 끝나고
            //올바른 괄호 문자열이면 answer+1
            if(tempQ.isEmpty() && stack.isEmpty())
                answer++;
            
            //문자열 회전
            string.add(string.poll());
            //System.out.println(string);
        }
        
        return answer;
    }
}