[boj 17299] 오등큰수 - js

 

// 오등큰수

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

const size_A = input.shift();
const element_A = input;
const sol = (size_A,element_A) =>{
    const result = new Array(size_A).fill(-1);
    const countArr = element_A.map(item => element_A.filter(item2=>item2 === item).length);
    const stack = [];
    for(let i =0; i<size_A; i++){
        while(stack.length>0 && countArr[stack[stack.length-1]] < countArr[i]){
            result[stack.pop()] = element_A[i];
        }
        stack.push(i);
    }
    console.log(result.join(' '));
}

sol(size_A,element_A);

오큰수와 비슷한 문제이다. 스택에 아직 큰 원소를 찾지 못한 값들을 저장해주고 원소들을 조회하며 비교하면 된다.

 

오큰수와 다른점이라면 해당 원소의 개수로 판단한다는 것인데 간단하게 모든 값을 조회해서 filter로 구하면된다고 생각해 구현하였으나 시간초과가 발생했다. 왜 그런가 했더니 개수를 세며 이미 했던 동작(ex 1,1,2,1,1,1 이라는 배열이 있다면 0의 인덱스에서 전체 1의 개수를 조회하고 1의 인덱스에서 또 전체 1의 개수를 조회하고 이런식으로..)을 또 하는 불필요한 로직이였다.

 

검색을 통해 객체를 통해 생성하는 아이디어를 얻었다. 

// 오등큰수

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

const size_A = input.shift();
const element_A = input;
const sol = (size_A,element_A) =>{
    const result = new Array(size_A).fill(-1);
    const count = {};
    for(let c in element_A){
        if(!count[element_A[c]]){
            count[element_A[c]] = 1;
        } else {
            count[element_A[c]]++;
        }
    }
    const stack = [];
    for(let i =0; i<size_A; i++){
        while(stack.length>0 && count[element_A[stack[stack.length-1]]] < count[element_A[i]]){
            result[stack.pop()] = element_A[i];
        }
        stack.push(i);
    }
    console.log(result.join(' '));
}

sol(size_A,element_A);

이렇게 작성을 한 결과 개수를 카운팅 할 때 반복문을 처음부터 끝까지 다시 반복하지않고 해당 원소의 카운트를 올리기만 하니 불필요한 행동을 안하게 되었다.

 

결과는 통과! 좀 더 효율적으로 사고하는 방법을 알아가는 것 같아 기분이 좋다~