프로그래머스 - Lv.2 모음사전(백트래킹) JS 본문
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/84512
해당 문제는 모음 A,E,I,O,U 를 조합하여 1~5 길이의 단어를 만들어 각각에 순서를 붙이고, 특정 문자열을 제시할 때 해당 문자열이 몇 번째 위치하는가에 대한 문제다.
먼저 A,E,I,O,U 를 조합하여 만들 수 있는 1~5가지의 문자열의 갯수는 3905(5^5 + 5^4 + 5^3 + 5^2 + 5^1)이기 때문에, 완전 탐색을 수행해도 높은 시간 복잡도가 우려되지는 않았다.
허나 이미 답에 맞는 문자열을 찾았음에도, 구태여 모든 탐색을 진행하는 것은 불필요하기에 내가 만든 문자열과 문제에서 제시된 문자열이 같다면 중지되도록 구현했다.
소스 코드
function solution(word) {
const vowels = ['A','E','I','O','U']
let compare = '' // 만들어지는 문자열을 담는 변수
let result = 0 // 결괏값을 담는 변수 => 밑에 반복문이 진행될수록 값 증가
let toggle = false // 결괏값을 찾았을 때 모든 반복문을 탈출할 수 있도록 임시로 만든 변수
const backTracking = () => {
if(compare.length === 5) return
else {
for(let i = 0 ; i < 5 ; i ++) {
// toggle = true 일 경우 모든 반복문을 탈출할 수 있도록 함
if(toggle) return
compare += vowels[i]
result ++
// # 만들어진 문자열이 문제에서 제시된 문자열과 같다면 toggle = true로 설정
if(compare === word) toggle = true
backTracking()
compare = compare.slice(0, compare.length - 1)
}
}
}
backTracking()
return result
}
console.log(solution('AAE'))
반응형
'개발 > algorithm' 카테고리의 다른 글
백준19947 - 투자의 귀재 배주형 (DP) JS (0) | 2023.10.06 |
---|---|
프로그래머스 - Lv.2 소수찾기 (백트래킹) JS (0) | 2023.10.05 |
백준1009 - 분산처리 JS (0) | 2023.10.03 |
백준10866 - 덱 (연결리스트) JS (0) | 2023.10.02 |
백준9322 - 철벽 보안 알고리즘 JS (0) | 2023.10.01 |
Comments