[백준 16496번] 큰 수 만들기 - java

문제 설명

1. 음이 아닌 정수 N개가 들어있는 리스트가 주어진다.

2. 이걸로 만들 수 있는 가장 큰 수를 return한다.

3. 답이 0이면 무조건 0하나만 출력되어야 한다. 0이 아닌 모든 수는 0으로 시작하지 않는다.

풀이 과정

 1. 진짜 쉽게보고 풀었는데 생각보다 난이도가 있었다.. 또 다 풀어놓고 뻘짓해서 시간 엄청 보냈다. 문제의 내용을 잘 읽어봐야 할 것이다.

 2. 먼저 입력은 String으로 입력받는다. 이걸 사용하면 더 쉽게 풀 수 있다.

 3. 입력받은 String들을 배열로 만들고 내림차순으로 정렬한다. <- 이렇게 하면 int를 정렬하는 것과 다르게 사전순으로 정렬이 가능하다.

ex) int로 받았을 때에 [ 1 33 4 ] 을 입력받으면 내림차순 정렬 시 [ 33 4 1 ] 이렇게 된다.

     이걸 String으로   [ 1 33 4 ] 을 입력받으면 내림차순 정렬 시 [ 4 33 1 ] 이렇게 된다.

 4. 그리고 중요한 것이 [ 45 44 43 42 41 4 ] 이렇게 입력받은 경우 가장 큰 수를 만들면 다음과 같다.

-> 45,4,44,43,42,41

     그런데 위의 3까지만 진행하면 이렇게 정렬될 것이다.

-> 45,44,43,42,41,4

     이걸 해결하는 방법을 생각해 보았는데, '4'라는 자리수로 시작하는 경우 숫자 4는 그 자리수로 시작하는 숫자들 중 무조건 맨 뒤에 위치하게 된다.

     이런 식으로 생각하면 숫자 [ 434 4355 4322 43 ] 이렇게 있으면 당연히 43 맨뒤에 위치할 것이다.

     그러면 그냥 위의 43이라는 숫자 자체를 포함하는 숫자가 앞에 존재할 때, 어떤 숫자가 앞에 오는 것이 더 클지를 비교하여 넣으면 될 것이다.

43,4322는 4322,43보다 크다.

 5. 그렇게 숫자의 위치를 바꾸어 주고 만들어진 모든 ArrayList를 이어붙여 출력하면 된다. 참고로 0000이면 0이 나와야 한다.

 

코드

	import java.io.*;
	import java.util.*;
	public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
	String ans = "";
	ArrayList<String> list = new ArrayList<>();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int N = Integer.parseInt(br.readLine()); // 값을 읽어온다.
	String input = br.readLine();
	String num[] = input.split(" "); // 값 만들어주기
	Arrays.sort(num,Collections.reverseOrder()); // 문자를 sort하면 사전순으로 나열됨.(사전순으로 나열하면 31 < 4이다) reverseOrder을 사용하여 큰 수부터 내림차순으로 정렬한다.
	for(String temp : num) list.add(temp); // 그렇게 해서 나누어진 문자들을 ArrayList에 넣는다. 그 이유는 문자를 변경하는 경우가 있기 때문이다.
	int digitNow; // 현재 숫자의 맨 앞 자리수 digitNow
	int digitBefore = -1; // 이전 숫자의 맨 앞 자리수 digitBefore <- 절대 맨 앞 자리수가 -1이 될수 없으므로 시작점은 자리수가 바뀌고 시작함.
	int standard = 0; // 위의 자리수가 바뀌는 경우를 기준으로 구할 필요가 있다.
	for(int i=0; i<N; i++) {
	digitNow = num[i].charAt(0)-'0'; // 현재 숫자 자리수 구함.
	if(digitNow!=digitBefore) { // 이전 숫자 자리수와 현재 숫자 자리수가 다르면.
	standard = i; // 그 바뀌어진 현재 숫자를 기준으로 구함.
	}
	for(int j=standard; j<i; j++) { // 자리수는 9~0까지 있고, 이전 숫자와 자리수가 바뀌었으면 그 때부터 지금 구하는 숫자까지 비교해 준다. 참고로 0부터 해도 되는데 나는 그냥 효율성을 위해 이걸 썼다.
	if(num[j].startsWith(list.get(i))) { // 앞에서 존재하는 숫자들 중 현재 숫자로 시작하는 것이 있다면 (ex 현재숫자 : 3 , 이전숫자 : 30 )
	String comp1 = list.get(i)+list.get(j); // comp1은 그럼 330이 될것이다.
	String comp2 = list.get(j)+list.get(i); // comp2는 303이다.
	if(Long.parseLong(comp1) > Long.parseLong(comp2)) { // 그러면 현재숫자가 이전숫자보다 앞으로 가야한다. 위치를 바꾸어 준다.
	list.add(j, list.get(i)); // ArrayList를 사용하면 앞에다가 끼워넣을 수 있다.
	list.remove(i+1); // 현재숫자 노드 삭제
	break;
	}
	}
	}
	digitBefore = digitNow; // 지금 숫자 자리수를 이전에 저장.
	}
	for(String i : list) { // ArrayList의 모든 숫자를 하나씩 빼가면서 결과 만들기.
	ans += i;
	}
	if(ans.startsWith("0") && ans.endsWith("0")) ans = "0"; // 여기서 2시간정도 쓴듯....00000 -> 0이다 중요하다.
	bw.write(ans+"\n");
	bw.flush(); //남아있는 데이터를 모두 출력시킴
	bw.close(); //스트림을 닫음
	}
	}

view raw 큰 수 만들기 hosted with ❤ by GitHub