백준 1759 - 암호 만들기 (백트래킹) JS 본문
반응형
https://www.acmicpc.net/problem/1759
해당 문제는 몇 가지 알파벳을 제시한 후, 특정 조건(모음 1개 이상, 자음 2개 이상)을 만족하는 암호를 출력하는 문제다.
나는 산출할 수 있는 모든 조합을 만들 수 있는 백트래킹 로직과, 만들어진 조합을 검증하는 검증 로직 두 가지를 구현하여 문제를 해결하였다.
const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
.toString().trim().split('\n')
// 검증 로직
const verify = (arr) => {
// 모음 배열
const vowels = ['a','e','i','o','u']
const table = {}
arr.forEach((el)=> {
// 모음일 경우, table['vowels'] / 자음일 경우 table['cons']에 갯수 추가
vowels.indexOf(el) !== -1
? table['vowels'] = (table['vowels'] || 0) + 1
: table['cons'] = (table['cons'] || 0) + 1
})
// 자음, 모음 갯수 검증 리턴
return table['vowels'] > 0 && table['cons'] > 1
}
function solution(data) {
const [[N,M], temp] = data.map(el => el.split(' '))
// 알파벳 순 정렬
const chars = temp.sort()
// 결괏값을 담는 배열
const result = []
// 백트래킹 시 산출되는 문자들을 저장하기 위한 임시 배열
const storage = []
// 중복 사용을 막기 위한 배열
const visited = Array.from({length : M}, ()=> false)
// 백트래킹 로직
const backTracking = (n) => {
// 길이 만족 시
if(storage.length === +N) {
// 검증에 통과하면 result 배열에 추가
if(verify(storage)) result.push(storage.join(''))
return
}
for(let i = n ; i < M ; i ++) {
// 방문(중복)한 곳이라면 패스
if(visited[i]) continue
// 방문 처리 및 storage 배열에 해당 값 추가
visited[i] = true
storage.push(chars[i])
// 재귀적으로 backTracking 함수 실행
backTracking(i)
// 방문 취소 및 storage 배열에 해당 값 제거
storage.pop()
visited[i] = false
}
}
// 정렬된 변수인 chars의 0번 인덱스에서 시작하므로 초기값은 0
backTracking(0)
console.log(result.join('\n'))
}
solution(input)
예전, 백준에서 순열에 대한 문제 풀이 방식을 보고 응용해서 해결했다. (처음에는 개념 자체가 이해가 안되서 vscode의 디버깅을 활용하며 이해했었더랬다.)
반응형
'개발 > algorithm' 카테고리의 다른 글
백준 1969 - DNA, JS (0) | 2023.09.07 |
---|---|
백준 11725 - 트리의 부모찾기 (BFS) JS (0) | 2023.09.06 |
프로그래머스 - Lv.2 삼각달팽이 JS (0) | 2023.09.04 |
백준 - 14940 쉬운 최단거리 (BFS) JS (0) | 2023.08.14 |
백준 - 12865 평범한 배낭 (DP) JS (0) | 2023.08.02 |
Comments