1138 한 줄로 서기 node.js

https://www.acmicpc.net/problem/1138
실버 2

N이 10이고 시간제한이 2초라서 순열로 모든 경우의수를 만들어 풀었는데, 이게 아니었나보다..

순열로 완전탐색

function isPass(selected, numList) {
  let result = true;
  // 입력으로 주어진 numList에 일치하는지 비교
  selected.forEach((el, i) => {
    const [index, cnt] = el;
    if (numList[index - 1] != cnt) {
      result = false;
    }
  });
  return result;
}

// 순열 구현
function perm(arr, selected, numList) {
  if (selected.length === arr.length) {
    if (isPass(selected, numList)) {
      console.log(selected.map((el) => el[0]).join(' '));
    }
  } else {
    arr.forEach((el) => {
      let isInclude = false;
      let biggerCnt = 0;
      // 이전 배열 중 자신보다 큰 수가 몇개 있는지 세기
      selected.forEach((selectedEl) => {
        const value = selectedEl[0];
        if (value > el) biggerCnt += 1;
        else if (value === el) isInclude = true;
      });
      // 이미 포함된 숫자라면 반복하지 않음
      if (isInclude) return;

      const newSelected = [...selected, [el, biggerCnt]];
      perm(arr, newSelected, numList);
    });
  }
}

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

const N = Number(input[0]);
const numList = input[1].split(' ').map(Number);
perm(
  Array.from({ length: N }).map((_, i) => i + 1),
  [],
  numList
);

그리디 알고리즘

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input.shift());
let list = input.shift().split(' ').map(Number);
let people = [];
for (let i = N - 1; i >= 0; i--) {
  people = people.slice(0, list[i]).concat([i + 1, ...people.slice(list[i])]);
}
console.log(people.join(' ').trim());

둘다 정답은 맞았으나... 시간이 60배 이상 차이났다.. ㅠ