[BaekJoon] 백준 10610번 _ 30 for JAVA _ 그리디 알고리즘

 

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

10610번: 30

 

 

 

문제

 

 

 

---

 

 

문자열 문제는 증말 어렵다..

 

 

30의 배수임을 알아볼 때의 조건

 

1. 1의 자리가 0으로 끝남

2. 10~n의 자리가 3의 배수임

3. 3의 배수라는 것은 모든 자리의 수를 더했을 때 값이 3의 배수임을 뜻한다.

 

 

여기서 3번이 제일 중요함.

 

1의 자리가 0이고 각 자리 숫자의 합이 3의 배수이면 입력받은 수를 내림차순으로 정리한게 가장 큰 수가 된다.

 

어차피 1의 자리가 0이어야 하므로... 걍 내림차순 해주면 됨

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;


public class Baek10610 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String N = br.readLine();
		
		String[] number = N.split("");
		int count = 0;

		
		Arrays.sort(number, Collections.reverseOrder()); // 내림차순으로 정렬
		
		String answer = "";
		for(int i = 0; i < number.length; i++) {
			count += Integer.parseInt(number[i]);  // number[]가 string이니까 int형으로 바꿔서 더함
			answer += number[i];
		}
		
		
		if(count % 3 == 0 && Integer.parseInt(number[number.length - 1]) == 0) // 그냥 string형으로 "0"인지 확인하면 오류난다
			System.out.println(answer);
		else {
			System.out.println("-1");
		}
	
	}

}

 

 

 

요거...자료형이 왔다갔다 해서 짜는데 오래걸렸다ㅠㅠ

 

 

주의할것은 원래 number[] 배열의 자료형을 char로 선언하고

 

 

charAt() 으로 배열에 저장한 뒤

 

Arrays.sort(number, Collections.reverseOrder()); 를 하려고 했는데

 

char 자료형인 배열은 Collections.reverseOrder()이 안된다!!!!

 

 

그래서 그냥 Arrays.sort() 해주고 반복문 등으로 거꾸로 저장을 다시 해주거나...해야함

 

 

 

복잡해서 그냥 string 자료형으로 바꾸고 split 사용했다.

 

 

 

 

 

 

성능

 

 

그리 좋지 않은 성능.... 메모리랑 시간 차리가 좀 많다. 왜징

 

 

 

 

---

 

남의 코드 살펴보기

 

 

 

 

 

 

N이라는 char형 배열에 저장한 뒤

 

 

오름차순으로 정렬해주고 배열의 1의자리 (N[0]) 가 0이 아니면 -1 출력한다.

 

 

아~ char형 배열을 사용했으므로 int화 하기 위해 N[] - '0' 을 사용하였다.

 

 

 

그리고 char형을 내림차순으로 바꾸기 위해 StringBuilder를 선언하여 N 배열을 넣고 reverse() 해주었다.