[백준 7696번 반복하지 않는 수]

오늘의 문제는 반복하지 않는 수이다.

 

 

처음엔 무조건 완전탐색!

 

처음엔 완전탐색으로 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