2.6프로그래머스 Lv.1 #71~80

개요

프로그래머스에 자바스크립트로 풀 수 있는 Lv.1 문제는 총 82문제가 있다. 정답률 높은 문제 순, 71 ~ 77번 문제 풀이 중 배울 점이 있는 풀이들에서 배운 개념들을 내 것으로 만들고자 정리해본다.

원래대로라면 80번까지여야겠지만, 정답률 높은 문제 순으로 풀다보니 갈수록 정리해야할게 많아지고 코드도 긴 문제들이되어서 한번 중간에 끊는다.

71. 키패드 누르기

키패드 누르기는 번호 입력 배열과 어느손 잡이인지 정보가 주어지면, 해당 번호 입력을 어느 손으로 했는지 문자열로 반환하는 문제다. 참으로 현실성 있는 설정에 쓸데없는(?) 문제라고 생각했다.

개인적으론 좀 지저분하게 풀었다. 휴대전화 번호판을 우선 하나의 배열로 만들고, 특정 번호와 번호 간의 간격을 구하는 함수를 만들었다. 이후 1, 4, 7이면 고민없이 왼손으로, 3, 6, 9면 고민없이 오른손으로 누르되 그 외는 거리를 구해서 가까운 손으로 누르고, 거리가 같으면 어느손 잡이인지를 체크해서 반환했다.

javascript
const numPad = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]];

function getDistance(number, target){
    let nc = 0, nr = 0, tc = 0, tr = 0;
    for(let i = 0; i < numPad.length; i++){
        for(let j = 0; j < 3; j++){
            if(numPad[i][j] === number){
                nc = j;
                nr = i;
            }
            if(numPad[i][j] === target){
                tc = j;
                tr = i;
            }
        }
    }
    return Math.abs(nc - tc) + Math.abs(nr - tr);
}

function solution(numbers, hand) {
    let result = "";
    const leftSet = new Set([1, 4, 7]);
    const rightSet = new Set([3, 6, 9]);
    const leftRecord = [];
    const rightRecord = [];
    
    for(let i = 0; i < numbers.length; i++){
        let num = numbers[i] === 0 ? 11 : numbers[i];
        if(leftSet.has(num)){
            result += "L"
            leftRecord.push(num);
            continue;
        } else if(rightSet.has(num)){
            result += "R"
            rightRecord.push(num);
            continue;
        } else {
            const dl = getDistance(num, (leftRecord[leftRecord.length - 1] ?? 10));
            const dr = getDistance(num, (rightRecord[rightRecord.length - 1] ??  12));
            if(dl > dr){
                result += "R"
                rightRecord.push(num);
                continue;
            } else if (dr > dl){
                result += "L"
                leftRecord.push(num);
                continue;
            } else if (dr === dl){
                if(hand === "left"){
                    result += "L"
                    leftRecord.push(num);
                } else {
                    result += "R"
                    rightRecord.push(num);
                }
            }
        }
    }
    
    return result;
}

71-1. 개선

우선 getDistance가 매 호출마다 키패드 전체를 이중 for문으로 훑는데, 좌표로 저장을 해두면 맨해튼 거리 계산법으로 O(1)로 줄일 수 있다.

또, 왼손으로 누른 버튼들과 오른손으로 누른 버튼들의 목록을 모두 저장할 필요가 없다. 현재 위치만 변수 두 개로 관리하면 충분하다.

Set은 나름 has를 이용해 성능 개선을 위해 쓴 것이지만, 사실 좌/우 열이 고정이므로 그냥 좌표의 column(0, 1, 2)로 분기해도 충분하다.

코드로 고치면 아래와 같다.

javascript
function solution(numbers, hand){
  // [row, col] 좌표
  const pos = {
    1: [0,0], 2: [0,1], 3:[0,2],
    4:[1,0], 5:[1,1], 6:[1,2],
    7:[2,0], 8:[2,1], 9:[2,2],
    10:[3,0], 11:[3,1], 12:[3,2]
  };

  const preferRight = hand === 'right';
  let left = 10; // *에서 시작
  let right = 12; // #에서 시작
  const out = [];

  const dist = (a, b) => {
    const [ar, ac] = pos[a];
    const [br, bc] = pos[b];
    return Math.abs(ar - br) + Math.abs(ac - bc);
  };

  for(let n of numbers){
    if(n=== 0) n = 11;
    const [, c] = pos[n]; // 열기준으로 좌/우/가운데 판단

    if(c === 0){
      out.push("L");
      left = n;
    } else if (c === 0){
      out.push("R");
      right = n;
    } else {
      const dl = dist(left, n);
      const dr = dist(right, n);
      if(dl < dr || (dl === dr && !preferRight)){
        out.push("L");
        left = n;
      } else {
        out.push("R");
        right = n;
      }
    }
  }
  return out.join("");
}

71-2. 행

javascript
function solution(numbers, hand) {
  const preferRight = hand === 'right';
  const rowRank = [1, 4, 4, 4, 3, 3, 3, 2, 2, 2]; // 행별 가중치, 0~9 순서

  let L = [1, 1]; // 맨 밑-왼쪽 시작
  let R = [1, 1]; // 맨 밑-오른쪽 시작
  const out = [];

  for (let x of numbers) {
    if (x === 1 || x === 4 || x === 7) {
      L = [rowRank[x], 1]; // 사이드
      out.push('L');
      continue;
    }
    if (x === 3 || x === 6 || x === 9) {
      R = [rowRank[x], 1]; // 사이드
      out.push('R');
      continue;
    }

    // 가운데 열(2,5,8,0)
    const distL = Math.abs(rowRank[x] - L[0]) + L[1];
    const distR = Math.abs(rowRank[x] - R[0]) + R[1];

    if (distL < distR || (distL === distR && !preferRight)) {
      L = [rowRank[x], 0]; // 가운데로 이동
      out.push('L');
    } else {
      R = [rowRank[x], 0];
      out.push('R');
    }
  }
  return out.join('');
}

72. 신규 아이디 추천

신규 아이디 추천은 정규표현식을 아는지 묻는 문제라 봐도 과언이 아니다.

이 문제를 푸는 동안 계속 또 정규표현식을 정리한 게시물을 뒤져가면서 풀었는데, 한번 다시 여기서 필요한 내용들을 정리하고자 한다.

이 문제는 총 7단계로 구성되어 있는데, 그 중 4단계까지가 정규표현식이 들어간다. 하나씩 살펴보자.

• 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 이건 그냥 String.prototype.toLowerCase()를 쓰면 된다. 굳이 이터러블을 하나하나 순회하며 할 필요 없이, 전체에 쓰면 다 바뀐다.

javascript
let s = new_id.toLowerCase();

• 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.

문자집합이므로 /[]/를 쓰고, ~~를 제외한 문자를 찾아서 제거하는 것이므로 /[^]/로 시작한다. 알파벳 소문자, 숫자, -, _, .이므로 /[^a-z0-9-_.]/를 써주고, 마지막에 전역 검색을 의미하는 g 플래그를 붙인다.

javascript
s.replace(/[^a-z0-9-_.]/g, '')

• 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.

마침표를 의미하려면 /./를 해야하지만 .은 임의의 문자 한개를 지시하는 와일드카드 문자이므로 escape를 해서 /\./를 써야 한다. 또, 2개 이상을 찾아야하므로 n회 이상을 의미하는 {n, }와 전역 검색 플래그 g를 넣어 /\.{2n}/g로 검색한다.

javascript
s.replace(/\.{2,}/g, '.');

• 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.

처음은 /^/, 끝은 /$/이고 둘 중 하나(|)에 .이 들어가야하므로 아래와 같다.

javascript
s.replace(/^\.|\.$/g, '');

73. 바탕화면 정리

바탕화면 정리는 .와 #로 구성된 문자열들로 구성된 배열을 받으면(보드 형태) 좌표상 어디서부터 어디까지 드래그해야 모두를 최소 범위로 포함할 수 있는지 묻는 문제다.

나는 생각해봤을 때 드래그 시작점의 x좌표는 모든 데이터 중 가장 왼쪽, y좌표는 모든 데이터 중 가장 위쪽, 드래그 끝점의 x좌표는 모든 데이터 중 가장 오른쪽, y좌표는 모든 데이터 중 가장 아랫쪽에 있을것이라 생각해 아래와 같이 코드를 작성했다.

처음엔 if(!lux) 식으로 작성했다가, 테스트 케이스에서 자꾸 떨어져 로깅을 해보니 0이 falsy value여서 그렇다는 사실을 인지했다. isNaN으로 해결.

javascript
function solution(wallpaper) {
    let lux, luy, rdx, rdy;
    for(let i = 0; i < wallpaper.length; i++){
        for(let j = 0; j < wallpaper[0].length; j++){
            if(wallpaper[i][j] === "#"){
                // lux: 가장 위쪽 좌표
                if(isNaN(lux)) lux = i;
                // luy: 가장 왼쪽 좌표
                if(isNaN(luy) || luy > j) luy = j;
                // rdx: 가장 아래 좌표
                if(!rdx || rdx < i + 1) rdx = i + 1;
                // rdy: 가장 오른쪽 좌표
                if(!rdy || rdy < j + 1) rdy = j + 1;
            }
        }
    }
    return [lux, luy, rdx, rdy];
}

73-1. 다 모아서 최솟값, 최댓값 반환

같은 원리로 더 멋지게 푼 답이 있어서 가져왔다. 각 위치(왼쪽, 오른쪽, 위, 아래)의 좌표에 해당하는 모든 데이터를 넣은 후 최솟값, 최댓값을 뽑아 반환하는 것이다. 가독성이 아주 좋다고 생각한다.

javascript
function solution(wallpaper) {
    let left = [];
    let top = [];
    let right = []
    let bottom = [];
    wallpaper.forEach((v,i) => {
        [...v].forEach((val,ind) => {
            if(val === "#") {
                left.push(i)
                top.push(ind)
                right.push(i + 1)
                bottom.push(ind + 1)
            }
        })
    })
    return [Math.min(...left), Math.min(...top), Math.max(...right), Math.max(...bottom)]
}

77. 공원 산책

공원 산책은 갈 수 있는 길 O, 장애물 X 그리고 시작점 S로 이루어진 문자열들의 배열로 구성된 보드와 어디로 몇번 움직이는지를 담은 배열 routes가 주어지면 최종적으로 어디에 도달하는지 좌표를 반환하라는 문제다.

이 문제의 핵심은, 개인적인 생각으론 장애물을 만나거나 보드판을 벗어나면 아예 그 이동을 무효화하고 다음 명령으로 넘어가는 것을 어떻게 처리하는지라고 생각한다.

도착지뿐 아니라 가는 중간에 장애물이 가로막아도 못 가는 것이니만큼 어쩔 수 없이 for문을 사용해 하나하나 이동해가며 장애물이 나오는지, 또는 유효하지 않은 범위로 가는지 체크하는 코드를 작성했다.

javascript
function solution(park, routes) {
    let rowIdx, colIdx;
    const H = park.length;
    const W = park[0].length;
    // 시작 위치
    for(let i = 0; i < park.length; i++){
        if(park[i].includes("S")){
            rowIdx = i;
            colIdx = park[i].indexOf("S");
            break;
        }
    }
    
    // route 파싱
    for(const route of routes){
        const [dir, dis] = route.split(" ");        
        let newColIdx = colIdx, newRowIdx = rowIdx, d = 1;
        while(d <= +dis){
            if(dir === "E") newColIdx = colIdx + d
            if(dir === "S") newRowIdx = rowIdx + d;
            if(dir === "W") newColIdx = colIdx - d;
            if(dir === "N") newRowIdx = rowIdx - d;
            if(newRowIdx < 0 || newColIdx < 0 || newRowIdx >= H || newColIdx >= W){
                newColIdx = colIdx, newRowIdx = rowIdx, d = 1;
                break;
            }
            if(!park[newRowIdx][newColIdx] || park[newRowIdx][newColIdx] === "X"){
                newColIdx = colIdx, newRowIdx = rowIdx, d = 1;
                break;
            }
            d++;
        }
        colIdx = newColIdx;
        rowIdx = newRowIdx;
    }
    return [rowIdx, colIdx];
}

77-1. 리팩토링

우선 풀이 방향은 유지하고 일부 코드들을 좀 고쳐보자.

• 시작 위치를 찾을 때 나는 이렇게 했다:

javascript
for(let i = 0; i < park.length; i++){
    if(park[i].includes("S")){
        rowIdx = i;
        colIdx = park[i].indexOf("S");
        break;
    }
}

위 코드는 그냥 아래와 같이 "S"의 위치를 저장해두고, 해당 위치가 -1이 아니라면(존재한다면) rowIdx와 colIdx를 한번에 바꾸는 편이 더 보기 쉽다.

javascript
for(let i = 0; i < park.length; i++){
  const j = park[i].indexOf("S");
  if(j !== -1){ rowIdx = i; colIdx = j; break;}
}

77-2. 방향을 객체로

rowIdx, colIdx를 어떻게 이동해야하는지를 담은 배열들을 객체에 저장하고 해당 객체에서 받아서 이동할 수 있다.

javascript
function solution(park, routes) {
        const dirs = { E: [0, 1], W: [0, -1], S: [1, 0], N: [-1, 0] };
        let [x, y] = [0, 0];
        for (let i = 0; i < park.length; i++) {
          if (park[i].includes('S')) {
            [x, y] = [i, park[i].indexOf('S')];
            break;
          }
        }

        routes.forEach((route) => {
          const [r, n] = route.split(' ');
          let [nx, ny] = [x, y];
          let cnt = 0;
          while (cnt < n) {
            [nx, ny] = [nx + dirs[r][0], ny + dirs[r][1]];
            if (!park[nx] || !park[nx][ny] || park[nx][ny] === 'X') break;
            cnt++;
          }
          if (cnt == n) [x, y] = [nx, ny];
        });
        return [x, y];
      }