드디어 시험 문제를 풀었다🤩 - 그 첫번째, 욕망의 항아ㄹ... 잔돈구하기
- '같은 금액의 잔돈이라면, 높은 금액의 화폐를 많이 가져가도록' 하는 것이 관건.
이런 류의 문제를 '탐욕 알고리즘' 혹은 'greedy' 라고 한다.
(처음에 검색했을 때 욕망의 항아리가 나온건 비밀)
1000원을 내고, 500원, 100원, 50원, 10원 단위로 돌려받도록 하고 싶다.
(원본 문제는 일본이 기준이라 5엔 1엔 단위까지 있었지만, 여기는 생략)
그렇다면 어떤 방법을 사용하는게 좋을까?
public class Main {
public static void main(String[] args) {
Main method = new Main();
int num1 = 160;
System.out.println(method.solution(num1));
}
public int solution(int num) {
int answer = 0;
int tsuri = 1000 - num;
int leng = (int) Math.log10(tsuri) + 1; // 잔돈이 몇자리 수인지 보려는 것.
int i;
for (i = leng - 1; i > 0; i--) {
answer += tsuri / (5 * (int) Math.pow(10, i));
tsuri %= (5 * (int) Math.pow(10, i));
answer += tsuri / (int) Math.pow(10, i);
tsuri %= (int) Math.pow(10, i);
}
return answer;
}
}
내가 선택한 방법: 상용로그를 사용, 10의 거듭제곱을 이용하자.
for문을 감소연산자로 i--로 걸면 큰 수부터 돌아가니까, 10의자리(i=1) 까지만 돌려야지!
그러나 생각처럼 쉽지 않았다 - 트러블(?) 슈팅
어라, 이거 분명히 그 병정개미 구할때 도연님껄 본 기억이 있는데...? 왜 안 구해지지...? 🤔
-> 이런 류 문제의 관건은, 나머지 수를 나눠질 수에 더해서 새로운 나눠질 수로 만들어줘야 한다는 것이다. 뭔가를 따로따로 구하려고 하면 늘 에러가 발생했다.
이를테면 몫을 구하려고 처음 수에서 나눠진 자릿수를 빼버렸더니 바로 멸망.
몫에 마이너스가 붙어 나와서 부호도 왔다갔다, 난리도 아니었더랬다.🤔
이 문제는 그래도 전에 몇번 정도 고생했더니 비교적 수월하게 풀렸다.
그 두번째 - 그냥 1점으로 계산하면 안돼?😖 O 하나에 1점씩 증가하다니.
이 문제의 관건은 크게 세개였는데,
- String을 무엇을 기준으로 자를 것인가
- O만 있을때나 X만 있을때를 어떻게 핸들링할 것인가
- 각 배열에서의 점수의 합을 어떻게 구할까? 1점씩이 아니라 1점 2점 3점으로 느는데.
이에 대해 내 나름의 선택은 이러했다.
- split 기준 -> O말고 X
- O나 X만 있다면 -> X는 replaceAll 하고, O는 원본 스트링 자체로 점수를 구하자
- 각 배열에서의 점수합은 등차수열의 공식을 써야지
그래서 나온 코드가 이것!
public int solution(String s) {
int answer = 0;
String[] spl = s.split("X", -1);
// X를 기준으로 String을 나눠 배열로 만든 것. 이때 spl.length는 X를 기준으로 나눠지는 덩어리 수.
// X가 연달아 연달아 있어도 덩어리 수는 지장 없는데, X가 없으면 문제가 다르다.
// X가 없으면 s.length() = 1+ 2+ 3+ 4+ ... s.length 만큼이 점수
int i, j, leng = 0;
float sum;
for (i = 0; i <= spl.length - 1; i++) { //덩어리 갯수만큼 돌것
for (j = 0; j < spl[i].length(); j++) {
if (!Character.isWhitespace(spl[i].charAt(j))) { // spl의 i번째 문자열이 공백이 아니라면 -> O가 적어도 하나 있다는 뜻이므로, 공백이 된 X자리를 제거 후 O만의 길이(갯수)를 구한다.
spl[i] = spl[i].replaceAll(" ", "");
leng = spl[i].length();
// 이 길이 = O의 갯수이므로, 각각 덩어리에서의 O 갯수를 answer에 더해서 점수 합산을 구할 수 있을 것
} //if문 종료
} //안쪽 for문 종료
if (spl[i].equals("")) { //split된 덩어리가 빈칸일 경우 for문 돌지 않고 지나치게 설정 -> 빈칸인데도 지난 덩어리의 합을 더해가는 것을 막아줌
continue;
}
sum = 0.5f * leng * (leng + 1); // 등차수열의 합공식. 점수를 1 +2 + 3 + ... 해야하므로, 총합은 공차가 1, 초항이 1, 길이가 leng인 등차수열로 봄.
System.out.println("각 덩어리별 점수합계: " + (int) sum);
answer += sum;
System.out.println("총합점수: " + answer);
} // 바깥 for문 종료
return answer;
}
}
구몬 등차수열(?)의 트러블 슈팅은 어떻게?
i < spl.length - 1;
i <= spl.length - 1; - 윗쪽의 부등식을 썼더니 각 배열요소의 끝번까지 가질 않아서, 등호를 넣어 아래 식으로.
if (spl[i].equals("")) {
continue;
}- 안쪽 for문에서 자꾸 배열이 공백일때도(X만 있는 순번의 배열에서도) 이전 배열에서의 점수를 더하길래, 공백이면 for문 돌지 않고 지나쳐버리게.
sum = 0.5f * leng * (leng + 1);- 등차수열의 합 공식 이용.
ex) 초항이 1이라면 1 = (공차)/2 * (길이)^2 + (계수) * (길이) 에서
길이와 공차가 1이므로 1 = 1/2 * 1 + (계수) 여야 하므로 계수 또한 1/2이다.
그런데 IntelliJ에서 1/2을 넣으니 int라고 생각했는지 자꾸 0을 뱉길래, float로 소수인 0.5로 써주었다.
즉, 이 문제에서 n번째 수 까지의 등차수열의 공식 = 0.5 * n^2 * 0.5 * n 이므로 0.5 * n을 뽑아주어 0.5 * n ( n + 1 ) 이라고 써준 것.
이 다음에도 무사히 합류할 수 있을진 모르겠지만, 그래도 좋은 조원들 덕분에 시험 문제를 주어진 만큼 풀수 있어서 기쁘다...🥺🥺!!
