[SWEA][JAVA] 1970. 쉬운 거스름돈(D2에서 발생한 시간초과)

import java.util.Scanner;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
           	int [] money = new int[8];
			int target = sc.nextInt();
            while(target != 0){
            	if(target/50000 >= 1){
                	money[0]++;
                    target -= 50000;
                }else if(target/10000 >= 1){
                	money[1]++;
                    target -= 10000;
                }
                else if(target/5000 >= 1){
                	money[2]++;
                    target -= 5000;
                }
                else if(target/1000 >= 1){
                	money[3]++;
                    target -= 1000;
                }
                else if(target/500 >= 1){
                	money[4]++;
                    target -= 500;
                }
                else if(target/100 >= 1){
                	money[5]++;
                    target -= 100;
                }
                else if(target/50 >= 1){
                	money[6]++;
                    target -= 50;
                }
                else if(target/10 >= 1){
                	money[7]++;
                    target -= 10;
                }
            }
            System.out.printf("#%d\n", test_case);
            for(int i: money){
            	 System.out.printf("%d ", i);
            }
            System.out.println();
		}
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PsIl6AXIDFAUq&categoryId=AV5PsIl6AXIDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=30&pageIndex=1

SW Expert Academy

---

오답노트(푸는 동안 사고과정 및 개선점)

무식한 방법으로 구성했다. 그동안 시간초과가 난 적이 없어서 이번에도 잘 돌아갈 것이라 생각하고 무식하게 짰지만 시간초과를 맛봤다.

여기서 로직을 바꾸지않고 BufferedReader, BufferedWriter, StringBuilder 를 사용한다고 시간초과가 해결이 되지않는다.

이제 로직을 한번 바꿔보자.

---

정답코드

class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T;
        T=Integer.parseInt(br.readLine());

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int[] count = new int[8];
            int target = Integer.parseInt(br.readLine());
            int[] money = {50000, 10000, 5000, 1000, 500, 100, 50, 10};
	
			for(int i=0; i<money.length; i++) {
				if(target>=money[i]) {
					count[i] = target/money[i];
					target %= money[i];
				}
			}
            
            bw.write("#" + test_case + "\n");
            for (int i : count) {
                bw.write(i + " ");
            }
            bw.write("\n");
        }
        br.close();
        bw.close();
    }
}

 

일종의 계수정렬처럼 돌아가게 코드를 작성했다. 참고로 선언과 동시에 초기화를 하는 거지 배열 선언과 초기화 시점이 다르면 에러가 발생한다. target>=money[i] 로 구간을 확인하고 몫을 저장하고, 나머지를 남기면 된다.

 

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^