๐Ÿ’ป TIL 2023.02.01

๊น€์˜์šฐ(Yeongwoo Kim)ยท2023๋…„ 2์›” 3์ผ
0

1. ๋ฌด์ธ๋„ ์—ฌํ–‰(level 2)

- ๋ฌธ์ œ

https://school.programmers.co.kr/learn/courses/30/lessons/154540

- ์ฝ”๋“œ ์ž‘์„ฑ ์ „ ์ƒ๊ฐ

  1. BFS๋ฅผ ์ด์šฉํ•ด map์˜ ํ•˜๋‚˜์˜ ์„ฌ์„ ์ฐพ๋Š”๋‹ค.
  2. ์ฐพ์€ ์„ฌ์˜ ์‹๋Ÿ‰์˜ ๊ฐœ์ˆ˜๋ฅผ ๋”ํ•œ ๋’ค canLive ๋ฐฐ์—ด์— ๋„ฃ๋Š”๋‹ค.
  3. canLive ๋ฐฐ์—ด์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.

- ๊ตฌํ˜„ ์ค‘ ์ถ”๊ฐ€ ๋œ ํ•ญ๋ชฉ

  1. ์ฒ˜์Œ ๋ฐ›์•„์˜ค๋Š” maps array๋ฅผ split์„ ํ†ตํ•ด ํ•˜๋‚˜์”ฉ ๋Š์–ด์„œ newMap์— ์ €์žฅํ•ด ์ค€๋‹ค.
  2. visited๊ฐ€ BFS ํ•จ์ˆ˜ ์•ˆ์— ์žˆ์œผ๋ฉด solution์˜ ์ด์ค‘ for๋ฌธ์— ์˜ํ•ด ๊ณ„์† ์ดˆ๊ธฐํ™”๊ฐ€ ๋˜๊ธฐ ๋•Œ๋ฌธ์— solution์—์„œ ์„ ์–ธํ•ด ์ค€ ๋’ค BFS์— ๋ณด๋‚ด์ค˜์•ผ ํ•œ๋‹ค.
  3. newMaps์— ์žˆ๋Š” ์š”์†Œ๋“ค์€ string type์ด๊ธฐ ๋•Œ๋ฌธ์— Number๋กœ ํ˜• ๋ณ€ํ™˜์„ ํ•ด์ค€ ๋’ค food ๋ณ€์ˆ˜์— ๋”ํ•œ๋‹ค.
  4. solution์˜ canLive ํ•จ์ˆ˜์— ์•„๋ฌด๊ฒƒ๋„ ๋“ค์–ด์žˆ์ง€ ์•Š๋‹ค๋ฉด [-1] ์„ ์ถœ๋ ฅํ•˜๊ณ  ๋“ค์–ด์žˆ๋‹ค๋ฉด sort๋ฅผ ์ด์šฉํ•ด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๋’ค ์ถœ๋ ฅํ•œ๋‹ค.

- ์ฝ”๋“œ

const solution = (maps) => {
  let canLive = [];
  const column = maps.length;
  const row = maps[0].length;
  const newMap = maps.map((element) => element.split(""));
  const visited = Array(column)
    .fill(false)
    .map(() => Array(row).fill(false));
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      if (newMap[j][i] === "X") continue;
      canLive.push(Bfs(i, j, column, row, newMap, visited));
    }
  }
  if (canLive.length !== 0) {
    const result = canLive.filter((element) => element >= 0);
    result.sort(function (a, b) {
      return a - b;
    });
    return result;
  }
  return [-1];
};

const Bfs = (x, y, column, row, maps, visited) => {
  const dx = [1, 0, -1, 0];
  const dy = [0, 1, 0, -1];
  let food = 0;
  const queue = [];
  if (visited[y][x] === true) {
    return -1;
  }
  food += Number(maps[y][x]);
  visited[y][x] = true;
  queue.push([x, y]);

  while (queue.length > 0) {
    let [cx, cy] = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nx = cx + dx[i];
      let ny = cy + dy[i];
      if (nx < 0 || ny < 0 || nx >= row || ny >= column) continue;
      else if (visited[ny][nx] === true) continue;
      else if (maps[ny][nx] === "X") continue;
      else {
        food += Number(maps[ny][nx]);
        queue.push([nx, ny]);
        visited[ny][nx] = true;
      }
    }
  }
  return food;
};

2. ์ธ์‚ฌ ๊ณ ๊ณผ(level 3)

- ๋ฌธ์ œ

https://school.programmers.co.kr/learn/courses/30/lessons/152995

- ์ฝ”๋“œ ์ž‘์„ฑ ์ „ ์ƒ๊ฐ

  1. ๊ทผ๋ฌดํƒœ๋„์ ์ˆ˜ ๋‚ด๋ฆผ์ฐจ์ˆœ์ •๋ ฌ, ๊ทผ๋ฌดํƒœ๋„ ๋™์ ์ผ ๊ฒฝ์šฐ ๋™๋ฃŒํ‰๊ฐ€์ ์ˆ˜ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌํ•œ๋‹ค.
  2. ๋‚ด ์•ž์˜ ๋™๋ฃŒํ‰๊ฐ€์ ์ˆ˜๊ฐ€ ๋‚˜๋ณด๋‹ค ๋†’์€ ์‚ฌ๋žŒ์ด ํ•œ ์‚ฌ๋žŒ์ด๋ผ๋„ ์žˆ์œผ๋ฉด ํƒˆ๋ฝ์‹œํ‚จ๋‹ค.
  3. ๊ทผ๋ฌดํƒœ๋„ ๋™์ ์ž์˜ ๊ฒฝ์šฐ ๋™๋ฃŒํ‰๊ฐ€์ ์ˆ˜ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ ๋˜์–ด์žˆ์œผ๋ฏ€๋กœ ๊ณ ๋ คํ•  ํ•„์š”X

- ๊ตฌํ˜„ ์ค‘ ์ถ”๊ฐ€ ๋œ ํ•ญ๋ชฉ

  1. maxScore๋ฅผ ์ƒ์„ฑํ•ด ๋™๋ฃŒํ‰๊ฐ€ ์ ์ˆ˜์™€ ๋น„๊ต ํ•ด์•ผํ•œ๋‹ค.

- ์ฝ”๋“œ

const solution = (scores) => {
   const wanho = scores[0];
    scores.sort((a,b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
    let answer = 1;
    let maxScore = 0;
    const wanhoSum = wanho[0] + wanho[1];
    for(let score of scores){
        if(score[1] < maxScore) {
            // ํƒˆ๋ฝ๋Œ€์ƒ
            if(score === wanho) return -1;
        } else {
            // ์ธ์„ผ๋Œ€์ƒ
            maxScore = Math.max(maxScore, score[1]);
            if(score[0] + score[1] > wanhoSum){
                answer++;
            }
        }
    }
    return answer;
}

3. ๋“ฑ๋Œ€(level 3)

- ๋ฌธ์ œ

https://school.programmers.co.kr/learn/courses/30/lessons/133500

- ์ฝ”๋“œ ์ž‘์„ฑ ์ „ ์ƒ๊ฐ

  1. ํŠน์ • ์œ„์น˜์—์„œ ์—ฐ๊ฒฐ๋œ ๊ฐ„์„ ์ด ํ•˜๋‚˜๋ฐ–์— ์—†๋‹ค๋ฉด, ํ•ด๋‹น ์œ„์น˜์™€ ์—ฐ๊ฒฐ๋œ ์„ฌ์˜ ๋“ฑ๋Œ€๋ฅผ ํ‚ค๋Š” ๊ฒƒ์ด ํšจ์œจ์ ์ผ ๊ฒƒ ๊ฐ™๋‹ค.
  2. ์ด์–ด์ง„ ๋…ธ๋“œ๋“ค์„ map ๋ณ€์ˆ˜์— ์ €์žฅ ex) 1๊ณผ ์—ฐ๊ฒฐ๋œ ๊ฒƒ ([2,3,4,5])
  3. DFS๋ฅผ ์ด์šฉํ•ด ๋…ธ๋“œ๋ฅผ ํŒŒ์•…ํ•œ๋‹ค.

- ๊ตฌํ˜„ ์ค‘ ์ถ”๊ฐ€ ๋œ ํ•ญ๋ชฉ

  1. visited ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ ๋‹ค
  2. DFS๋ฅผ ํ•˜๋ ค๋‹ค๊ฐ€ greedy๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์–ด๋–จ๊นŒ๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.
  3. map์„ filter๋ฅผ ํ†ตํ•ด ๊ฐ„์„ ์ด ํ•œ๊ฐœ๋งŒ ์žˆ๋Š” ๋…ธ๋“œ๋“ค์„ ๊ตฌํ•œ๋‹ค.
  4. ๊ฐ„์„ ์ด ํ•œ๊ฐœ๋งŒ ์žˆ๋Š” ๋…ธ๋“œ๋“ค ์ค‘์—์„œ map[target]์— ์š”์†Œ๊ฐ€ ํ•œ๊ฐœ๋งŒ ์žˆ์œผ๋ฉด ๋”ํ•˜๊ธฐ๊ฐ€ 2๋ฒˆ ๋˜๋ฏ€๋กœ ๊ฒฝ์šฐ๋ฅด ๋‚˜๋ˆ ์„œ ํ•œ๊ฐœ๋งŒ ์žˆ์œผ๋ฉด 0.5๋ฅผ ๋”ํ•ด์ฃผ๊ณ  ์•„๋‹ˆ๋ผ๋ฉด 1์„ ๋”ํ•œ๋‹ค.
  5. lightHouse์—์„œ ๊ฐ„์„ ์ด ํ•œ๊ฐœ์ธ ๋…ธ๋“œ๋“ค์„ ์‚ญ์ œํ•œ๋‹ค.
  6. lightHouse์— ๋…ธ๋“œ๊ฐ€ ์•ˆ๋‚จ์„ ๋•Œ๊นŒ์ง€ 3,4,5 ๋ฐ˜๋ณต

- ์ฝ”๋“œ

const solution = (n, lightHouse) => {
  const visited = new Array(n + 1).fill(false);
  let result = 0;
  while (lightHouse.length) {
    const map = new Array(n + 1).fill().map((_) => []);
    for (const el of lightHouse) {
      const [a, b] = el;
      map[a].push(b);
      map[b].push(a);
    }
    // ํƒ์š•๋ฒ•
    map
      .filter((element) => element.length === 1)
      .forEach((element) => {
        const [target] = element;
        if (!visited[target]) {
          visited[target] = true;
          if (map[target].length !== 1) {
            result += 1;
          } else {
            // ์–‘์ชฝ ๋ชจ๋‘ ์žˆ๋Š” ๊ฒฝ์šฐ์ด๋ฏ€๋กœ ๋”ํ•˜๊ธฐ๊ฐ€ ๋‘๋ฒˆ์ผ์–ด๋‚œ๋‹ค.
            result += 0.5;
          }
        }
      });
    // ๊ฐ„์„ ์ด 1๊ฐœ์ธ ์„ฌ ๋ชจ๋‘ ์ œ๊ฑฐ
    lightHouse = lightHouse.filter((el) => {
      const [a, b] = el;
      return !visited[a] && !visited[b];
    });
  }
  return result;
};
profile
์ฐจ๊ทผ์ฐจ๊ทผ ์„ฑ์žฅํ•˜๋Š” ๊ฐœ๋ฐœ์ž์ž…๋‹ˆ๋‹ค

0๊ฐœ์˜ ๋Œ“๊ธ€