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

• 그리디 알고리즘