SWEA 16003. 화면 캡쳐

이미지 번호를 1부터 n까지 정렬할 때 숫자 정렬이 아닌 문자열 정렬을 따라서 정렬하여 min(n, 50)개의 파일명을 출력하는 문제이다.

ex) n = 11 일때 1 10 11 2 3 4 5 6 7 8 9  로 출력하면 된다.

 

백트래킹을 적용하여 문자열에 0부터 9까지 더하면서 빈 공간 혹은 0이 아닌 숫자이면서 n보다 작거나 같은 수 min(n, 50)개를 List에 순서대로 넣는다. 처음 빈 문자열에는 1부터 9, 비어있지 않다면 0부터 9를 순서대로 넣는다.

private static void backtracking(List<String> list, String now, long n) {
    if(list.size() >= 50) {
        return;
    }
    
    if(!now.isEmpty()) {
        long number = Long.parseLong(now);
        if(number > n) {
            return;
        }
        list.add(now);
        for(char c = '0'; c<='9'; c++) {
            backtracking(list, now+c, n);
        }
    } else {
        for(char c = '1'; c<='9'; c++) {
            backtracking(list, now+c, n);
        }
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            long n = Long.parseLong(br.readLine());
            List<String> list = new ArrayList<>();
            backtracking(list, "", n);
            for(String number: list) {
                sb.append(number).append(".png").append(' ');
            }
            sb.append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static void backtracking(List<String> list, String now, long n) {
        if(list.size() >= 50) {
            return;
        }
        
        if(!now.isEmpty()) {
            long number = Long.parseLong(now);
            if(number > n) {
                return;
            }
            list.add(now);
            for(char c = '0'; c<='9'; c++) {
                backtracking(list, now+c, n);
            }
        } else {
            for(char c = '1'; c<='9'; c++) {
                backtracking(list, now+c, n);
            }
        }
    }
}