[가장 큰 수]
https://programmers.co.kr/learn/courses/30/lessons/42746
문제 재정의:
numbers배열이 주어짐 (input)
numbers 배열에 있는 숫자를 조합하여 가장 큰 수를 만들어 '문자열로' return
numbers의 길이는 1 이상 100,000 이하, numbers의 원소는 0 이상 1,000 이하
예외 테스트 케이스
0, 0, 0, 0 -> 0
0, 1000, 0, 0 -> 100000
12, 121 -> 12121
21, 212 -> 21221
[0,0,0,1000]
[0,0,1000,0]
[1000,0,0,0]
틀리기 쉬운 입출력 예제
(출처:https://stroot.tistory.com/114[Strong Root])
입력 | 출력 |
---|---|
{40, 403} {40, 405} {40, 404} {12, 121} {2, 22, 223} {21, 212} {41, 415} {2, 22} {70, 0, 0, 0} {0, 0, 0, 0} {0, 0, 0, 1000} {12, 1213} |
40403 40540 40440 12121 223222 21221 41541 222 70000 0 1000000 121312 |
구현할 때 참고한 사이트
- x자릿수 쪼개서 저장하는 법
- int형 숫자의 자리수 구하기
String형 문자열의 길이는 length 함수를 이용해서 쉽게 구할 수 있지만, int형 숫자의 자릿수를 구할 때는 수학적 함수를 사용해야 한다.
(int)(Math.log10(num)+1)
int num = 3648; int length = (int)(Math.log10(num)+1); System.out.println("길이 : " + length);
- 자바 정렬 Comparable, Comparator, Sort() 확실히 알기
https://javaplant.tistory.com/15
https://cwondev.tistory.com/15
- 내 코드에 사용된 comparator
생각한 방법
만약 input이 9, 30, 34라면
9 | 9 | -1 | -1 |
30 | 3 | 0 | -1 |
34 | 3 | 4 | -1 |
처럼 각 숫자의 자릿수를 쪼개서 2차원 배열을 만드는 것임
2열을 sort 하고 -> 그다음 3열을 sort 하는 방식
- 2차원 배열 만드는 코드
//split 해서 각 행에 각 자리의 숫자 집어넣기. (숫자가 없는 곳은 -1을 집어넣음)
/*
자리수 체크하는 코드
public static int check(int x){
return (int)(Math.log10(x)+1);
}
*/
for(int j=0;j<numbers.length;j++){
temp=v[j][0];
cases=check(temp);
switch(cases){
case 1 : //1의 자리
v[j][1]=temp;
v[j][2]=-1;
v[j][3]=-1;
break;
case 2 : //10의 자리
a=Integer.toString(temp);
v[j][1]=a.charAt(0)-'0';
v[j][2]=a.charAt(1)-'0';
v[j][3]=-1;
break;
case 3: //100의 자리
a=Integer.toString(temp);
v[j][1]=a.charAt(0)-'0';
v[j][2]=a.charAt(1)-'0';
v[j][3]=a.charAt(2)-'0';
break;
}
}
그 대신 sort 할 때 행이 다 같이 움직여야 함. (comparator를 이용함)
- 정렬하는 부분 코드
public static void ArraysSort2(int[][] arr, final int index_num, int from, int to){
Arrays.sort(arr,from,to+1, new Comparator<int[]>(){
public int compare(final int[] entry1, final int[] entry2){
final int time1=entry1[index_num];
final int time2=entry2[index_num];
return Integer.compare(time2,time1);
}
});
}
매개 변수 설명: ArraysSort2(배열 이름, 몇 열을 정렬할 건지, 몇 행부터, 몇 행까지 정렬할 건지)
from과 to 가 있는 이유) 33, 35, 9를 정렬해야 할 때 첫 자릿수가 '3'으로 같은 애들만 비교하기 위해 from 과 to를 설정함
- 앞 자리수가 같은 경우의 행을 반환(30과 34의 경우)하는 코드
그럼 위 예제처럼 앞 자릿수가 '3'으로 같은지 비교하는 메서드는 아래와 같음. from과 to를 배열에 저장해 반환
public static int[] isSame(int[][] a, int x){
int[] from_to = new int[a.length];
int from=0, to=0;
int pivot=a[0][x];
for(int i=1;i<a.length;i++){
if(pivot==a[i][x]){
to++;
}
else{
from=i;
pivot=a[i][x];
to=i;
}
}
from_to[0]=from;
from_to[1]=to;
return from_to;
}
문제점 (예외가 너무 많이 발생)
단적인 예로)
만약 input이 30, 34, 3이라면
'34-3-30' 이어야 하는데
내 코드에 의하면 '34-30-3'이 됨
-> 한 자릿수를 중간에 끼워 넣을 수 있는 경우의 수를 생각하지 못함.
sol1)
스터디 팀원분이 2차원 배열. 일의 자릿수에 -1 말고 그 수를 채우자는 아이디어를 주심
sol1- prob)
30, 3, 34는 '34330'으로 잘 정렬됨
40, 403은 틀린 답 '40340'이 나옴
__이뿐만 아니라 예외가 많이 발생해 복잡해져 버리기,,, __
내가 생각한 아이디어는 뒤집어엎어버리기로 함
https://developerdk.tistory.com/24 님의 해답을 봄
-> int형을 일단 string을 변경함
-> comparator 이용해서 정렬함( 2개씩 더한 후, 비교해서 정렬되는 방식)
-> 0000은 0 이 되게 예외처리해줌
이 방법은 코드가 50줄도 안 나온다...
반성
1. sort(), comparator, comparable를 사용한다는 것까진 왔으나, 이에 대해 깊이/이해하지 않고, 더 어렵게 생각해서 풂.
2. 그리고 string형 합칠 때 +가 아닌, String.valueOf()를 사용하는 게 더 효율적이라는 것을 깨달음
"java convert int to string"
char c = 'a'; String s = String.valueOf(c); // fastest + memory efficient String s = Character.toString(c); String s = new String(new char[]{c}); String s = String.valueOf(new char[]{c}); String s = new Character(c).toString(); String s = "" + c; // slowest + memory inefficient
https://developerdk.tistory.com/24
참고 : https://stackoverflow.com/questions/8172420/how-to-convert-a-char-to-a-string
'ALGORITHM > Implement' 카테고리의 다른 글
[JAVA] 백준 1789번 (0) | 2019.09.01 |
---|---|
[JAVA] 백준 10871번 (0) | 2019.09.01 |
[JAVA] 백준 2455번 (0) | 2019.08.25 |
[JAVA] 백준 1173번 (0) | 2019.08.17 |
[JAVA] 백준 1592번 (0) | 2019.08.17 |
Comments