CS 일기장
[Boj/11047] 동전 0 코드 리팩토링 본문
https://www.acmicpc.net/problem/11047
1) 리팩토링을 하는 이유
알고리즘에서 시간 복잡도를 중요시 해야한다. 중요시 해야한다. 라고 배우긴 배우는데, 지금껏 시간 1초 차이로 그렇게 떨어져 본 적은 없어서 그냥 풀이가 중요하다고 생각했다. 그러나 알고리즘을 요새 배우고 있는데, 걸린 시간(시간 복잡도)가 빠를수록 중요하다고 슬슬 배우다보니 조금 체감이 되는 것 같다. 그러던 중, 맞추면 장땡이라고 했던 예전 마인드를 최근에 수업을 듣다가 바뀌게 되었다. 항상 코드는 짜기만 하는 것이 중요한 게 아니라 리팩토링이 중요한데, 그것이 문제 풀이에도 적용되어야 실력이 늘 수 있다는 사실을 깨달았다. 그리고 내가 처음에 짠 코드는 이 문제의 의도를 크게 벗어나면서 시간을 많이 잡아 먹었다.
2) 문제 해석
이 문제는 그리디 문제의 대표적인 예시이다. 동전을 적절하게 사용해서, 필요한 동전 갯수의 최솟값을 구하라고 하였다. 최솟값이나 최댓값 등 문제를 구하는 것은 DP나 그리디를 통해 풀 수 있다는 사실을 알게되었다. 내가 한 문제 해석은 다음과 같았다.
1) 최솟값이 되기 위해서는 가장 큰 동전부터 순서대로 나누어주면 된다.
1-1) 이 때, 정렬이 필요하겠다고 생각, 그리고 제일 큰 동전의 단위가 50000, 50000으로 나누어지지 않으면 continue문을 적극 활용해 수행하자고 생각
2) for문이나 while 등의 반복을 돌아, 0원이 될 때 까지 돌자, 안 나누어질 때는 해야할 예외처리에 대한 설명이 없다. -> 안해도 된다는 결론(결국 다 나누어지는 테스트 케이스만 존재하겠구나)
2-1) 그리디 하는 부분은 3가지 부분으로 나눈다.
1) 선택 절차 : 현재 상황에서 최적의 상황을 선택 (앞 뒤 상황을 고려하지 않는다.)
2) 적절성 검사 : 선택된 최적의 상황, 즉 답(해)이, 문제의 조건을 벗어나지 않나 확인하고 예외처리 해줌
3) 해답 검사 : 문제가 해결되었는지 확인하고, 그 부분 되지 않으면 선택 절차로 돌아가기 (결국 반복문이라는 이야기)
이 부분들을 하나의 메소드로 모듈화를 취해주자라고 생각 -> 기능 단위로 분리하는 습관을 들이고, 웹 어플리케이션 개발에 적용하고 싶은 생각
처음 짠 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr, (a, b) -> b - a);
int result = greedy(arr, k);
System.out.println(result);
}
private static int greedy(Integer[] arr, int k) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > k) {
continue;
}
if (k / arr[i] == 0) {
return k / arr[i] + count;
}
count += k / arr[i];
k %= arr[i];
}
return count;
}
}수행 시간 : 184 ms
이 문제를 가장 빨리 푼 사람은, 60ms의 수행시간이 걸렸다.
내 문제점이 무엇인가를 생각해보았다. 그러자 2가지의 문제를 알 수 있었다.
1) 굳이 정렬를 해서, 시간을 낭비해야 할까?
그렇다. 이 문제는 동전의 가치가 오름차순으로 주어진다. 그렇다는 이야기는 다른 입력 케이스에서도, 순서대로 나온다는 것이다.
문제를 똑바로 읽지 않고 풀었다는 의미를 말하는 것 같다.
2) 적절성 검사에 쓸 데 없이 많은 if문
말 그대로다. 그냥 저기 저 문제를 해결하는 count와 k를 구하는 방법은 맞는 로직인데, 그냥 저기다가 if문을 쓰면 바로 해결될 수 있는 문제였는데, 이걸 왜 돌아가서 해결하는지 모르겠다. 0에 대한 예외처리도 0이 될때 break이 되게끔, 설정해봤는데 시간복잡도가 똑같이 나왔다.
수정 후
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
br.close();
int result = greedy(arr, k);
System.out.println(result);
}
private static int greedy(Integer[] arr, int k) {
int count = 0;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] <= k) {
count += k / arr[i];
k %= arr[i];
}
}
return count;
}
}시간 복잡도 : 64ms
확실히 줄은 모습을 볼 수 있었다. 메소드로 빼는 것이 줄어드는지 안 줄어드는지 이것은 잘 모르겠다. 그리고 0에 대한 예외처리를 안해도 if 문이 참이 아니라면 빠르게 loop를 돌 것이다.