728x90
오늘의 문제는 반복하지 않는 수이다.
처음엔 무조건 완전탐색!
처음엔 완전탐색으로 while문을 통해 모든 수를
각 자릿수를 그때그때 따로 파악하여 출력을 해줬다.
그 결과는 메모리 초과였다.
고민을 해본 결과 1부터 최대 n범위인 1백만까지 각 수에 해당하는
n번째 반복 숫자 없는 수를 미리 구하고
요구하는 수마다 해당하는 수를 출력해 주면 되는 것이었다.
코드는 다음과 같다.
( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )
( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )
import java.util.*;
import java.io.*;
public class Main{
static int [] ans = new int [1000010]; // 모든 답안을 저장해줄 배열
static int [] visited_arr = new int [10]; // 자리마다 사용된 수를 세어줄 배열
public static void main(String [] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = 1; // n번째를 판단해줄 수
int num = 1; // 현재 위치한 수
while(cnt <= 1000000){ // 1백만번째까지만
if(check(num)){ // 각 수를 중복 판단하여 true라면
ans[cnt] = num; // n(cnt)번째 수에 num 넣어주고
cnt++; // cnt 1칸 이동
}
num++; // num은 항상 1씩 이동해준다.
}
//출력을 도와줄 StringBuilder 선언
StringBuilder sb = new StringBuilder();
// 입력받는 모든수에 해당하는 애들을 sb에 넣어주기
while(true){
int temp = Integer.parseInt(br.readLine());
// 이번 수가 0이라면 끝내기
if(temp == 0){
break;
}
sb.append(ans[temp]).append("\n");
}
System.out.println(sb);
}
private static boolean check(int num){
Arrays.fill(visited_arr, 0); // 매번 배열 0으로 초기화
while(num > 0){ // 자리수 중복 확인
visited_arr[num % 10]++;
if(visited_arr[num % 10] >= 2){
return false;
}
num /= 10;
}
return true;
}
}
알고리즘 재활을 하려는데 처음이 아닌 내용이지만 떠오르지 않았어서 속상하다..
고민의 시간이 짧았던걸 수도 공부가 그동안 얕았던걸 수도..
다시 꾸준히 해나가야겠다.

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~
https://www.acmicpc.net/problem/7696
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준 10610번 30] (0) | 2025.01.06 |
---|---|
[백준 15996번 팩토리얼 나누기] (1) | 2025.01.05 |
[백준 31589번 포도주 시음] (1) | 2024.12.17 |
[백준 1735번 분수 합] (2) | 2024.12.04 |
[백준 13241번 최소공배수] (0) | 2024.12.04 |