[programmers] Java Lv.2 - 괄호 회전하기

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

프로그래머스

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

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

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

제한사항
s의 길이는 1 이상 1,000 이하입니다.

 

입출력 예

입출력 예 설명

입출력 예 #1

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

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

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

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

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

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

 

---

풀이

접근 방식

 s를 왼쪽으로 x만큼 회전시켰을 때, s가 올바른 괄호 문자열이 되게 하는 x의 개수

1. s의 길이가 홀수라면 올바른 괄호 문자열이 될 수 없음
       바로 answer = 0 리턴
2. 문자열 회전 시키기
       인덱스 계산해서 회전시킨 문자열 판단
3. 올바른 괄호를 확인하는 방법: stack 활용
       여는 괄호를 만나면 stack에 push
       닫는 괄호 만나면 peek, 같은 괄호 쌍이면 pop
       모든 문자열을 처리했는데 스택이 비어있지 않으면 올바른 괄호 문자열이 아님

 

---

문자열 회전

2중 for문으로 문자열을 회전시킴

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

• `i` : 회전 횟수 (`0` ~ `s.length - 1`) (현재 몇 번째 회전인지)
• `j` : 문자열 내 문자 위치 
• `i`번째 회전에서 인덱스 `j`의 문자 값 : `s.charAt((i+j) % s.length())`
  • `(회전 횟수 + 위치) % 문자열 길이`
  • `% s.length()`
    • `(i+j)`값이 문자열 s의 길이 보다 커지게 되면 `StringIndexOutOfBoundsException` 발생 
    • => 인덱스 계산`(i+j)`이 문자열 길이보다 커지면 처음(인덱스 0)으로 돌아가도록 해줌.

 

---

스택 자료구조

2025.01.10 - [Java Study/Basics] - [Java] 스택 자료구조: Stack과 Deque 비교

[Java] 스택 자료구조: Stack과 Deque 비교

 

---

풀이 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        String s = "}]()[{";
        int answer = 0;

        if (s.length()%2 == 0) {
            for (int i=0; i<s.length(); i++) {
                StringBuilder newS = new StringBuilder();	// 회전된 문자열 확인을 위한 StringBuilder
                Deque<Character> stack = new ArrayDeque<>();
                for (int j=0; j<s.length(); j++) {
                    char chk = s.charAt((i+j) % s.length());
                    /*if (chk == '(' || chk == '{' || chk == '[')
                        stack.push(chk);
                    else {
                        if (!stack.isEmpty()) {
                            if (chk == ')') {
                                if (stack.peek() == '(') {
                                    stack.pop();
                                }
                            } else if (chk == '}') {
                                if (stack.peek() == '{') {
                                    stack.pop();
                                }
                            } else if (chk == ']') {
                                if (stack.peek() == '[') {
                                    stack.pop();
                                }
                            }
                        }
                    }*/
                    // if문 가독성 안좋아서 switch문으로 재작성
                    switch (chk) {
                        case ')':
                            if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
                            break;
                        case '}':
                            if (!stack.isEmpty() && stack.peek() == '{') stack.pop();
                            break;
                        case ']':
                            if (!stack.isEmpty() && stack.peek() == '[') stack.pop();
                            break;
                        default:
                            stack.push(chk);
                            break;
                    }
                    newS.append(chk);
                }
                System.out.println(i + "번째 회전 : " + newS);	// 회전된 문자열 확인
                if (stack.isEmpty()) answer++;
            }
        }

        System.out.println(answer);
    }
}

 

---

제출

import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
    public int solution(String s) {
        int answer = 0;
        
        if (s.length()%2 == 0) {
            for (int i=0; i<s.length(); i++) {
                Deque<Character> stack = new ArrayDeque<>();
                for (int j=0; j<s.length(); j++) {
                    char chk = s.charAt((i+j) % s.length());
                    switch (chk) {
                        case ')':
                            if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
                            break;
                        case '}':
                            if (!stack.isEmpty() && stack.peek() == '{') stack.pop();
                            break;
                        case ']':
                            if (!stack.isEmpty() && stack.peek() == '[') stack.pop();
                            break;
                        default:
                            stack.push(chk);
                            break;
                    }
                }
                if (stack.isEmpty()) answer++;
            }
        }
        
        return answer;
    }
}