Today Sulim Learned

silver 5. 30(10610)

27 Jan 2022 | 알고리즘 프로그래밍 자바

silver 5. 30 (10610)

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

문제

입력된 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들어주는 프로그램

입력: N를 입력받음. N은 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않음

출력: 주어진 숫자로 30의 배수를 만들 수 있다면, 만들 수 있는 30의 배수 중 가장 큰 수 출력. 만들 수 없다면, -1를 출력

풀이

  • 아이디어: 30의 배수는 마지막 자리가 항상 0이고, 각 자리수의 합이 3의 배수가 되어야 함
    • StringBuffer로 입력된 변수를 저장하고 for문을 통해 각 자리수를 더해줌
    • 각 자리수의 합이 3의 배수인 경우, 주어진 수로 만들 수 있는 가장 큰 30의 배수를 찾기 위해 각 자리수를 정렬해주어야 함
      • StringBuffer 변수의 경우 정렬해주는 함수가 없으므로 char형 배열로 변경해 sort()를 수행
      • sort()의 결과는 오름차순이므로, StringBuffer 변수로 값을 받아와 reverse() 연산을 수행함
      • 연산을 마치면 정수형으로 형 변환 해준 뒤 출력
    • 각 자리수의 합이 3의 배수가 아닌 경우, 입력받은 수로 30의 배수를 만들어줄 수 없으므로 -1를 출력

1차 코드

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        StringBuffer tmp = new StringBuffer(sc.nextLine());
        int result = 0;
        
        // 각 자리 수를 모두 더해 result에 저장
        for (int i=0; i<tmp.length(); i++){
            result += tmp.charAt(i);
        }
        
        // result가 3의 배수인 경우 (입력받은 숫자로 30의 배수를 만들 수 있는 경우)
        if (result % 3 == 0){
            char[] cArr = tmp.toString().toCharArray();	// 정렬을 위해 char형 배열로 생성
            Arrays.sort(cArr);	// 오름차순으로 정렬
            tmp = new StringBuffer(new String(cArr)).reverse();	// Stringbuffer에 저장 후 내림차순으로 변경
            System.out.println(Integer.parseInt(tmp.toString()));	// 정수형으로 형변환 후 결과를 보여줌
        }
        else{	// result가 3의 배수가 아닌 경우 (입력받은 숫자로 30의 배수를 만들 수 없는 경우)
            System.out.println(-1);
        }   
    }
}

  • 결과

    • Replit에서는 잘 돌아가지만, 백준에 제출할 경우 Runtime Error 발생

    • 아직 어느 부분이 문제인지 발견하지 못 함 (2022-01-28 문제점 발견)
    • 문제점: input의 최댓값은 자리수가 10^5(십만 자리)인 수. 하지만 int형이 담을 수 있는 최댓값은 20억(10자리)까지이므로 출력해주는 과정에서 int형으로 형변환해서 출력할 경우 런타임 에러(NumberFormat)이 발생
      • NumberFormat: 문자열을 수로 변환할 때 발생하는 에러

2차 코드

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        StringBuffer tmp = new StringBuffer(sc.nextLine());
        int result = 0;
        
        for (int i=0; i<tmp.length(); i++){
            result += tmp.charAt(i)-'0';
        }
        
        if (result % 3 == 0){
            char[] cArr = tmp.toString().toCharArray();
            Arrays.sort(cArr);
            StringBuffer num = new StringBuffer(new String(cArr)).reverse();
            System.out.println(num.toString());	// 수정
        }
        else{
            System.out.println(-1);
        }   
    }
}
  • 출력할 때 int형으로 형변환해주지 않고 문자열로 출력해주는 코드로 변경
  • 결과
    • 백준에 제출했을 때 출력 초과 발생
    • 원인: 30의 배수이기 위해서는 input 값에 0이 포함되어 있어야 하는데 input 값에서 0의 존재를 확인하는 조건을 빼먹음

3차 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        StringBuilder num = new StringBuilder(sc.nextLine());
        int sum = 0;
        
        for (int i=0; i < num.length(); i++){
            sum += num.charAt(i);
        }
        
        if (num.toString().contains("0") && (sum % 3 == 0)){	// 수정
            char[] cArr = num.toString().toCharArray();
            Arrays.sort(cArr);
            num = new StringBuilder(new String(cArr)).reverse();
            System.out.println(num.toString());
        }
        else {
            System.out.println(-1);
        }
    }
}
  • if문 조건에 input 값에서 0의 존재를 확인하는 코드 추가
  • StringBuffer 대신 StringBuilder 사용
    • 이유: StringBuffer는 멀티 쓰레드 환경에서 동기화 때문에 사용하는 것이기 때문에 알고리즘같은 단일 쓰레드 환경에서는 StringBuilder가 성능이 더 좋음

배운점

Related Posts