[Java] 사전식 배열

1. 문제

숫자 1부터 n 까지 '사전식 순서'로 배열을 출력하고자 한다.

사전식 순서는 숫자를 문자열로 보고 비교하는 것과 같으며, 규칙은 아래와 같다.

• 첫 자릿수부터 숫자가 더 작을 수록 앞에 온다. 
  • 예) 140이 21보다 앞에 온다.
• 숫자의 길이가 다르고, 앞자리가 같을 경우 더 짧은 숫자가 앞에 온다.
  • 예) 10이 103보다 앞에 온다.

 

 

2. 입력 설명

1 <= n <= 100000

 

 

 

3. 출력 설명

사전식 순서로 정수의 배열

 

 

 

4. 매개변수 형식

n = 15

 

 

 

5. 반환값 형식

{1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9}

 

참고) 사전식 순서로 숫자 1부터 500까지 배열하면 아래와 같다.

1, 10, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 11, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 12, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 13, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 14, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 15, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 16, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 17, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 18, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 19, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 2, 20, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 21, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 22, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 23, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 24, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 25, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 26, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 27, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 28, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 29, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 3, 30, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 31, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 32, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 33, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 34, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 35, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 36, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 37, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 38, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 39, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 4, 40, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 41, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 42, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 43, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 44, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 45, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 46, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 47, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 48, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 49, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 5, 50, 500, 51, 52, 53, 54, 55, 56, 57, 58, 59, 6, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 7, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99

 

 

6. 코드 구현

(1) 방법 1

 

숫자를 문자열로 변환하여 정렬한 후 다시 숫자로 변환한다.

 

    public static int[] solution(int n) {

        // 1. 숫자를 문자열로 변환
        String[] numToStr = new String[n];
        for (int i = 1; i <= n ; i++) {
            numToStr[i-1] = String.valueOf(i);
        }

        // 2. 문자열 배열을 정렬
        Arrays.sort(numToStr);

        // 3. 다시 int 형 배열로 변환
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.parseInt(numToStr[i]);
        }
        return result;
    }

 

 

 

 

(2) 방법 2

 

DFS 사용하여 한번에 사전식으로 작성

첫 시작 노드를 0으로 설정

( 루트 노드 (0) 에서 자식노드를 만들 때 0인 자식은 제외하기 )

 

import java.util.*;

class Solution {
    List<Integer> res;
    public int[] solution(int n) {
        res = new ArrayList<>();
        dfs(0, n);
        
        return res.stream().mapToInt(i -> i).toArray();
    }
    
    void dfs(int currentNode, int n) {
    	
        // 만약 현재 노드값이 최대값인 n을 넘어가게 된다면 반환
        if(currentNode > n) {
        	return;
        }
        
        // 현재 노드가 루트노드가 아닐 때
        if(currentNode > 0) {
        	res.add(currentNode);
        }
        
        // 자릿수를 하나 올리고, 일의 자리에 0~9 순서대로 DFS
        for(int i = 0 ; i < 10; i++) {
        	int newNum = currentNode * 10 + i;
            
            // 루트노드(0)에서 계속 0으로 내려가는 경우
            // 즉, 0000... 이 되는 경우
            if(newNum == 0) {
            	continue;
            }
            dfs(newNum, n);
        }
    }
}