괄호 회전하기

공부하며 느낀 점

괄호 회전하기

입력된 문자열을 두배로 늘린다음에 검사하면되겠다.

나의 풀이

아무래도 ( ( [ ) ) ] 같은 테스트 예시가 있나보다.
세 종류의 괄호중 나중에 나온게 먼저 닫히는 경우 넘어가게 해야한다...

괄호의 종류에 따라서 나오는 순서가 고정되어 있지는 않다.
그렇다고 0보다 크냐 같은걸로 하면 괄호가 열리는 순간 에러가 뜰 것이다.

여전히 안된다. [ [ ( ] ) ] 와 같은 경우를 거르지 못한다.

닫히는 괄호가 생기는 곳에서 반으로 나누면 [ [ ] ] ( )같은 것이 오류가 나버린다.

애초에 if문과 for 문을 너무 중첩시킨게 문제인것같다.

function sol0(s) {
    let answer = 0;

    for (let i = 0; i < s.length; i++) {
        const rotated = s.slice(i) + s.slice(0, i);
        if (isProper(rotated)) {
            answer++;
        }
    }

    return answer;
}

const rotated = s.slice(i) + s.slice(0, i); : 반복문 이중 중첩을 피하기 위해서 slice를 이용해 새로운 문자열을 만든다.

아래는 괄호의 갯수를 파악하기 위한 함수
열리는 괄호는 배열안에 넣고, 닫히는 괄호가 나왔을 경우 마지막 요소와 현재 닫는 괄호의 종류를 기준으로 참/거짓을 판별한다.

function isProper(str) {
    const stack = [];

    for (let i = 0; i < str.length; i++) {
        const char = str[i];

        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        } else {
            if (stack.length === 0) return false;

            const top = stack.pop();
            if (
                (char === ')' && top === '(') ||
                (char === ']' && top === '[') ||
                (char === '}' && top === '{')
            ) {
                
            } else {
                return false;
            }
        }
    }

    return stack.length === 0;
}

다른 사람의 풀이

function sol1(s) {
    if(s.length % 2 === 1) return 0;

    let answer = 0;
    const mapping = { "}" : "{", "]" : "[", ")" : "("};

    for(let i = 0; i < s.length; i++) {
        const stack = [];
        const rotate = s.slice(i) + s.slice(0, i);
        let flag = true;

        for(let j = 0; j < s.length; j++) {
            if(rotate[j] === "[" || rotate[j] === "(" || rotate[j] === "{" )
                stack.push(rotate[j]);
            else {
                const last = stack.pop();
                if(last !== mapping[rotate[j]]) {
                    flag = false
                    break;
                }
            }
        }

        if(flag) answer++;
    }

    return answer;
}

mapping이라는 객체에 닫히는 괄호를 키, 열리는 괄호를 밸류로 설정하여 조건문으로 활용하였다.

속도 비교

시간 복잡도

둘 다 $O(N^2)$이다.

sol02, sol12 은 홀수인 경우 0을 리턴하는 예외를 추가한 경우이다.

반복 횟수 증가 시키기

위는 길이가 1000(짝수)인 경우 아래는 999(홀수)인 경우이다.

홀짝 판단하는게 성능이 매우 확실한것같다.

입력 길이 증가

두번째 줄은 나누기를 잘못 입력한거니까 신경쓰지 않으셔도 됩니다... ㅠㅠ

역시나 홀수일 경우 반으로 나누는게 아주 유용하다.

??? 뭔가 이상하다. 나도 모르게 뭔가를 건드렸을지도 모르니 sol02를 먼저 실행시켜봐야겠다.

순서를 바꾸니 마찬가지로 다음에 실행하는 것이 더 느리다.
나도 모르게 잘못된 코드를 짠걸까?
pop이 들어 있긴하지만 원본 배열은 건드리지 않아서 차이가 날리가 없다.

sol1X 를 먼저 실행시키니 똑같이 sol12 의 실행 시간이 줄었다. 처음 한번 함수를 실행시키면서 뭔가가 메모리에 들어가고 그것으로 인해 최적화 되는걸까?

오해(?)의 소지가 없게 그때그때 새로운 값을 선언했다.

이건 천천히 생각을 해봐야할 것같다.

공부하며 느낀 점

1. 검사를 다하지 않아도 홀짝에 따라서 값이 정해진다면 홀짝 검사를 먼저하는 것이 좋다.
   예외가 아닌 경우에는 별 차이가 없고, 예외인 경우에는 큰 차이가 날 수 있다.
2. 키:밸류 또는 그것들이 담긴 객체로도 참 거짓을 판별 할 수 있다는 점을 잘 활용해야겠다.
3. 나는 분명히 모든 변수를 잘 통제했다고 생각해도 아닌 경우가 있다. 좀 더 공부해야겠다.