programmers_가장 큰 수
programmers
# Level 2 # Java # 코딩테스트 연습
정렬) 가장 큰 수 (19.10.08)
* 첫번째로 제출했던 코드.
* numbers 배열의 길이만큼 숫자 배열 arr를 만들어서 모든 순열을 구했다.
* 순열의 순서로 numbers의 원소의 위치를 조정했는데 시간초과가 나왔다.
* 순열로 모든 경우 안보고 두 수를 비교하는 방식으로 코드를 수정했다.
* 첫번째로 제출했던 코드.
* numbers 배열의 길이만큼 숫자 배열 arr를 만들어서 모든 순열을 구했다.
* 순열의 순서로 numbers의 원소의 위치를 조정했는데 시간초과가 나왔다.
* 순열로 모든 경우 안보고 두 수를 비교하는 방식으로 코드를 수정했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.math.BigDecimal;
import java.util.*;
class Solution {
public boolean check = false;
public void swap(int[] arr, int a, int b){
int s = arr[a];
arr[a] = arr[b];
arr[b] = s;
}
public void next(int[] arr, int n){
int p = -1;
for(int i=n-1;i>0;i--){
if(arr[i-1]<arr[i]){
p = i-1;
break;
}
}
if(p<0) {
check = true;
return;
}
for(int i=n-1;i>p;i--){
if(arr[p]<arr[i]){
swap(arr, p, i);
break;
}
}
int q = n-1;
for(int i=p+1; i<q;i++){
if(p<q){
swap(arr, i, q);
q = q-1;
}
}
}
public String solution(int[] numbers) {
int n = numbers.length;
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = i;
}
double max = 0;
while(true){
String as = "";
for(int i=0;i<n;i++){
as = as+numbers[arr[i]];
}
max = Math.max(max,Double.parseDouble(as));
next(arr, n);
if(check) break;
}
BigDecimal bd = new BigDecimal(max);
String answer = bd.toString();
answer = bd.toString();
return answer;
}
}
| cs |
* 순열 대신 새로 작성한 코드.
* ArrayList를 만들어서 숫자를 차례로 각 자리마다 add 해서 비교해줬다.
* 지난번에 썼던 BigDecimal을 사용.
* 일부 시간초과, 일부는 틀렸습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.math.BigDecimal;
import java.util.*;
class Solution {
public String solution(int[] numbers) {
int n = numbers.length;
int ch = 0;
double max = numbers[0];
ArrayList<Integer> list = new ArrayList<>();
String answer = "";
for(int i=1;i<n;i++) {
list.add(ch, numbers[i-1]);
for(int j=0;j<=i;j++) {
String s = "";
list.add(j, numbers[i]);
for(int p : list) {
s = s+String.valueOf(p);
}
if(Double.parseDouble(s)>max) {
max = Double.parseDouble(s);
ch = j;
}
list.remove(j);
}
}
BigDecimal bd= new BigDecimal(max);
answer = String.valueOf(bd);
return answer;
}
}
| cs |
* 시간초과를 해결하려고 길이가 10이 넘는 테스트케이스를 입력했더니
* max 값이 double을 초과해서 값이 틀린거였다.
* 생각해보니까 왜 long을 안쓰고 double을 썼을까.....
* long으로 고쳐주고 시간초과는 없어졌다.
* 근데 왜 틀린거지...? 진짜 게시판 + 자체 테스트케이스 다 돌렸는데 도무지 알수가없다.
* 몇시간 낑낑거리다가 질문글 올렸는데 제발 누가 답좀..... ㅠㅠ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
class Solution {
public String solution(int[] numbers) {
int n = numbers.length;
int ch = 0;
long max = numbers[0];
ArrayList<Integer> list = new ArrayList<>();
for(int i=1;i<n;i++) {
list.add(ch, numbers[i-1]);
for(int j=0;j<=i;j++) {
String s = "";
list.add(j, numbers[i]);
for(int p : list) {
s = s+String.valueOf(p);
}
if(Long.parseLong(s)>max) {
max = Long.parseLong(s);
ch = j;
}
list.remove(j);
}
}
String answer = String.valueOf(max);
return answer;
}
}
| cs |
댓글
댓글 쓰기