1759번: 암호 만들기

문제 접근 🤔

• 중복을 허용하지 않고 정해진 길이의 문자열을 만드는 것이기 때문에 조합을 생각했다.
• 입력된 문자 리스트를 사전순으로 정렬 후, 길이가 L 인 조합을 생성하고 문제의 조건에 부합하는 것들만 출력해주자.
• 파이썬의 itertools.combinations 함수를 이용하면 쉽게 조합을 만들 수 있다.
• 암호에는 최소 한 개의 모음과 최소 두 개의 자음으로 구성되기 때문에, 조건을 만족하는지 만들어진 조합의 원소들을 검사한다.
  
  
  

놓쳤던 부분 😅

• 백트래킹으로 풀고 싶었으니 이해 부족으로 먼저 조합으로 풀이했다.
  
  
  

코드 😁

파이썬 코드(40 ms)

# 조합을 이용한 풀이 - (시간 40ms)
from itertools import combinations

L, C = map(int, input().split())
combiList = list(combinations(sorted(input().split()), L))
pwdList = []

for combi in combiList:
    consonants, vowels = 0, 0
    for s in combi:
        if s in ['a', 'e', 'i', 'o', 'u']:
            vowels += 1
        else:
            consonants += 1
    if consonants >= 2 and vowels >= 1:
        pwdList.append(''.join(combi))

print('\n'.join(pwdList))

# 백트래킹을 이용한 풀이 - (시간 60ms)
L, C = list(map(int, input().split()))
sList = sorted(input().split())
pwdList = []

def checkPwd(combi):
    consonants, vowels = 0, 0
    for s in combi:
        if s in ['a', 'e', 'i', 'o', 'u']:
            vowels += 1
        else:
            consonants += 1
    if consonants >= 2 and vowels >= 1:
        return True
    else:
        return False

def backtracking(combi):
    if len(combi) == L:
        if checkPwd(combi):
            pwdList.append(''.join(combi))
            return
    
    for idx in range(len(combi), C):
        if combi[-1] < sList[idx]:
            combi.append(sList[idx])
            backtracking(combi)
            combi.pop()

for i in range(C - L + 1):
    backtracking([sList[i]])
    
print('\n'.join(pwdList))

자바스크립트 코드(180 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, data] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = ([n, m], sList) => {
  const pwdList = [];
  sList.sort();

  const checkPwd = (combi) => {
    let [consonants, vowels] = [0, 0];

    for (let i = 0; i < combi.length; i++) {
      if (['a', 'e', 'i', 'o', 'u'].includes(combi[i])) {
        vowels++;
      } else {
        consonants++;
      }
    }
    if (consonants >= 2 && vowels >= 1) {
      return true;
    } else {
      return false;
    }
  };

  const backtracking = (combi) => {
    if (combi.length === n) {
      if (checkPwd(combi)) {
        pwdList.push(combi.join(''));
        return;
      }
    }

    for (let idx = 0; idx < m; idx++) {
      if (combi[combi.length - 1] < sList[idx]) {
        combi.push(sList[idx]);
        backtracking(combi);
        combi.pop();
      }
    }
  };

  for (let i = 0; i <= m - n; i++) {
    backtracking([sList[i]]);
  }
  console.log(pwdList.join('\n'));
};

solution(L.split(' ').map(Number), data.split(' '));