구현 문제 풀이

• 알고리즘 스터디 4주차 주제는 구현이었다.
• 기억에 남는 문제 위주로 풀이 내용을 정리한다.

---

 

백준 2174번

  다수의 로봇들 (1≤N≤100) 이 존재하는 공간에서 각 로봇들에 명령을 내리고, 해당 명령을 문제 없이 수행할 수 있는지 파악하는 문제. 명령은 총 3가지인데, ‘로봇이 향하는 방향을 기준으로’ 왼쪽/오른쪽으로 90도 회전/앞으로 한 칸 움직이기이다. 따라서 각 로봇들의 위치 뿐 아니라, 로봇이 현재 향하고 있는 방향 또한 고려해야하는 문제였다.

  로봇이 다수 존재하기 때문에, 입력받은 순서대로 로봇에 번호를 붙여 객체에 위치 및 방향을 저장해두고, 각 로봇의 정보에 접근하기 용이하게끔 하였다. 이후로는 순서대로 들어오는 명령을 처리하기만 하면 된다. 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const nextRow = [-1, 0, 1, 0];
const nextCol = [0, 1, 0, -1];

const direction = {
  N: 0,
  E: 1,
  S: 2,
  W: 3,
};

rl.on("line", (line) => {
  input.push(line.split(" "));
}).on("close", function () {
  const [col, row] = input.shift().map((el) => parseInt(el));
  const [robots] = input.shift().map((el) => parseInt(el));
  const robot = {};
  let error;

  const board = new Array(row);
  for (let i = 0; i < row; i++) {
    board[i] = Array(col).fill(0);
  }

  for (let i = 1; i <= robots; i++) {
    const [x, y, dir] = input[i - 1];
    robot[i] = {
      x: row - parseInt(y),
      y: parseInt(x) - 1,
      dir: direction[dir],
    };
    board[row - parseInt(y)][parseInt(x) - 1] = i;
  }

  const rotateRight = (target, repeat) => {
    const newDirection = (robot[target].dir + repeat) % 4;
    robot[target].dir = newDirection;
  };

  const rotateLeft = (target, repeat) => {
    const newDirection = robot[target].dir - (repeat % 4);
    robot[target].dir = newDirection >= 0 ? newDirection : newDirection + 4;
  };

  const move = (target, repeat) => {
    const curDir = robot[target].dir;
    for (let j = 0; j < repeat; j++) {
      const curX = robot[target].x;
      const curY = robot[target].y;

      const nextX = curX + nextRow[curDir];
      const nextY = curY + nextCol[curDir];

      if (nextX < 0 || nextY < 0 || nextX >= row || nextY >= col) {
        error = `Robot ${target} crashes into the wall`;
        break;
      }

      if (board[nextX][nextY] !== 0) {
        error = `Robot ${target} crashes into robot ${board[nextX][nextY]}`;
        break;
      }
      board[curX][curY] = 0;
      board[nextX][nextY] = target;
      robot[target].x = nextX;
      robot[target].y = nextY;
    }
  };

  const commandsList = input.slice(robots);

  for (let i = 0; i < commandsList.length; i++) {
    const [target, command, repeat] = commandsList[i];
    if (command === "L") {
      rotateLeft(target, parseInt(repeat));
    }
    if (command === "R") {
      rotateRight(target, parseInt(repeat));
    }
    if (command === "F") {
      move(parseInt(target), parseInt(repeat));
    }

    if (error != null) {
      console.log(error);
      process.exit();
    }
  }

  console.log("OK");

  process.exit();
});

 

 

백준 1756번

  문제를 보고 바로 떠오르는... 이중 for문을 사용하여 오븐 및 반죽의 크기 배열을 순회하는 방법은 당연히 시간 초과가 난다. 따라서 이 방법을 사용하지 않고 로직을 짜야하는데... 이 부분이 조금 어려웠다.

• 주어진 오븐의 깊이 배열을 그대로 쓰는게 아니라, 약간의 변형을 가하면 순회 및 체크가 쉽다.
  → 예를 들어, 위에서부터 차례로 [2, 5, 4, 8]의 크기를 갖는 오븐이 있으면, 2번째 오븐 구멍 크기가 아무리 5라 하더라도 바로 위의 크기가 2밖에 안 되기 때문에, 결과적으론 2 이하 크기의 반죽 밖에 안 들어온다.
  → 이 점을 활용하여, 해당 오븐에 ‘실질적으로 들어올 수 있는’ 가장 큰 크기의 반죽 값을 새로 할당해준다.
• 오븐의 크기 값을 재할당하고 나면, 오븐의 맨 아래부터 순서대로 반죽을 넣어가며 최종적으로 반죽이 어디에 위치하는지를 확인하면 된다.

예제의 오븐 배열을 재할당한 모습

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  const [d, n] = input.shift();

  const ovenDepth = input.shift();
  const dough = input.shift();

  let max = ovenDepth[0];
  for (let i = 1; i < d; i++) {
  	// 각 오븐에 들어갈 수 있는, 실질적으로 가장 큰 크기의 지름을 기록한다
    if (ovenDepth[i] < max) max = ovenDepth[i];
    if (ovenDepth[i] > max) {
      ovenDepth[i] = max;
    }
  }

  let idx = 0;
  let num = 0;
  let answer;
  for (let i = d - 1; i >= 0; i--) {
    if (ovenDepth[i] >= dough[idx]) {
      num++;
      idx++;
      answer = i + 1;
    }
  }

  if (num !== n) {
    console.log(0);
  } else {
    console.log(answer);
  }

  process.exit();
});

 

 

백준 1283번

  간단한 문자열 + 구현 문제. 단축키 정보를 Object에 저장하고, 주어진 문자열 리스트를 순회하며 문제에서 제시한 단축키 지정법을 그대로 따라주기만 하면 되었다.

  유의할 것은 조건의 '대소문자를 구분치 않는다' 정도. 대소문자를 구분하지 않기 때문에 'A'로 단축키를 설정했다면 'a'로 단축키를 설정하는 것은 불가능하다. 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", function () {
  const n = parseInt(input.shift());
  let hotKeyObj = {};

  for (let i = 0; i < n; i++) {
    let hasSetKey = false;
    const words = input[i].split(" ");

    for (let j = 0; j < words.length; j++) {
      const first = words[j][0];
      if (hotKeyObj[first.toUpperCase()] == null) {
        hotKeyObj[first.toUpperCase()] = words[j];
        words[j] = words[j].replace(first, `[${first}]`);
        input[i] = words.join(" ");
        hasSetKey = true;
        break;
      }
    }

    if (!hasSetKey) {
      for (let j = 0; j < input[i].length; j++) {
        const char = input[i][j];
        if (char !== " " && hotKeyObj[char.toUpperCase()] == null) {
          hotKeyObj[char.toUpperCase()] = input[i];
          input[i] = input[i].replace(char, `[${char}]`);
          break;
        }
      }
    }
  }

  console.log(input.join("\n").trim());

  process.exit();
});

 

 

백준 14499번

  주사위를 한 칸씩 굴릴 때마다, 이동 후 주사위 맨 위에 오는 수가 무엇인지 출력하는 문제. 다른 조건은 다 괜찮았는데, 가장 오래 고민한 것이 주사위를 이동시키는 것이었다. 주사위를 여러 방향으로 굴리다보면 주사위가 회전하게 되다 보니, 주사위 상단에 쓰인 수가 같더라도 옆면의 상황이 달라질 수 있기 때문이었다. 이는 결국, 주사위의 각 옆면 4개와 상단/하단의 모든 면의 숫자값을 별도의 배열에 저장하고, 주사위를 굴릴 때는 이 배열 내의 요소들의 순서를 바꿔주는 것으로써 구현했다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const direction = {
  1: [0, 1],
  2: [0, -1],
  3: [-1, 0],
  4: [1, 0],
};

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  const [n, m, firstX, firstY, k] = input.shift();
  const board = input.slice(0, n);

  const answer = [];
  const commandArr = input[input.length - 1];

  // 문제 속 전개도 기준, 각 면에 적힌 숫자 값
  const dice = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
  };
  
  // 전개도 기준, 각 면이 어디에 위치하였는지 기록
  let currentDice = [1, 6, 2, 3, 5, 4]; // top, bottom, n, e, s, w

  let currentX = firstX,
    currentY = firstY;

  for (let i = 0; i < k; i++) {
    const command = commandArr[i];
    const nextX = currentX + direction[command][0];
    const nextY = currentY + direction[command][1];

    if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) {
      // 유효하지 않은 명령
      continue;
    }

    currentX = nextX;
    currentY = nextY;

    const [top, bottom, north, east, south, west] = currentDice;
    switch (command) {
      case 1:
        currentDice = [west, east, north, top, south, bottom];
        break;
      case 2:
        currentDice = [east, west, north, bottom, south, top];
        break;
      case 3:
        currentDice = [south, north, top, east, bottom, west];
        break;
      case 4:
        currentDice = [north, south, bottom, east, top, west];
        break;
    }
    const currentFloor = currentDice[1];

    if (board[currentX][currentY] === 0) {
      board[currentX][currentY] = dice[currentFloor];
    } else {
      dice[currentFloor] = board[currentX][currentY];
      board[currentX][currentY] = 0;
    }

    answer.push(dice[7 - currentFloor]);
  }
  console.log(answer.join("\n").trim());

  process.exit();
});

 

---

• 구현 문제는 하다보면 재밌는데, 이런 저런 경우의 수를 생각하는 케이스가 많아서 코드가 길어지고 복잡해지는 것 같다...
• 스터디 3주차 주제가 다이내믹 프로그래밍이었는데, 이 문제 풀이도 조만간 정리하여 올리려 한다.
• +) 1756번을 풀고난 감상