[백준/연결리스트/JS] 거울냥이는 죽어서 거울을 남긴다

문제 설명

---

16226번: 거울냥이는 죽어서 거울을 남긴다

• 거울: 거울냥이의 하단, 냥이가 죽어도 거울은 남음, 거울 있으면 빔 통과하지 못함
• (1,1)부터 시작
• 빔은 상하좌우 발사
• 거울냥이가 사라지면 자기 차례와도 빔 쏘지 못함

 

• 입력값: 거울냥이 마릿수, 빔 쏘는 순서대로 거울냥이 위치
• 출력값: 살아남은 거울냥이 갯수

 

시간 복잡도

---

시간 초과도 났고, 정답을 확인해보니 방향성도 틀렸다. 

 

 

알고리즘 설계

---

처음 설계 방식 - 틀린 방식

1. 2차원 배열 생성
2. 거울 위치 구하기 => mirror로 표시
3. 거울냥이 위치 구하기 => cat으로 표시
4. cat 위치에서부터 상, 좌, 우로 mirror 만날때까지 반복 => false로 표시
5. 2차원 배열에서 cat인 값만 세기

 

정답 설계 방식

1. 객체 생성 => 키: 행, 값: [열, false(거울냥이) 또는 true(거울)]

{
  '1': [ [ 1, false ], [ 4, false ], [ 3, false ] ],
  '2': [ [ 1, true ], [ 4, true ], [ 3, true ] ]
}

출처: 백준

2. 거울 만나면 shouldKill에 false 할당(리셋)

3. shouldKill이 false면 true 할당, result++(거울 이후 첫 번째로 만난 거울냥이만 살리기)

 

 

다른 풀이

---

let [n, ...cats] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
// let [n, ...cats] = `7\n1 2\n2 1\n2 3\n2 5\n3 4\n4 1\n4 2`.split('\n'); // [ '1 2', '2 1', '2 3', '2 5', '3 4', '4 1', '4 2' ]
n = Number(n);
cats = cats.map((el) => el.split(' ')).map((el) => el.map(Number));

let aliveCatCount = 0;
const map = {};
// 키: 행, 값: [열, false(거울냥이) 또는 true(거울)]
for (let [y, x] of cats) {
  // 거울냥이
  if (map[y] === undefined) map[y] = [];
  // 거울
  if (map[y + 1] === undefined) map[y + 1] = [];

  map[y].push([x, false]);
  map[y + 1].push([x, true]);
}

let shouldKill = false;

for (let y in map) {
  shouldKill = false;
  map[y].sort((a, b) => a[0] - b[0]);

  for (let [x, isMirror] of map[y]) {
    // 리셋
    if (isMirror) {
      shouldKill = false;
      continue;
    }
    // 거울 이후 첫 번째로 만난 거울냥이++ or 거울냥이
    if (shouldKill === false) {
      shouldKill = true;
      aliveCatCount += 1;
    }
  }
}

console.log(aliveCatCount);

 

기억해야 하는 정보

---

• 연결리스트 문제라고는 하는데, 연결리스트로 접근하여 풀지는 않아서 아쉽다..
• 2차원 배열을 사용할 경우 비게 되는 값들이 많기 때문에, 객체를 사용한 것도 포인트같다. 
• continue를 사용하면 아래 코드를 전부 스킵하고, 다음 포문 차례로 넘어간다. 
• 상, 좌, 우 모두 고려해야 한다고 생각했었지만, 사실상 좌우로 쏘는 빔만 고려하면 되었다. 위로 쏘는 빔도 언젠가 거울을 만나니깐.. 안 만나도 거기에는 거울냥이가 없을 것이다. 

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖