[백준] 1759. 암호 만들기 풀이 / Python, JavaScript

1759번: 암호 만들기

1759. 암호 만들기

접근한 방법

주어진 문자들중 L개의 조합을 구하는 문제입니다. 조합 라이브러리와 DFS를 사용하는 방법이 있는데 저는 DFS를 사용했고 파이썬의 경우 조합 라이브러리를 쓰는 것이 속도 측면에서 더 유리합니다.

먼저 문자들을 정렬해놓고 스택을 이용해서 순서대로 값을 넣어줍니다.

L개가 완성되면 자음과 모음 개수를 체크해서 자음이 1개, 모음이 2개 이상인 경우에만 출력해주면 답을 구할 수 있습니다.

 

Python 풀이

import sys
input = sys.stdin.readline

l, c = map(int, input().split())
arr = sorted(list(input().split()))
def dfs(s):
    if len(s) == l:
        a, b = 0, 0
        for m in s:
            if m in "aeiou":
                a += 1
            else:
                b += 1
        if a >= 1 and b >= 2:
            return print("".join(s))
        return
    for v in arr:
        if v > s[-1]:
            s.append(v)
            dfs(s)
            s.pop()
for i in range(c - l + 1):
    dfs([arr[i]])

JavaScript 풀이

function solution(l, c, arr) {
  const dfs = (s) => {
    if (s.length === l) {
      let [a, b] = [0, 0];
      for (const m of s) "aeiou".includes(m) ? (a += 1) : (b += 1);
      if (a >= 1 && b >= 2) return console.log(s.join(""));
      return;
    }
    for (const v of arr) {
      if (v > s[s.length - 1]) {
        s.push(v);
        dfs(s);
        s.pop();
      }
    }
  };
  arr.sort();
  for (let i = 0; i < c - l + 1; i += 1) dfs([arr[i]]);
}

solution(4, 6, ["a", "t", "c", "i", "s", "w"]);