[java]백준 1038번: 감소하는 수, ArrayList 첫번째에 넣어주기 list.add(0,123), ArrayList 합치기 list.addAll(list2)

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

---

코드

 

import java.util.*;

public class j1038_2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); //N번째 감소하는 수

		ArrayList<Long> list = new ArrayList<>();

		int cnt = -1; 	// cnt번째 감소하는 수

		for (long i = 0; i < 10; i++) {
            //자릿수 1인 것들 0~9까지 넣어준다
			cnt++;

			list.add(i);
			if (cnt == N) {

				System.out.println(i);
			}
		}

		if (N >= 10) {
			//자릿수 1, 10, 100~ 이런식으로 구해준다
			int jarisu = 1; 	//	리스트 안에 들어있는 것들은 jarisu 크기
			Label: while (cnt != N) {
				ArrayList<Long> list2 = new ArrayList<>(); // 구한 다음 자릿수 넣어주기
				boolean check = false;	// 해당 자릿수에서 없으면 감소하는 수 없으므로 그거 찾아주기 위해
				for (long i = 1; i < 10; i++) {

					for (long a : list) {
						if (i > a / jarisu) {// 리스트안에는 모두 감소하는 수가 들어있으므로 가장 앞자리 수만 비교
							check = true;
							cnt++;

							long result = i * (10 * jarisu) + a;
							list2.add(result);

							if (cnt == N) {

								System.out.println(result);
								break Label;
							}
						} else {
							break;
						}
					}

				}
				if (check == false) {
					//해당 자릿수에서 없으면 감소하는 수 없었다
					System.out.println(-1);
					break;
				}

				jarisu *= 10;//1~9까지 탐색끝나고 다음 자릿수 탐색
				list = list2;//해당 자릿수 리스트들로 바꿔준다

			}
		}

	}
}

 

풀이

 

1의 자리, 10의 자리, 100 자리 크기 별로 감소하는 수를 구해줬다.

 

(list 1) 리스트 안에 전 자리 크기의 감소하는 수가 들어있다.

 

1~9의 수를 리스트의 가장 앞자리만 비교해서 앞자리보다 크면 list2에 넣어준다.

-> 리스트 안에는 감소하는 수들의 집합이므로 앞자리만 비교함

 

모든 비교가 끝나면 자릿수를 늘려준다 jarisu*=10;

 

 

---

ArrayList list=new ArrayList<>();

ArrayList 맨 앞에 넣어주기

list.add(0,123);    // 리스트 0번째에 123 넣어주기

 

ArrayList 다른 리스트와 합치기

list.addAll(list2);   //리스트 1에 리스트 2 합치기