백준 10799번 쇠막대기

yugyeongKim·2022년 3월 28일

백준

목록 보기

44/52

내가 푼 코드

1. 한번에 되면 무슨일이 일어나나?

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

let laser = input[0].replace(/\(\)/gi, '*').split('');

let bar = [];
let laserIndex = [];
let isbar = false;

let left = 0;
while(laser.includes('(')) {
    for(let i=0; i <laser.length; i++) {
        if(laser[i] === '(') {
            isbar = true;
            left = i;
        } else if(isbar && laser[i] === ')') {
            isbar = false;
            bar.push([left, i]);
            laser[left] = 0;
            laser[i] = 0;
        }
    }
}

laser.filter((e,i) => { e === '*' ? laserIndex.push(i) : null});

let answer = 0;
for(let i=0; i < bar.length; i++) {
    let [start, end] = bar[i];
    for(let j=0; j < laserIndex.length; j++) {
        if(start < laserIndex[j] && end > laserIndex[j]) {
            answer++;
        }
    }
    answer++;
}
console.log(answer);

시간초과가 떴는데 맞는 방법인 거 같긴함.

2. 아예 다른 방법(구글링)

구글링한 것에서 힌트를 얻었다. 파이프의 시작한 갯수를 더해서 레이저를 만나면 그만큼 더해주고 파이프의 끝에 달하면 갯수를 다시 더해주는 식으로레이저의 만남과 파이프의 양끝에 초점을 두고 문제를 풀었다.

파이프의 왼쪽끝'('일때 count++를 해주고 레이저일때 bar에 count만큼 더해준다. 그 후 파이프의 오른쪽끝')'일때 count--해주고 bar++를 해준다. 이런식으로 계속하다보면 잘려진 갯수를 알 수 있다.

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

let arr = input[0].split('');

let bar = 0;
let count = 0;

let stack = [];
for(let i=0; i < arr.length; i++) {
    if(arr[i] === '(' && arr[i+1] !== ')') {
        count++;
    } else if(arr[i] === ')' && arr[i-1] !== '(') {
        bar++;
        count--;
    } else if(arr[i] === ')' && arr[i-1] === '(') {
        count !== 0 ? bar += count : null;
    }
}

console.log(bar);

개간결하죠? 이런^^

참고 블로그
이 블로그에서 아이디어를 얻었다.

다른 사람 풀이

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('');
var stack = [];
var answer = 0;
for(var i in input){
    if(input[i] === '('){
        stack.push(input[i]);
    }else{
        if(input[i-1] === '('){
            stack.pop();
            answer += stack.length;
        }else{
            stack.pop();
            answer ++;
        }
    }
}
console.log(answer);

막대기가 시작하면 stack에 집어넣고 레이저가 지나가면 stack의 길이만큼 answer에 더해준다. 막대기가 끝나면 pop으로 빼준다.
출처

2022-05-15 복습

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split(' ')[0].split('');
console.log(input);

let answer = 0;
let bar = 0;

for(let i=0; i < input.length; i++) {
    if(input[i] === '(' && input[i+1] === ')') {
        answer += bar;
    } else if(input[i] === ')' && input[i-1] !== '(') {
        bar--;
        answer++;
    } else if(input[i] === '(') {
        bar++;
    }
}

console.log(answer);

처음에 안풀리다가 계속 고민하다가 엇?하면서 생각났다.

막대가 잘리려면
1. 막대기가 있어야 한다.
2. 레이저가 지나가야한다.

저 순서대로 조건이 성립해야 된다. 그래서 (일때 막대기가 생기니 막대기 수를 1 더해준다. ()일때 막대기 개수만큼 잘리니 answer += bar를 해준다. 막대기가 끝나면 막대기 수를 1개줄여주면 끝!

yugyeongKim