[프로그래머스] 1. [카카오 인턴] 키패드 누르기 (Lv1), 2. k진수에서 소수 개수 구하기 (Lv2), 3. 프린터 (Lv2)

손규성·2022년 10월 25일
0

alogrithm

목록 보기
12/22
post-thumbnail

Lv. 1: [카카오 인턴] 키패드 누르기✍️


문제 설명

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

  • 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
  • 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
  • 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
  • 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

제한사항

  • numbers 배열의 크기는 1 이상 1,000 이하입니다.
  • numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
  • hand는 "left" 또는 "right" 입니다.
    - "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
  • 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

나의 답안

function keyIs(x) {
    let phone = [
        ['1', '2', '3'],
        ['4', '5', '6'],
        ['7', '8', '9'],
        ['*', '0', '#']
    ];

    for(let i = 0; i < phone.length; i++) {
        for(let j = 0; j < phone[i].length; j++) {
            if(phone[i][j] == x) return [i, j];
        }
    }
}

function solution(numbers, hand) {
    let answer = '',
        L = '*',
        R = '#';

    for(let i = 0; i < numbers.length; i++) {
        let str = numbers[i].toString();

        //1. when numbers[i] is only pushable with a certain hand 
        if(str === '1' || str === '4' || str == '7') {
            answer += 'L';
            L = str;
        } else if(str === '3' || str === '6' || str === '9') {
            answer += 'R';
            R = str;
        }

        //2. when numbers[i] is in the middle 
        else {
            let leftIdx = keyIs(L); 
            let rightIdx = keyIs(R);
            let strIdx = keyIs(str);
            let leftSteps = Math.abs(leftIdx[0] - strIdx[0]) + Math.abs(leftIdx[1] - strIdx[1]);
            let rightSteps = Math.abs(rightIdx[0] - strIdx[0]) + Math.abs(rightIdx[1] - strIdx[1]);

            if(leftSteps > rightSteps) {
                answer += 'R';
                R = str;
            } else if(rightSteps > leftSteps) {
                answer += 'L';
                L = str; 
            } else if(rightSteps === leftSteps) {
                if(hand === 'left') {
                    answer += 'L';
                    L = str;
                } else {
                    answer += 'R';
                    R = str;
                }
            }
        }
    }
    return answer; 
}

접근 방식:

  1. 그나마 가독성이 조금 좋은 코드를 작성하기 위해 두 개의 함수를 사용했다.
    A. 첫 번째 함수 keyIs()는 전화기의 키패드 모습을 한 이차원 배열을 이중배열로 순회하면서 각 입력값의 인덱스 값을 [i, j]형태로 반환한다.
    B. 두 번째 함수 solution()에서는 keyIs() 함수를 사용해서 현재 왼손/오른손 위치에서 다음 숫자의 위치까지 이동하는 거리를 계산한다.
    C. 만약 오른손이 이동해야 하는 거리와 왼손이 이동해야 하는 거리가 같은 경우에는 매개번수로 받은 hand 값을 참고해서 더 익숙한 손을 움직인다.

  2. 추가로 왼손이나 오른손만 움직일 수 있는 경우에는 상황에 맞게 왼손이나 오른손 값만 업데이트 해주었다.

  3. 인덱스의 차이를 계산할 때는 위 아래로 움직여야할 때 모두를 고려해서 Math.abs 메서드를 사용했다.

회고:

  • 최근 알고리즘 스터디에 참여하게 되어서 일주일에 4번씩 Level 1 문제 1개, Level 2 문제 2개를 풀이하고 있는데, 이 문제는 Level 1 임에도 불구하고 오늘 풀었던 문제 중 가장 어려웠다. 문제의 난이도 자체가 높다기 보다는 중간 중간 고려할 점이 많아서 푸는데 생각보다 오랜 시간이 걸렸다.

  • 손을 한번 움직일 때마다 인덱스 값을 어떻게 다룰지에 대해 생각하느라 시간을 많이 썼는데, 이 부분을 해결하고 나니 나머지 로직을 구현하는 것은 크게 어렵지 않았다.

  • 문제를 풀고나서 코드가 너무 길어서 이게 과연 최선의 풀이 방법인지에 대해 고민을 조금 했다. 근데 막상 다른 사람들의 풀이를 보니 대부분의 사람들이 나와 비슷하게 풀었다는 점에서 위안을 받았다.


Lv. 2: k진수에서 소수 개수 구하기✍️


문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

  • 0P0처럼 소수 양쪽에 0이 있는 경우
  • P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
  • 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
  • P처럼 소수 양쪽에 아무것도 없는 경우
  • 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
    - 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • 1 ≤ n ≤ 1,000,000
  • 3 ≤ k ≤ 10

나의 답안

function isPrime(num) {
    if(num === 1 || num === 0) return false;

    for(let i = 2; i * i <= num; i++) {
       if(num % i === 0) return false;
    } 

    return true;
}

function solution(n, k) {
    let test = '',
        count = 0,
        arr = [],
        num = n.toString(k);

    for(let i = 0; i < num.length; i++) {
        if(num[i] === '0' && test.length > 0) {
            arr.push(Number(test));
            test = '';
        } else test += num[i];
    }

    if(test.length > 0) arr.push(Number(test));

    for(let i = 0; i < arr.length; i++) {
        if(isPrime(arr[i]) === true) count++;
    }

    return count;
}

접근 방식:

  1. 우선 매개변수로 받은 nk 진수로 변환해준다.

  2. k 진수로 변환된 num 값을 순회하면서, num[i] 값이 0이 아닌 경우 test 값에 현재 값을 추가해준다. 반대로 0이 나오는 경우 현재까지 누적된 test 값을 arr 배열에 숫자로 변환해서 담아주고, test 값은 초기화해준다.

  3. for문이 끝난 후에 남은 test 값의 길이가 0보다 큰 경우, 즉 뭐라도 들어있는 경우 배열에 담아준다.

  4. 새로운 for문을 통해 arr 배열을 순회하면서, isPrime() 함수를 사용해서 각 숫자가 소수인지 확인한다. 만약 소수인 경우 count++ 하고 누적된 count 값을 반환한다.

회고:

  • 처음 제출한 코드에서는 isPrime() 함수에서 숫자가 0인 경우는 고려하지 않았다. 이런 경우 12번 테스트 케이스에서만 실패가 뜬다. 숫자가 0인 경우를 꼭 처리해주어야 한다.

  • 문제 설명에 0P0, 0P, ... 등 여러 조건을 헷갈리게 걸어두었지만, 사실 잘 읽어보면 그냥 소수 주변에 0이 있으면 되는 것이다. 편하게 0을 기준으로 num 값을 순회하면 복잡한 로직 없이 풀이 가능하다.

  • 굳이 count 같은 변수를 만들지 말고 마지막에 arr에 filter 사용해서 isPrime() 함수를 통과하는 값만 남은 배열의 length 를 출력했으면 보다 간결한 코드를 작성했을 수 있을 것 같다. (다른 문제 풀이들을 보면 알겠지만 난 count 변수 중독이다)


Lv. 2: 프린터✍️


문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

  • 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
  • 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
  • location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

나의 답안

function solution(priorities, location) {
    let topPriority = Math.max(...priorities),
        count = 0;

    function Element(name, priority, location = 'Not Here') {
        this.name = name;
        this.priority = priority;
        this.location = location;
    }

    let pq = [];
    for(let i = 0; i < priorities.length; i++) {
        let el;
        if(i === location) el = new Element(`paper${priorities[i]}`, priorities[i], 'Here');
        else el = new Element(`paper${priorities[i]}`, priorities[i]);
        pq.push(el);
    }
    
    while(true) {
        for(let i = 0; i < pq.length; i++) {
            if(pq[0].priority < topPriority) {
                pq.push(pq[0]);
                pq.shift();
            } else if(pq[0].priority === topPriority) {
                if(pq[0].location === 'Here') {
                    count++;
                    return count;
                } else {
                    pq.shift();
                    priorities.splice(priorities.indexOf(topPriority), 1);
                    topPriority = Math.max(...priorities);
                    count++;
                }
            }
        }
    }
}

접근 방식:

  1. name, priority, location 정보를 가지고 있는 Element 클래스를 만든다. 이후 priorities 배열을 순회하며 각 인쇄 예정인 종이를 Element로 바꿔주고 pq 배열에 담아준다. 이때 i 값이 location 값과 같은 경우에만 새 Element의 location 값을 Here 로 할당했다.

  2. 이후 pq 배열을 순회하면서 →

    • pq 배열의 첫 번째 값의 priority가 현재 topPriority보다 적은 경우 배열 앞에서 뒤로 이동
    • pq 배열의 첫 번째 값이 priority가 현재 topPriority와 같은 경우, 해당 종이의 location 값이 Here인지 확인한다. location 값이 Here이 아닌 경우 pq에서 빼주고 count를 증가준 후 현재까지 누적된 count 값을 반환한다. 반대로 location 값이 Not Here인 경우 pq에서 빼주고 count를 증가시킨 후 topPriority 값을 업데이트한다.

회고:

  • priorities배열은 priority 값만 포함하고 있기 때문에, priorities 배열만 조작해서 문제를 풀이하는 것 보다는 조금 더 직관적인 로직으로 풀이하고 싶었다. (다른 사람들에겐 직관적이지 않을 수도...)

  • 굳이 Element에 name 값을 할당해줄 필요는 없었다. 이건 혹시 디버깅해야 하면 조금 더 편하게 하려고 임의적으로 할당해준 값이었다. (한번에 풀이 성공해서 디버깅할 필요가 없었다) 마찬가지로 location 값에 i 값을 입력하지 않고 굳이 Here, Not Here 같은 걸 입력한 건 오직 내 재미를 위해서였다. 실제로 진짜 프린터를 상상하면서 재밌게 풀었다.

profile
블로그 이사 → https://sqsung.tistory.com/

0개의 댓글