오늘의 알고리즘 (12.20)

알고리즘 스터디 때 배운 내용을 정리 해봤다.

x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "[]"() {} O
1 "](){}[" X
2 "(){}[]" O
3 "){}[](" X
4 "{}" O
5 "}{" X

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        // 괄호는 열고 닫히는 특성
        // boolean
        // 오해
        // 0, 1 만약에 이거를 다 돌고 끝났을 때
        // 0으로 끝나면 정상
        // 1로 끝나면 비정상
        // 비정상 < 0 > 비정상
        String[] sStrArr = s.split("");
        List<String> sList = new ArrayList<>();
        for (int i = 0; i < sStrArr.length; i++) {
            sList.add(sStrArr[i]);
        }
        for (int i = 0; i < sList.size()-1; i++) {
            int small = 0;
            int middle = 0;
            int large = 0;
            for(int j = 0; j < sList.size(); j++) {
                if (sList.get(j).equals("(")) {
                    small++;
                } else if (sList.get(j).equals("{")) {
                    middle++;
                } else if (sList.get(j).equals("[")) {
                    large++;
                }
                if (sList.get(j).equals(")")) {
                    small--;
                } else if (sList.get(j).equals("}")) {
                    middle--;
                } else if (sList.get(j).equals("]")) {
                    large--;
                }
                // 소중대 중 하나라도 0이하로 떨어졌다면?
                if (small < 0 || middle < 0 || large < 0) {
                    break;
                }
            }
            if (small == 0 && middle == 0 && large == 0) {
                answer++;
            }
            // 회전 로직
            String tmp = sList.get(0);
            sList.remove(0);
            sList.add(tmp);
        }
        return answer;
    }
}

• 처음 이 문제를 풀었읋 때는 모든 경우의 수를 다 적을 생각이었지만 위에 코드처럼 열리고 닫히는것을 개수를 세서 풀었으나 14번 째 에서 틀려버렸다.

• 힌트를 본 후

class Solution {
    public int solution(String s) {
        int answer = 0;
        String s2 = s;
        String s3 = s;
        for(int i = 0; i < s.length()-1; i++) {
            s3 = s2;
            for(int j = 0; j < s.length(); j++) {
                s3 = s3.replace("()", "");
                s3 = s3.replace("{}", "");
                s3 = s3.replace("[]", "");
            }
            if(s3.length() == 0) {
                answer++;
            }
            s2 = s2.substring(1) + s2.charAt(0);
        }
        return answer;
    }
}

• replace 함수를 이용하여 간단하게 풀 수 있었던 문제였다... 여기서 배운것은 문자열의 값을 substring과 charAt을 이용해 자르고 이어 붙일 수 있다는 것이다.