[백준] 0926 오늘의 문제 풀이📚

최근 공채 시즌을 거치면서

보기 싫어서 미뤄뒀던 코딩테스트 알고리즘들을 공부하고있다.

BFS, 그리디, 스택 등등 뭐 사실 공부한다고 하기도 애매한 것들이지만..

재귀는 증말 너무 싫어서 DP랑 백트래킹은 최대한 미뤄두고 있는데

그것들도 뭐 언젠간 풀어야겠지..

 

1. ATM

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const N = Number(input.shift());
    const line = input[0].split(' ');
    const atmLine = [];

    for(let i = 0; i < N; i++) {
        atmLine.push(Number(line[i]));
    }
    
    atmLine.sort((a, b) => a - b);
    
    let sum = 0;
    let partSum = 0;
    for(let i = 0; i < N; i++) {
        partSum += atmLine[i];
        sum += partSum;
    }
    console.log(sum);
});

내가 한 번에 풀어낸 걸로 봐서는 

아주 기초중에서도 기초 문제인 듯하다.

그리디 알고리즘 문제인데, 사실 뭐 생각할 거리도 없이

문제를 그대로 코드로 옮기면 되는 수준.

 

2. 연결 요소의 개수

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    let [N, M] = input.shift().split(' ');
    N = +N; M = +M;

    const g = new Array(N + 1);
    const v = new Array(N + 1).fill(0);
    for(let i = 0; i < N+1; i++) {
        g[i] = new Array(N + 1).fill(0);
    }

    for(let i = 0; i < M; i++) {
        const line = input[i].split(' ');
        g[+line[0]][+line[1]] = 1;
        g[+line[1]][+line[0]] = 1;
    }

    function dfs(x) {
        v[x] = 1;
        
        for(let i = 1; i < N+1; i++) {
            const next = i;
            if(g[x][next] === 1 && v[next] === 0) {
                dfs(next);
            }
        }
    }

    let count = 0;
    for(let i = 1; i < N+1; i++) {
        if(v[i] === 0) {
            dfs(i);
            count++;
        }
    }

    console.log(count);
});

DFS 문제인데, 얘도 엄청 기초 문제인 듯.

BFS 문제만 풀다가 그래프를 DFS로 탐색하려니 약간 버벅거렸다.

그래도 한 가지 배운 점이라면

숫자로 형변환하는 건 문자열 앞에 '+'를 붙이는 게 가장 빠르다는 것.

 

3. 균형잡힌 세상

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const len = input.length;
    let stack = []; 

    for(let i = 0; i < len - 1; i++) {
        const sentence = input[i];
        const sentenceLength = sentence.length;
        let isBalanced = true;

        for(let j = 0; j < sentenceLength; j++) {
            if(sentence[j] === '(' || sentence[j] === '[') {
                stack.push(sentence[j]);
            } else if(sentence[j] === ')') {
                if(stack.length && stack[stack.length - 1] === '(') {
                    stack.pop();
                } else {
                    isBalanced = false;
                    break;
                }
            } else if(sentence[j] === ']') {
                if(stack.length && stack[stack.length - 1] === '[') {
                    stack.pop();
                } else {
                    isBalanced = false;
                    break;
                }
            }
        }

        if(stack.length > 0) isBalanced = false; 
        if(isBalanced) console.log('yes');
        else console.log('no');
        stack = [];
    }
});

간단하다고 생각했다가 엄청 시간을 많이 쓴 문제.

조건을 많이 검사해줘야 하는데, 몇 개를 빠뜨려서 결국 해답을 봤다.

우선, 스택에서 pop()을 할 때는 항상 스택에 원소가 남아있는지를 확인해줘야 한다.

물론 구현해놓은 스택이 있다면 거기서 이미 검사를 해놨겠지만

배열을 이용해서 그냥 스택처럼 쓰는 방식이라면 반드시 확인할 것.

 

그리고, 문장이 끝나고 나서 괄호쌍이 남아있는지를 반드시 확인해야 한다.

사실 처음에는 확인했었는데, 이리저리 고치다가 빠뜨린 케이스.

'( ( ) ( )'처럼, pop()을 할 수 있는대로 다 했는데 마지막에 괄호가 하나 남을 수도 있다.

이런 경우에는 균형잡힌 문장이 아니기 때문에 'no'를 출력해야 함.

 

추가로, 이런 문제에서는

문장이 여러개 주어지고, 각 문장별로 조건을 판별해야 하기 때문에

스택과 isBalanced 변수를 전역보다는 지역변수로 선언하는 것이 더 합리적이다.

안 그러면 마지막에 계속 스택을 비워주고, isBalanced를 true로 초기화시켜줘야 해서 귀찮아지기 때문.

 

4. 쇠막대기

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const pipes = input[0];
    console.log(pipes);
    const len = pipes.length;
    const stack = [];
    let parts = 0;

    if(pipes[0] === '(') stack.push(pipes[0]);

    for(let i = 1; i <= len; i++) {
        if(pipes[i] === ')') {
            if(pipes[i - 1] === '(') {
                stack.pop();
                parts += stack.length;
            } else {
                stack.pop(); 
                parts += 1;
            }
        } else if(pipes[i] === '(') {
            stack.push(pipes[i]);
        }
    }

    console.log(parts);
});

사실 이것도 정답률을 보니, 거의 기초적인 문제인 것 같은데

핵심적인 생각 하나를 딱 못해서 결국 답을 보고 푼 문제.

원리는 다음과 같다.

 

1. 일단 레이저가 나타나면, 쌓인 쇠막대기의 개수만큼 조각이 생긴다.

2. 일단 레이저 뒷부분은 고려하지 않고, 앞부분의 조각들만 더해준다.

3. ')'를 닫을 때, 레이저가 아닌 쇠막대기가 끝나는 부분이라면 거기서 조각이 1개 더 생긴다.

 

나는 3번에서, 쇠막대기가 끝날 때 조각이 하나 더 생긴다는 규칙을 발견하지 못했다.

자꾸 조각 개수가 불규칙하게 나오는 것 같아서, 왜 이렇게 되지? 하고 고민하다가

결국 시간은 시간대로 잡아먹고 문제는 못풀었다.

 

조금 억지스럽더라도 일단 규칙부터 발견했더라면

문제를 푸는 데에 한 걸음 더 나아갈 수 있었을텐데.

문제 푸는 데에 너무 소심했던 듯.

 

오늘의 팁.

숫자 -> 문자열 변환은 숫자 + "" 가 제일 빠르다.

문자열 -> 숫자 변환은 +문자열 이 제일 빠르다.