[백준 10703번 유성/ JS]

✏️ 문제 링크

https://www.acmicpc.net/problem/10703

✏️ 문제 풀이

 

중력에 관련된 문제이다. 사실 어떻게 풀어야하나 고민이 됐는데, 일단 풀어보자는 마인드로 풀었다. 
뭔가 알고리즘을 사용할 수 는 없을 것 같았고 구현을 빡세게 해야한다는 생각을 했다. 

그래서 car의 위치 정보를 저장해두고 맨 아래 줄부터 한줄 씩 확인하면서 car가 들어갈 수 있는지 확인하는 로직을 구현했다. 

i는 row를 뜻하고 car에 저장된 j들은 column 위치를 뜻한다. 

 

만약 n = 5라고 하면 i = 4부터 시작하는거다. (index = 0 부터 시작하기 때문에)

1. i= 4일 때 car에 들은 input들의 정보를 확인한다. 첫번째 입력 값을 기준으로 하면 car에는 [[1,2,3,4], [4]] 이런식으로 저장돼 있을 것이다. 

2. car.reverse()를 한다. reverse를 하는 이유는 i가 아래서부터 올라오기 때문에 가장 먼저 만나는게 car의 마지막 index이다. 마지막 index부터 시작해서 --로 하나씩 내려가며 봐도 되지만 i=0부터 시작하는게 가독성에 좋고 헷갈릴 가능성이 없기 때문에 car.reverse()를 해줬다. 

3. 먼저 [4]부터 확인한다. input[temp][4]에 car가 채워질 수 있는지 확인하는거다. 만약 채워질 수 있다면 다음 car 위치 정보를 확인하러 간다. 

4. 만약 car에 있는 모든 정보를 확인했는데 지금 i의 위치부터 시작해서 모두 갈 수 있다면 fit=true다. 중간에 실패하면 fit=false로 다시 i부터 시작해야한다. 

5. 이제 만약 fit=true로 성공했다면 각 car의 위치에 맞게 정보를 채워주고 출력해준다.

 

난 우선 이렇게 한줄 씩 체크하면서 들어갈 수잇는지 없는지 확인하고 만약에 전체가 들어가면 출력하고 아니면 다시 그다음 i부터 확인하는 로직으로 구현했는데, 다른 C++, 혹은 python으로 푼 분들은 위에서부터 x를 발견하고 뭔가 아래로 내려가면서 counting을 해서 min 값을 가지고 어떻게 문제를 푸는 느낌이었다... ㅠㅠㅠ 나와는 좀 다른 접근법이긴했지만...! 어쨋든 풀었고 다른 방식으로 푸는 방법도 한번 봐야되겠다. 

✏️ 문제 코드

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

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [n, m] = input.shift().split(" ").map(Number);
  const car = [];
  
  // car 위치 저장
  for (let i = 0; i < n; i++) {
    if (input[i].includes("X")) {
      let indexes = [];

      for (let j = 0; j < m; j++) {
        if (input[i][j] === "X") {
          indexes.push(j);
        }
      }
      input[i] = ".".repeat(m);
      car.push(indexes);
    }
  }
  car.reverse();

  // 땅의 가장 아래부터 시작해서 car의 위치가 .인지 확인하고
  // 만약 아니라면 다음 줄 확인 
  let i = n - 1;
  while (i >= 0) {
    let temp = i;
    let fit = true;

    for (let j = 0; j < car.length; j++) {
      for (const idx of car[j]) {
        if (input[temp][idx] === ".") {
          continue;
        } else {
          fit = false;
          break;
        }
      }
      if (fit === false) {
        i--;
        break;
      }

      temp--;
    }

    if (fit === true) {
      i = temp;
      break;
    }
  }

  let start = i + car.length;
  const answer = input.map((i) => i.split(""));
  for (const c of car) {
    for (const idx of c) {
      answer[start][idx] = "X";
    }
    start--;
  }

  answer.map((a) => console.log(a.join("")));
});