백준 1759번: 암호 만들기 - javascript

2 분 소요

백준 1759번: 암호 만들기

문제 설명

접기/펼치기

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

접기/펼치기

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

접기/펼치기

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예시

접기/펼치기

입력
4 6
a t c i s w

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

접근

N과 M 시리즈시리즈가 기반인 문제다.
재귀하면서 DFS의 형식으로 풀어나가는 brute-force문제다.
기본적인 개념은 주어진 C개의 문자들 중 L개를 선택해서 만들 수 있는 모든 수열이고, 그 중에서 자음은 2개이상, 모음은 1개이상 이라는 추가 조건이 주어진다.

재귀함수를 만들어보자.
먼저 우리는 L개를 선택할 때 까지 현재의 선택으로 이루어진 DFS 가지가 옳은 것인지 알 수 없다.
따라서 L개의 수가 선택된 순간 행동을 취해줘야한다.

먼저, 당연한거지만 기본적으로는 재귀의 반환.
그리고 현재 재귀 깊이가 L인지 확인
그리고 자음이 2개 이상인지 확인
그리고 모음도 1개 이상인지 확인
위의 조건을 모두 충족한 경우에는 전역변수에 현재 수열을 push

위의 조건에 기반하면 우리는 매개변수로 깊이값, L, 자음갯수, 모음갯수를 받아야한다.
function (cnt, L, cons_cnt, vowel_cnt….)

이번에는 0부터 C-1까지 반복하면서 모든 경우의 수를 찾아줄 반복문을 구성해야한다.

오름차순의 조건이 붙었으므로 매 반복문의 시작값은 이전 재귀함수 호출에서 i+1로 올려줘야 매번 0부터 시작하지 않는다. -> function (i+1, …)
당연한거지만 현재 주어진 알파벳을 현재 깊이의 인덱스에 추가해주는 것
현재 고른 알파벳이 모음인지 자음인지 구별해서 해당 카운터 값을 1 올려준 상태로 추가해 주는 것.

이렇게 구성하면 된다고 생각한다.
원래 N과M시리즈 처럼 중복방지용 boolean 체크배열이 있었는데, 생각해보니 문제에서 중복되는 것은 없다 라고 했으니 필요없어 보여서 빼버렸다.

ps 재귀에서 조심해야할 점 중 하나는 변수의 변화라고 생각한다.
설계할때 당장 재귀함수에 매개변수에 값을 넘겨주기 위해서 특정 변수값을 직접 변경해서 넣어줄때가 있는데, 재귀함수가 단일직선이면 상관없겠지만 반복문이 들어간 재귀함수라면 0부터 i번째까지 지속적으로 해당 변수가 동일 깊이에서는 동일한 값을 유지해야 다음 재귀결과들도 일정하게 유지가 된다.
따라서 매개변수로 넘겨 줄 때 cnt += n; 같은 형식이 아닌 func( cnt+n ); 의 형식으로 넘겨줘야 할 필요가 있다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let result = [];
let list = [];
let consonant  = ['a', 'e', 'i', 'o', 'u'];
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer = [];  
  let tmp = input[0].split(' ');
  let l = tmp[0]*1;
  let c = tmp[1]*1;
  let alpha = input[1].split(' ').sort();
  re_alpha (0, 0, l, c, alpha, 0, 0)
  console.log(result.join('\n'));
  process.exit();
});

let re_alpha = function(cnt,start,l,c,alpha, cons_cnt, vowel_cnt){  
  if(cnt==l){
    //자음,모음 조건을 충족 할 때만 result에 추가
    if(cons_cnt>=1 && vowel_cnt >=2){
      result.push(list.join(''));
    }    
    return;
  }
  for(let i=start;i<c;i++){    
    list[cnt] = alpha[i];
    //각각 현재 추가되는 글자가 모음인지 자음인지 체크해서 해당 카운터를 올려준다.
    if(consonant.indexOf(alpha[i])!=-1) {
      re_alpha(cnt+1, i+1, l, c, alpha, cons_cnt+1, vowel_cnt);
    }
    else{
      re_alpha(cnt+1, i+1, l, c, alpha, cons_cnt, vowel_cnt+1);
    } 
  }
}

Twitter Facebook LinkedIn

ryeon

백준 1759번: 암호 만들기 - javascript