[BaekJoon] 1662 번 압축 문제 - (nodejs)

문제 번호 :  1662번

문제 바로가기 ☞ https://www.acmicpc.net/problem/1662

---

 

<<< 문제 내용 >>>

 

---

 

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');

input = input[0].split('');
let arr = [];
let front = 0;
let answer = new Array(20).fill(0);

for(let i in input){
    if(input[i] === ')'){
        let temp = "";
        while(true){
            let index = arr.pop();
            
            if(index === '('){
                let number = arr.pop();
                answer[front] = answer[front] + (answer[front+1]+temp.length) * number;
                answer[front+1] = 0;

                break;
            }else{
                temp += index;
            }
        }
        front--;
    }else if(input[i] === '('){
        arr.push(input[i]);
        front++;
    }else arr.push(input[i]);

}

console.log(arr.length+answer[1]);

* 처음엔 문자를 그대로 담아뒀다 갯수만큼 쏟아내었더니 메모리초과가 떴습니다.

이 문제는 결국 string을 줄이고 반복되는 건 버려야 했습니다.

 

해결방법

1. 입력값을 하나씩 담고 '(' 와 ')'일때만 다르게 처리한다.

2. '('는 front값을 하나씩 진행해주었는데, 이는 괄호의 단계를 뜻한다.

3. 따라서 만약 answer = [0, 0, 0, 0, 0, 0, 0 ... 0] 이렇게 있다고하면 세번째 '('는 answer[3]에 기록될 것이다.

( 그 이유는 15(22)13(92(1111)42(222))123(1)45 와 같은 반례 때문이다. 그리고 answer[0]은 계산의 편의를 위해 그냥 비웠다. )

4. 그 이후 ')'를 만나게되면 '('를 만날 때 까지 temp에 값을 담아두고, '('를 만나면 '('앞의 숫자와 계산해서 answer[괄호 단계]에 계속해서 누적시켜준다.

5. 만약 괄호단계가 줄어들게되면 뒤의 단계에 영향을 주지 않도록 0으로 초기화 시켜주면서 마지막엔 answer[1]에 모든 계산한 값이 누적된다.

6. 이 누적한 값을 계산에 들어가지않았던 나머지 arr의 길이와 합쳐주면 값이 출력된다.

 

 

다른 사람의 코드도 확인해보고자 검색해봤지만 안타깝게도 javascript, nodejs 등의 검색어로도 찾을 수 없었습니다.

애초에 제출한 사람의 수가 굉장히 적었고, 그 중 2명만이 맞추었기 때문인 것 같았습니다.

 

그래서 다른 언어로 한번 보았으나, 대부분 재귀를 사용하시더라구요.

재귀로도 할 수 있겠구나... 싶어서 놀랬지만 어쨋든 이렇게 정해진 케이스 내에서는 제 방식이 나름 빠른 것 같아서 도움이 될까하고 올려봅니다 ㅎㅎ.

 

 

 

도움이 되셨다면 공감 부탁드립니다.