엘리스 알고리즘 코드 챌린지 Day1(07월 08일) - Java

 

요즘 퇴근하고 집에서 남는 시간에 알고리즘 문제를 유형 별로 천천히 공부하며 풀어보고 있다.

메일을 정리하는데 원티드에서 발송한 엘리스 알고리즘 코드 챌린지 광고가 눈에 띄였다.

알고리즘 대회(?)를 참여해본 경험이 없기도 하고 신선한(?) 문제를 풀어보고 싶어 신청했다.

나는 Java로 참여 해보려 한다.

 

07월 08일~12일, 07월 15일~19일(평일) 매일 아침 10시부터 자정까지 한 문제씩 오픈된다.

온라인 예선에서 상위 50명을 추려 오프라인 본선을 진행한다.

목표는 예선 문제들을 해결하며 알고리즘 공부하는 것이다. 기회가 되면 오프라인 본선에도 참여해보고 싶다.

 

말이 예선이지 학습인 듯 하다...

---

Day1

목표량

• 시간 제한: 1초

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.
내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.
예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.
오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

지시사항

입력

• 첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다.

1 ≤ N ≤ 999999

• 정답이 반드시 있는 경우만 입력값으로 주어집니다.

출력

• 다음날 풀 문제의 개수를 출력합니다.

입력 예시

364

출력 예시

436

 

나의 제출

import java.io.*;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int length = (int)(Math.log10(N)+1);
        int[] arr = new int[length];
        int result = Integer.parseInt("9".repeat(length));

        for (int i=arr.length-1; i>=0; i--) {
            arr[i] = (N/(int)Math.pow(10, (arr.length-1)-i))%10;
        }

        Stack<Item> stack = new Stack<>();
        for (int i=0; i<arr.length; i++) {
            if (arr[0] <= arr[i]) {
                stack.push(new Item(0, i, arr[i] * (int)Math.pow(10, length - 1), new boolean[length]));
                while (!stack.isEmpty()) {
                    Item cur = stack.pop();

                    if (cur.at == length - 1) {
                        if (cur.num > N) {
                            result = Math.min(result, cur.num);
                        }
                        continue;
                    }

                    cur.used[cur.idx] = true;
                    for (int j=0; j<arr.length; j++) {
                        if (!cur.used[j]) {
                            int num = cur.num + (arr[j] * (int)Math.pow(10, arr.length-1-(cur.at+1)));
                            boolean[] used = cur.used.clone();
                            stack.push(new Item(cur.at+1, j, num, used));
                        }
                    }
                }
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
    }
}

class Item {
    public int at;
    public int idx;
    public int num;
    public boolean[] used;

    public Item(int at, int idx, int num, boolean[] used) {
        this.at = at;
        this.idx = idx;
        this.num = num;
        this.used = used;
    }
}

 

친구 제출

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String N = br.readLine();
        char[] arr = N.toCharArray();

        int index = -1;
        for (int i=arr.length-1; i>0; i--) {
            for (int j=i-1; j>=0; j--) {
                if (arr[i] > arr[j]) {
                    char temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    index = j;
                    break;
                }
            }
            if (index != -1) {
                break;
            }
        }

        Arrays.sort(arr, index+1, arr.length);

        bw.write(String.valueOf(arr));
        bw.flush();
        bw.close();
    }
}

알게된 내용

• int 자릿 수 구하기

(int)(Math.log10(N)+1)