https://www.acmicpc.net/problem/10610
10610번: 30
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
ArrayList<Integer> arrList = new ArrayList<Integer>();
String s = br.readLine();
int len = s.length();
Character[] arr = new Character[len];
for (int i = 0; i < len; i++) {
arr[i] = s.charAt(i);
}
boolean have = false;
int sum = 0;
for (int i = 0; i < len; i++) {
sum += Character.getNumericValue(arr[i]);
if (arr[i] == '0') {
have = true;
}
}
// 30의 배수는 0이 있어야하며, 합이 3의 배수
if (have == true && sum % 3 == 0) {
for (int i = 0; i < len; i++) {
arrList.add(Character.getNumericValue(arr[i]));
}
Collections.sort(arrList, Collections.reverseOrder());
for (int i = 0; i < len; i++) {
sb.append(arrList.get(i));
}
System.out.println(sb.toString());
} else {
System.out.println(-1);
}
}
}
|
cs |
문제 풀면서 잘못 생각한 부분
두가지를 잘 못 생각했는데
1. 30의 배수는 모든 자리수의 합이 3의 배수 이다.
30의 배수니까 마지막 자리가 0이면 될 것 같아서 숫자에 0의 유무만 찾고 있었는데 자리수 합이 3의 배수인건 생각도 못했다. -> 놓친부분
2. 숫자에 0의 개수가 두개 일 때를 생각하지 못함.
|
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
|
Character[] newArr = new Character[len + 1];
boolean have = false;
for (int i = 0; i < len; i++) {
if (arr[i] == '0') {
newArr[len] = arr[i];
have = true;
} else {
newArr[i] = arr[i];
}
}
if (have == false) {
System.out.println(-1);
} else {
for (int i = 0; i < len; i++) {
if (newArr[i] == null) {
continue;
}
arrList.add(Character.getNumericValue(newArr[i]));
}
Collections.sort(arrList, Collections.reverseOrder());
int zero = Character.getNumericValue(newArr[len]);
for (int i = 0; i < len - 1; i++) {
sb.append(arrList.get(i));
}
sb.append(zero);
System.out.println(sb.toString());
}
}
|
cs |
위 코드가 처음 짠 코드였는데
예를들어 102가 입력받아지면
newArr을 원래 문자열 길이인 3보다 1큰 4의 크기만큼 배열을 초기 설정해주고,
newArr[3]에 '0'을 넣어주고 (즉 맨끝에 '0'을 넣어주는 방식)
newArr[0]='1'
newArr[1]=null
newArr[2]='2'
로 만들어줬다.
하지만 이러면 문제가 0의 개수가 두개 일때 막히게 되고, null을 정수형으로 바꿔서 AraayList에 넘어갈때도 문제가 생긴다.
|
1
2
3
4
5
6
7
8
9
10
11
|
for (int i = 0; i < len; i++) {
if (arr[i] == null) {
arrList.add(0);
}
arrList.add(Character.getNumericValue(arr[i]));
}
for (int i = 0; i < len; i++) {
arrList.remove(Integer.valueOf(0));
}
|
cs |
물론 이럴줄 알고 null이면 arrList에 들어갈때 0으로 들어가고, 나중에 0인 값을 가진 애들을 arrList에서 삭제해주는 방식을 선택했지만 시간초과에 걸렸다.
문제를 푸는 절차
문자 입력받고 -> 문자에 '0' 있는지 확인, 각자리 수의 합이 3의 배수인지 확인 -> ArrayList에 숫자들 담은 다음에 내림차순 정렬 (그러면 가장 큰 값이 나오게됨) -> StringBuilder 이용해서 문자열로 변환
이러면 0이 몇개인지 중요해지지 않아서 간단하게 문제를 풀어낼 수 있다.
그럼에도 불구하고 잘한 부분
1. 문자열을 이용해서 접근
2. 시간복잡도가 그나마 작은 Collections.sort 이용
'알고리즘 > 그리디' 카테고리의 다른 글
| [java 백준]골드 4/ 1744번 수묶기 (0) | 2022.02.11 |
|---|---|
| [java 백준] 실버 2/1931번 회의실 배정 (0) | 2022.02.08 |
| [java 백준] 실버 4/ 1783번 병든 나이트 (0) | 2022.02.06 |
| [java 백준]브론즈 3/ 2875번 대회 or 인턴 (0) | 2021.09.19 |
| [java 백준] 실버2/11047번 동전 0 (0) | 2021.08.10 |
댓글