[백준] 6603. 로또 풀이 / Python, JavaScript

6603번: 로또

6603. 로또

접근한 방법

(1)조합과 (2)DFS를 사용하는 두 가지 방법이 있는데,

범위가 적으므로 Python을 쓰는 경우라면 조합 알고리즘으로 풀어내는게 더 빠르고 효율적입니다. 주어지는 수 들중 6개를 뽑는 경우들을 모두 구하는 것이므로 중복이 없는 조합을 구해야 합니다. 파이썬은 조합 라이브러리가 있지만 자바스크립트는 직접 구현해주어야 하므로 DFS로 풀어내는게 더 유리할 겁니다.

 

DFS를 사용할 경우 스택에 값을 하나씩 넣습니다. 오름차순 조합을 구해야하므로 DFS로 들어가서 스택의 상단값보다 현재 순회중인 값이 더 클 경우에만 스택에 넣어주는 식으로 진입하면 6개 수들을 구할 수 있습니다.

 

Python (1)

import sys
input = sys.stdin.readline

while 1:
    arr = list(map(int, input().split()))
    if arr == [0]:
        break
    arr.pop(0)
    from itertools import combinations
    [print(*v) for v in list(combinations(arr, 6))]
    print()

Python (2)

import sys
input = sys.stdin.readline
def dfs(s, arr):
    if len(s) == 6:
        return print(*s)
    for i in arr:
        if not s:
            s.append(i)
            dfs(s, arr)
            s.pop()
        elif s[-1] < i:
            s.append(i)
            dfs(s, arr)
            s.pop()

while 1:
    arr = list(map(int, input().split()))
    if arr == [0]:
        break
    arr.pop(0)
    dfs([], arr), print()

 

JavaScript (1) 

// ※백준 컴파일러 환경에 맞게 조정 필요.
function solution(arrays) {
  for (const arr of arrays) {
    if (arr[0] === "0") return;
    arr.shift();
    const combinations = (arr, n) => {
      const result = [];
      if (n === 1) return arr.map((value) => [value]);

      arr.forEach((fixed, index, origin) => {
        const rest = origin.slice(index + 1);
        const combs = combinations(rest, n - 1);
        const attached = combs.map((comb) => [fixed, ...comb]);
        result.push(...attached);
      });
      return result;
    };
    for (const res of combinations(arr, 6)) console.log(res.join(" "));
    console.log();
  }
}
solution([
  ["7", "1", "2", "3", "4", "5", "6", "7"],
  ["8", "1", "2", "3", "5", "8", "13", "21", "34"],
  ["0"],
]);

JavaScript (2) 

// ※백준 컴파일러 환경에 맞게 조정 필요.
function solution(arrays) {
  for (const arr of arrays) {
    if (arr[0] === "0") return;
    arr.shift();

    const dfs = (s) => {
      if (s.length === 6) return console.log(s.join(" "));

      for (const i of arr) {
        if (!s.length) {
          s.push(i);
          dfs(s);
          s.pop();
        } else if (parseInt(s[s.length - 1]) < parseInt(i)) {
          s.push(i);
          dfs(s);
          s.pop();
        }
      }
    };
    dfs([]);
    console.log();
  }
}
solution([
  ["7", "1", "2", "3", "4", "5", "6", "7"],
  ["8", "1", "2", "3", "5", "8", "13", "21", "34"],
  ["0"],
]);