Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 세그먼트 트리
- 그리디
- 에라토스테네스의 체
- 문자열
- 애드 혹
- 해시 테이블
- 누적 합
- 2357
- Python
- DFS
- 싸피
- 정수론
- SSAFY
- 13164
- 맵
- JavaScript
- 플로이드-워셜
- 그래프
- boj
- 트리
- 모던 JavaScript 튜토리얼
- DP
- 정렬
- 구현
- 수학
- 투 포인터
- 슬라이딩 윈도우
- BFS
- 이분 탐색
- 브루트포스
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 2661 - 좋은수열 (Python, JavaScript) 본문
아이디어
백트래킹으로 가장 작은 수의 좋은 수열을 찾는다.
풀이 #1 (Python)
좋은 수열 중 가장 작은 수는 1로 시작하게 되므로 리스트 stack에 길이 1과 문자열 1을 튜플로 저장한다.
while문에서 DFS로 문자열 길이 l과 문자열 s를 꺼내 슬라이싱으로 인접한 두 부분 수열 중 같은 쌍을 찾는다.
같은 쌍이 존재하면 break로 다음 값을 꺼내고, 그렇지 않으면 길이가 N인지 비교하고 N이면 출력 후 종료한다.
N이 아니면 stack에 다음 길이와 문자열을 추가하는데, stack은 마지막 값부터 꺼내므로 숫자가 큰 순서대로 넣는다.
가장 먼저 찾은 좋은 수열이 가장 작은 수의 좋은 수열이므로 좋은 수열을 찾으면 결과값 출력 후 while문을 종료한다.
N = int(input())
stack = [(1, '1')]
while stack:
l, s = stack.pop()
for i in range(l//2):
if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
break
else:
if l >= N:
print(s)
break
stack.append((l+1, s+'3'))
stack.append((l+1, s+'2'))
stack.append((l+1, s+'1'))
함수를 사용하여 구현할 수도 있으나, 결과값을 찾았는지 여부를 확인하기 위해 변수 res를 사용한다.
def dfs(l, s):
global res
if res:
return
for i in range(l//2):
if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
return
if l >= N:
res = s
return
dfs(l+1, s+'1')
dfs(l+1, s+'2')
dfs(l+1, s+'3')
N = int(input())
res = ''
dfs(1, '1')
print(res)
exit 메서드를 사용하여 결과값 출력 후 바로 종료하는 코드가 더 빠를 것이라고 예상했으나 의외로 조금 더 느렸다.
# 더 느린 코드
def dfs(l, s):
for i in range(l//2):
if s[l-i-1:] == s[l-(i+1)*2:l-i-1]:
return
if l >= N:
print(s)
exit()
dfs(l+1, s+'1')
dfs(l+1, s+'2')
dfs(l+1, s+'3')
N = int(input())
dfs(1, '1')
풀이 #2 (JavaScript)
풀이 #1과 같은 방식으로 동작한다.
자바스크립트에는 for else문이 없어 flag 변수로 break문으로 for문이 종료되었는지 여부를 판단한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const N = Number(input[0]);
let stack = [[1, '1']];
while (stack.length > 0) {
let [l, s] = stack.pop();
let flag = true;
for (let i=0; i<parseInt(l/2); i++) {
if (s.substring(l-i-1, l) === s.substring(l-(i+1)*2, l-i-1)) {
flag = false;
break;
}
}
if (flag) {
if (l >= N) {
console.log(s);
break;
}
stack.push([l+1, s+'3']);
stack.push([l+1, s+'2']);
stack.push([l+1, s+'1']);
}
}
함수를 사용하는 코드는 while문을 사용하는 코드보다 메모리를 조금 더 적게 사용하지만 더 느렸다.
// 메모리를 더 적게 사용하나 더 느린 코드
function dfs(l, s) {
if (res) return;
for (let i=0; i<parseInt(l/2); i++) {
if (s.substring(l-i-1, l) === s.substring(l-(i+1)*2, l-i-1)) return;
}
if (l >= N) {
res = s;
return;
}
dfs(l+1, s+'1')
dfs(l+1, s+'2')
dfs(l+1, s+'3')
}
const N = Number(input[0]);
let res = 0;
dfs(1, '1');
console.log(res);
'알고리즘' 카테고리의 다른 글
[BOJ] 6588 - 골드바흐의 추측 (Python) (0) | 2023.02.11 |
---|---|
[BOJ] 1915 - 가장 큰 정사각형 (Python) / 데이터 추가 (0) | 2023.02.11 |
[BOJ] 15681 - 트리와 쿼리 (Python) (0) | 2023.02.10 |
[BOJ] 3980 - 선발 명단 (Python, JavaScript) (0) | 2023.02.09 |
[BOJ] 1509 - 팰린드롬 분할 (Python) (0) | 2023.02.09 |
Comments