문제
https://www.acmicpc.net/problem/2661
2661번: 좋은수열
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
www.acmicpc.net
1,2,3 으로만 이루어진 N자리 숫자를 만든다. 이 중 가장 작은 수를 리턴한다.
단, 같은 순서가 연속해서 반복될 수 없다. ex) 33, 123123321
접근
- 12131213 처럼 딱히 규칙이 있지도 않고고, 1 <= N <= 80 으로 범위가 큰 수가 아니므로 완전탐색이 가능하다.
- 우선 수열이 좋은 수열인지(같은 순서가 연속해서 반복되지 않는지) 판단해야 한다. 해당 블로그를 참조하였다.
1211 => 길이 4, 1자리 비교, 나쁜 수열
1212 => 길이 4, 1자리 비교, 좋은 수열
1212 => 길이 4, 2자리 비교, 나쁜 수열
123123 => 길이 6, 1자리 비교, 좋은 수열
123123 => 길이 6, 2자리 비교, 좋은 수열
123123 => 길이 6, 3자리 비교, 나쁜 수열
- 해당 접근 방식을 코드로 짠다. 재귀를 이용해 전체 탐색을 했다.
시도
1차 시도
결과: 틀렸습니다
// 백준 제출시
// const address="/dev/stdin"
// VSC 테스트시
const address = "./input.txt";
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
let min = Number.MAX_SAFE_INTEGER;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
min = min > Number(str) ? Number(str) : min;
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
return min;
};
console.log(solution(input));
2차 시도
결과: 맞았습니다!!
const address="/dev/stdin"
const input = require("fs").readFileSync(address).toString().trim().split("\n");
const solution = (input) => {
const N = +input;
let stop = false;
const isGoodSequence = (str) => {
let len = str.length;
let loop = len / 2;
let start = len - 1;
let end = len;
for (let i = 1; i <= loop; i++) {
if (str.substring(start - i, end - i) === str.substring(start, end))
return false;
start -= 1;
}
return true;
};
const recursion = (len, str) => {
if (stop) return;
if (len === N) {
stop = true;
console.log(str);
}
// 수열은 1,2,3 중 하나로 이루어져 있다.
for (let i = 1; i <= 3; i++) {
if (isGoodSequence(str + i)) recursion(len + 1, str + i);
}
};
// 가장 작은 수를 구하는 것이므로 첫번째 자리는 항상 "1"이 되어야하고, 따라서 따로 탐색할 필요 x
recursion(1, "1");
};
solution(input);
분석
왜 min 부분을 삭제하니 통과한 걸까?
우선 굳이 min 이 필요 없었다. 차례대로 작은수부터 대입하니까 반복문이 끝나기전 제일 먼저이자 마지막으로 찍힌 수가 어차피 가장 작은 수이기 때문이다.
1차 풀이도 틀리지는 않았는데 틀렸던 이유는 정답(min)의 출력타입이 number 였기 때문이다. 정답으로 제출한 코드 마지막 부분만 console.log(Number(string)) 으로 쳤더니 틀렸다고 나온다. 출력 타입도 str 이어야 하는 구나.
나보다 속도가 적게 나온 다른 사람 코드 분석
1. 좋은 수열인지 판별하는 함수에서 substring 메소드가 아닌 slice 메서드를 사용
2. 재귀 함수에서 정답을 도출할 때 string 대신 array 를 사용
3. 재귀 함수에서 백트래킹시 조건문을 좋은 수열일 경우에만 진행이 아닌 나쁜 수열일 경우 반복문을 패스하도록 설정.
const fs = require('fs');
// /dev/stdin
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((v)=> v.split(" ").map((v)=> parseInt(v)))
// 숫자 1, 2, 3으로만 이루어지는 수열이 있다.
// 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면,
// 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
// 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다.
function solution (N){
const arr = [1,2,3]
const result = []
const dfs = (depth, number = '') => {
if(result.length > 0) return
if (depth === N) {
result.push(number)
return
}
for(let i = 0; i < arr.length; i++) {
const nextArray = number + arr[i].toString()
if(isBad(nextArray)) continue
dfs(depth+1, nextArray)
}
}
dfs(0)
return result[0]
}
function isBad (str) {
for (let i = 1; i <= str.length/2; i++) {
const last = str.slice(-i)
const before = str.slice(-i*2, -i)
if (last === before) return true
}
return false
}
console.log(solution(...input[0]))
'Board > 알고리즘' 카테고리의 다른 글
| 백준 2178 자바스크립트 (0) | 2023.01.24 |
|---|---|
| 백준 2667 자바스크립트 (0) | 2023.01.24 |
| 백준 14888 자바스크립트 (0) | 2023.01.22 |
| 백준 14889 자바스크립트 (0) | 2023.01.19 |
| [알고리즘 공부] 20230115 2주차 회고 (0) | 2023.01.16 |
