항해99 11/9(화) 알고리즘 - 알아서 푼 것들

키패드 누르기

코딩테스트 연습 - 키패드 누르기

class Solution {
    public int distance(int num, int pos){
        int distance = 100;
        int temp_num = 100;

        // 현재 위치가 2 5 8일 경우
        // 1. |num - pos| 값 구하기
        // 2. 3 뺄 수 있으면(세로이동) 3 빼고 거리 + 1
        // 3. 3 뺄 거 다 빼고 1 뺄 수 있게 되면(가로이동) 1 빼고 거리 +1
        // 4. 마지막에 남은게 2일 경우 break;
        if (pos % 3 == 2) {
            temp_num = Math.abs(num - pos);
        }else if (pos % 3 == 1) {
            // 1 4 7일 경우
            temp_num = Math.abs(num - pos);
        }else if(pos %3 == 0){
            // 3 6 9일 경우
            // rPos - 2 : 정확한 거리 결과를 얻어내기 위한 보정
            // ex) rPos = 3, num = 5일 때
            //     5 - 3 = 2로 거리가 0으로 나옴.
            //     5 - 1 = 4여야 거리가 2로 정상적으로 출력됨.
            temp_num = Math.abs(num - (pos - 2));
        }

        distance = getDist(temp_num);

        return distance;
    }
    public int getDist(int num){
        int distance = 0;

        while (num > 0) {
            if (num - 3 >= 0) {
                num -= 3;
                distance++;
            } else if (num == 1) {
                num -= 1;
                distance++;
            } else {
                distance += 2;
                num = 0;
            }
        }

        return distance;
    }
    public int nowLocZeroDist(int num){
        // num이 0일땐 거리가 0이므로 기본값 0 반환
        int distance = 0;

        switch(num) {
            case 8:
                distance = 1;
                break;
            case 5:
                distance = 2;
                break;
            case 2:
                distance = 3;
                break;
        }

        return distance;
    }
    public int objNumIsZero(int pos){
        int distance = 0;

        switch (pos) {
            case 1:         case 3:
                distance = 4; break;
            case 4: case 2: case 6:
                distance = 3; break;
            case 7: case 5: case 9:
                distance = 2; break;
            case 8: case -1:
                distance = 1; break;
            case 0:
                distance = 0; break;
        }

        return distance;
    }
    public int nowLocDefault(int num){
        // num이 0일땐 거리가 0이므로 기본값 0 반환
        int distance = 0;

        switch(num) {
            case 8:
                distance = 2;
                break;
            case 5:
                distance = 3;
                break;
            case 2:
                distance = 4;
                break;
        }

        return distance;
    }

    public String solution(int[] numbers, String hand) {
        // 1 4 7이면 L
        // 3 6 9면 R
        // 2 5 8 0은 현재 위치에서 가까운 손
        // 거리가 같을 경우 hand에 의존

        StringBuilder answer = new StringBuilder();
        int lPos = -1;
        int rPos = -1;

        for (int num : numbers) {
            if (num == 1 || num == 4 || num == 7) {
                // 1 4 7일 경우 왼 손
                lPos = num;
                answer.append("L");
            } else if (num == 3 || num == 6 || num == 9) {
                // 3 6 9일 경우 오른손
                rPos = num;
                answer.append("R");
            } else {
                // 거리 계산을 위한 변수
                // 0을 대상으로 하지 않은 거리 구하기
                int lDist = distance(num, lPos);
                int rDist = distance(num, rPos);

                // 현재 위치가 0 또는 기본값(*, #)일 경우
                if (lPos == 0) {
                    lDist = nowLocZeroDist(num);
                }else if(lPos == -1){
                    lDist = nowLocDefault(num);
                }
                if (rPos == 0) {
                    rDist = nowLocZeroDist(num);
                }else if(rPos == -1){
                    rDist = nowLocDefault(num);
                }

                // 목표가 0일 경우
                if (num == 0) {
                    lDist = objNumIsZero(lPos);
                    rDist = objNumIsZero(rPos);
                }

//                System.out.println("lPos  : " + lPos + " \t rPos  : " + rPos);
//                System.out.println("lDist : " + lDist + " \t rDist : " + rDist);
//                System.out.println("목표 숫자 : " + num);
//                System.out.print("결과 : " );
//                if(lDist < rDist){
//                    System.out.println("lDist 승리!");
//                }else if(lDist > rDist){
//                    System.out.println("rDist 승리!");
//                }else{
//                    if(hand.equals("left")){
//                        System.out.println("lDist 승리!");
//                    }else{
//                        System.out.println("rDist 승리!");
//                    }
//                }

                // 출력구간
                if (lDist < rDist) {
                    lPos = num;
                    answer.append("L");
                } else if (lDist > rDist) {
                    rPos = num;
                    answer.append("R");
                } else {
                    if (hand.equals("left")) {
                        lPos = num;
                        answer.append("L");
                    } else {
                        rPos = num;
                        answer.append("R");
                    }
                }

//                if (Math.abs(lPos + 2 - num) < Math.abs(rPos - num)) {
//                    lPos = num;
//                    answer.append("L");
//                } else if (Math.abs(lPos + 2 - num) > Math.abs(rPos - num)) {
//                    rPos = num;
//                    answer.append("R");
//                } else {
//                    if (hand.equals("left")) {
//                        lPos = num;
//                        answer.append("L");
//                    } else {
//                        rPos = num;
//                        answer.append("R");
//                    }
//                }
                // 가중치로 판단 ( 목표 번호 - pos 위치 )
                // 1. 목표 번호가 4 이상 7 이하일 땐 +3 or -3이면 반드시 거리 1.
                // 2. lpos or rpos == 0이면 -3일때만 거리 1.
                //    %3 == 0 (3 6 9) 이면 -1일 때 거리 1,
                //    %3 == 1 (1 4 7) 이면 +1일 때 거리 1,
                //    %3 == 2 (2 5 8) 이면 +1 또는 -1일 때 거리 1.
                // 3. 목표번호가 lpos+2 또는 rpos보다 크면 목표-pos값이 작은쪽이 가까움
                //              보다 작으면 pos-목표값이 작은쪽이 가까움
                //              같으면 반드시 그 손가락이 승리
                // 왼손 : 258일때 +2 ok
                // 오른손 : 580일때 -2 ok
                // 왼손 : 147일때 +2 ok
                // 오른손 : 369일때 -2 ok
                // 공통 : 2일때 +3 ok, 5일때 +-3 ok, 8일때 -3 ok
                // 0 : 0일때 8이 제일 가까움
            }
        }

        return answer.toString();
    }
}

 

정말 긴 시간과 많은 고민을 한 문제였다.

2차원 배열을 쓰면 쉽게 풀릴 것 같긴 했지만 뭔가 안에 까리한 규칙같은게 있을거라는 막연한 생각으로 배열 없이 풀어봐야겠다는 생각을 했다. 왜냐면..... 카카오니까.....

그래서 많은 시간을 투자했다. 4시간? 5시간? 동안 풀었던 것 같은데, 정말 보통 강한 친구가 아니었다. 이게 어떻게 프로그래머스 레벨 1인가 싶은 난이도였다.

어려운 점은 중앙의 버튼(2 5 8 0)을 처리할 때 나온다. 배열을 쓴다면 대충 이동거리를 구하는 하나의 메소드로 퉁 칠 수 있는 문제

근데 사람들 풀어놓은거 보니 다 배열로 풀었다. 배열로 풀고나니 직관적인 코드가 나왔다. 하지만 배열로 구성한 코드보다 내가 짠 코드가 훨씬 빠르다. 이거 하나는 자신한다. 시간들인 보람이 있었다는 생각이 들 정도로 만족스러운 성과였다.

 

내가 짠 코드의 실행 결과(속도)

좋아요 순위 1위의 실행 결과(속도). 이것보다 몇 배나 느린 코드도 많았다.

솔직히.. 알고리즘 푸는데 가장 일반적인 방법을 사용하지 않는 것은 테스트를 임할 때 있어서는 좋지 않은 것 같다. 이렇게 풀면 난 한 문제 풀고 끝이다. 현실은 만화처럼 문제하나 색다르게 풀었다고 특별하게 봐주거나 그런 일은 없는 것이다. 시험장에서는 무조건 출력결과가 나올 수 있도록 빠르게, 그리고 정확하게 짜는것이 중요할 것이다.

 

하지만 시험은 시험이고 이 문제만큼은 내 방식으로 풀어낸 이 방식이 옳다는 것을 증명해냈다. 자신감은 조금 오른 기분이 든다.

 

왘ㅋㅋㅋㅋ

 

 

약수의 합

코딩테스트 연습 - 약수의 합

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int solution(int n) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= n; i++){
            if(n % i == 0){
                list.add(i);
            }
        }
        for(int i = 0; i < list.size(); i++){
            answer+=list.get(i);
        }
        
        return answer;
    }
}

약수 구해서 list에 넣어주고 answer에 더해주면 끝나는 문제였다. 심플하다.

 

 

예산

코딩테스트 연습 - 예산

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;

        Arrays.sort(d);
        for(int i = 0; i < d.length; i++){
            if(budget >= d[i]){
                budget -= d[i];
                answer++;
            }else{
                break;
            }
        }

        return answer;
    }
}

지문이 장황해서 약간 헤메나 싶었는데 그냥 오름차순 정렬하고 때려박으면 되는 문제였다..... 국어능력테스트였나보다

 

 

최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};

        //문제에서 수가 1이상 1,000,000 이하라고 제시했음
        int divider = 1;
        int multiple = 1000000;

        for(int i = n; i >= 2; i--){
            if(n % i == 0 && m % i == 0){
                divider = i;
                break;
            }
        }

        int plus_val = m;
        while(true){
            if(m % n == 0){
                multiple = m;
                break;
            }else{
                m += plus_val;
            }
        }

        answer = new int[]{divider, multiple};

        return answer;
    }
}

평이한 문제였는데 최대공약수 구하는 로직에서 헤멨다. 쉬운 문제였다.

 

 

나머지가 1이 되는 수 찾기

코딩테스트 연습 - 나머지가 1이 되는 수 찾기

class Solution {
    public int solution(int n) {
        int answer = 0;

        for(int i = 2; i < n; i++){
            if(n % i == 1){
                answer = i;
                break;
            }
        }

        return answer;
    }
}

이런 문제만 나온다면 코딩테스트가 세상 아름답게 보이지 않을까?