📙[Algo] 24.01.06 알고리즘

7696번: 반복하지 않는 수

문제요약
같은 숫자를 두 번 이상 사용하지 않는 수 중 N번째 수 출력

시간 제한
1초

입력
N(1≤N≤1,000,000)
N이 0일 때 종료

출력
케이스별 N번째 반복 숫자 없는 수 출력

 

접근법

• 메모리 문제 관련해서 공부해볼 수 있는 문제
• N번째에서 N이 1000000까지 가능한 거였으니까, for문에서 num≤1000000할 게 아니라 배열의 인덱스를 1000000까지 탐색해야 한다.
• 자릿수 하나하나 체크하면서 이미 1~9까지 이미 방문한 숫자를 또 방문한 경우를 제외한 반복하지 않는 숫자들을 ableNum배열에 담아준다.

 

코드

import java.io.*;
import java.util.Arrays;

public class Main {
    static int[] ableNum = new int[1000010]; //마진은 넉넉하게
    static boolean[] visited = new boolean[10];

    static void makeCase() {

        int temp, remain;
        boolean check;
        for(int num=1, idx=1; idx<=1000000; num++){

            Arrays.fill(visited, false);
            temp=num;
            check = true;

            while(temp>0){
                remain = temp % 10;
                temp /= 10;

                if(visited[remain]) {
                    check = false;
                    break;
                }

                visited[remain] = true;
            }

            if(check) ableNum[idx++] = num;

        }

    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N;
        boolean[] check;
        makeCase();

        while(true){
            N = Integer.parseInt(br.readLine());

            if(N==0) break;

            System.out.println(ableNum[N]);

        }


    }
}