[Programmers] Lv2. 마법의 엘리베이터
09 Jan 2023
Reading time ~2 minutes
해당 문제는 프로그래머스 마법의 엘리베이터에서 풀어보실 수 있습니다.
생각할 포인트
1. 숫자가 5인 경우 그 왼쪽에 있는 숫자를 보고 판단해야 하는데 해당 로직을 넣지 않아서 반례를 찾느라 오래 걸림.
오른쪽에서 하나씩 결정하다가 숫자 5를 만났을 때 왼쪽에 있는 숫자가 5이상 이면 올림하는 경우가 더 적은 횟수. 이 부분을 캐치하지 못해서 if이하 부분을 추가하지 않고 주석처리한 부분의 3번 과정까지만 진행했더니 9555나 5555같은 입력 값에서 잘못된 결과가 출력되었음. if(i-1 >= 0 && numbers[i-1] >= 5) 부분을 추가하여 해결하였음.
2. 올림할 자리를 한 자리 더 만들어 주어야 했음.
numbers 배열의 길이를 numbersLength+1로 올림할 한 자리를 감안해서 1만큼 크게 생성함.
3. 중첩된 if문과 else 키워드를 모두 삭제하면 더 가독성 좋은 코드로 개선할 수 있었음.
아래 메서드를 들여쓰기 depth를 2로 최소화 하여 깔끔하게 변경할 수 있었음.
자세한 내용은 중첩 if문 제거 과정에서 확인
public int solveWithGreedy(int storey){
int answer = 0;
int numbersLength = getLength(storey);
int[] numbers = getSplitNumbers(storey);
for(int i = numbersLength; i >= 0; i--) {
int number = numbers[i];
if(number == 5){
answer += 5;
if(i-1 >= 0 && numbers[i-1] >= 5){
numbers[i-1]++;
}
} else if(number > 5) {
answer += (10 - number);
if(i-1 >= 0) {
numbers[i-1]++;
}
} else {
answer += number;
}
}
return answer;
}
그리디(Greeedy) 풀이 구현
class Solution {
/**
*
* @author ryureka
* 1. 숫자를 1의 자리에서부터 왼쪽으로 가면서 한 자리씩 확인한다.
* 2. 확인하는 숫자가 5보다 작으면 그 자리수 숫자를 1씩 빼서 0으로 만든다.
* 3. 5보다 크면 그 자리수의 숫자를 1씩 더해서 자리수 올림한다.
* 4. 5일 때는 판단을 보류한 후 다음 숫자를 보고 판단해서 5보다 크거나 같으면 자리수 올림한다.
*
*/
public int solution(int storey) {
return solveWithGreedy(storey);
}
public int solveWithGreedy(int storey){
int answer = 0;
int numbersLength = getLength(storey);
int[] numbers = getSplitNumbers(storey);
for(int i = numbersLength; i >= 0; i--) {
int number = numbers[i];
if(number < 5) {
answer += number;
continue;
}
answer += (10 - number);
if(i-1 < 0) {
continue;
}
if(number == 5 && numbers[i-1] < 5) {
continue;
}
numbers[i-1]++;
}
return answer;
}
// 정수의 길이를 리턴.
public int getLength(int number) {
int length = 0;
while(number > 0){
number /= 10;
length++;
}
return length;
}
// 정수의 자리수에 해당하는 숫자들을 하나씩 가져와 배열로 저장해 리턴.
public int[] getSplitNumbers(int number) {
int numbersLength = getLength(number);
int[] numbers = new int[numbersLength+1];
int count = 0;
while(number > 0) {
int indexOfNumbers = numbersLength - count;
numbers[indexOfNumbers] = number % 10;
number /= 10;
count++;
}
return numbers;
}
}