백준 6603 < 로또 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/6603

6603번: 로또

 

📍알고리즘 분류

- 수학

- 조합론

- 백트래킹

- 재귀

 

📍문제 풀이

- 주어진 수들의 집합에서 6개를 뽑는 경우의 수를 구하자 (조합)

- 백트래킹으로 조합을 구현할 수 있다

- 테스트 케이스 그룹마다 줄바꿈으로 구분해줘야 한다

 

📍코드 (JavaScript)

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

input.pop();

const answer = [];

for (let el of input) {
  const group = [];
  const result = [];
  const isUsed = [];
  const [k, ...S] = el.split(' ').map(Number);

  const recursive = (depth) => {
    if (depth === 6) {
      const res = result.join(' ');
      group.push(res);
      return;
    }

    for (let i = 1; i <= k; i++) {
      if (!isUsed[i]) {
      	// 오름차순이 깨지면 다음 수(depth가 아님) 로 넘어감
        if (depth >= 1 && result[depth - 1] > S[i - 1]) continue;
        result[depth] = S[i - 1];
        isUsed[i] = true;
        recursive(depth + 1);
        isUsed[i] = false;
      }
    }
  };
  recursive(0);
  answer.push(group.join('\n'));
}

// 테스트 케이스 단위마다 줄바꿈 넣어줌
console.log(answer.join('\n\n'));

 

📍리뷰

- 반복문 안에서 매번 재귀 함수를 정의하지 않고, 바깥에서 한 번에 정의하면 복잡도를 개선할 수 있을 것 같다