원하는 것은 뭐든지
99클럽 코테 스터디 23일차 TIL , 마법의 엘리베이터 본문
반응형
문제
풀이
마법의 세계에서 살면 마법으로 왔다 갔다 하면 될 거 같은데 굳이 엘리베이터를 타는 민수는 마법의 돌을 최소만 사용해서 자신의 집에서 0층으로 내려가고 싶다. 이 엘리베이터는 10^c 씩만 움직일 수 있는데 한 번 움직일 때 하나의 돌이 사용된다. 입력으로 층 수가 주어지면 최소로 사용해야 하는 마법의 돌을 구하는 문제이다.
예제로 주어진 16 같은 경우 +1만큼 네 번 -10만큼 두 번 해서 여섯 번이다.
2554는 -1로 네 번 -10으로 다섯 번 -100으로 다섯 번 -1000으로 두 번 해서 16번이다.
제출 1 - 오답
class Solution {
public int solution(int storey) {
int answer = 0;
String str = String.valueOf(storey); //층 수 String으로 변환
int len = str.length(); //층 수 자릿수
int[] storeyArr = new int[len + 1]; //다 나누어버림
for(int i=1;i<=len;i++){
storeyArr[i] = str.charAt(i-1) - '0';
}
for(int i=len;i>0;i--){
if(storeyArr[i] <= 5){ //5랑 같거나 작으면 그냥 더해줌
answer += storeyArr[i];
}else{ //5보다 클 경우 위에 자리가 올라가기 때문에 올려줌
answer += 10 - storeyArr[i];
storeyArr[i-1]++;
}
}
answer += storeyArr[0]; //첫번째 자리 올려줌
return answer;
}
}
설명은 코드에 있는 주석으로 하면 충분하다.
오답인 이유를 찾아봤더니 5랑 같을 경우에도 생각해줘야 할 게 있다.
제출 2 - 정답
class Solution {
public int solution(int storey) {
int answer = 0;
String str = String.valueOf(storey);
int len = str.length();
int[] storeyArr = new int[len + 1];
for(int i=1;i<=len;i++){
storeyArr[i] = str.charAt(i-1) - '0';
}
for(int i=len;i>0;i--){
int tmp = storeyArr[i];
if(tmp < 5){
answer += storeyArr[i];
}else if(tmp > 5){
answer += 10 - storeyArr[i];
storeyArr[i-1]++;
}else{
int up = storeyArr[i-1];
if(up + 1 > 5){
answer += 5;
storeyArr[i-1]++;
}else{
answer += storeyArr[i];
}
}
}
answer += storeyArr[0];
return answer;
}
}
만약 5랑 같을 시에 앞자리의 변화가 생기므로 앞자리의 변화를 미리 생각해 주어야 한다.
예를 들어 275층일 경우 이전에 내가 작성한 코드대로 한다면 -1 다섯 번 +10 세 번 -100 세 번 해서 열한 번인데
위의 앞의 자리까지 고려해 줄 경우 +1 다섯 번 +10 두 번 -100 세 번 해서 열 번으로 끝낼 수 있다.
TIL
- 그리디 알고리즘
반응형
'개발 > 문제풀이' 카테고리의 다른 글
99클럽 코테 스터디 25일차 TIL , Evaluate Division (0) | 2024.08.16 |
---|---|
99클럽 코테 스터디 24일차 TIL , 대충 만든 자판 (0) | 2024.08.14 |
99클럽 코테 스터디 22일차 TIL , 멀리 뛰기 (0) | 2024.08.12 |
99클럽 코테 스터디 21일차 TIL , 피보나치 수 (0) | 2024.08.11 |
99클럽 코테 스터디 20일차 TIL , 큰 수 만들기 (0) | 2024.08.10 |
Comments