Boongranii

최고의 열정을 뽐내는 쿼카 🐶

7 분 소요

마흔 다섯 번째 포스팅Permalink

안녕하세요! 마흔 다섯 번째 포스팅으로 찾아뵙게 되어 반갑습니다!♥

오늘의 포스팅 내용은 프로그래머스 - 거리두기 확인하기에 관한 내용입니다.
자세한 내용을 알아보러 갑시다❗️

[Boongranii] Here We Go 🔥

1️⃣ 문제Permalink

[프로그래머스] 거리두기 확인하기 (문제 링크)

💨 문제 설명Permalink

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

  1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
  2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
  3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,

image image image
위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다. 위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다. 위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.
image image image
응시자가 앉아있는 자리(P)를 의미합니다. 빈 테이블(O)을 의미합니다. 파티션(X)을 의미합니다.

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

💨 제한 사항Permalink

  • places의 행 길이(대기실 개수) = 5
    • places의 각 행은 하나의 대기실 구조를 나타냅니다.
  • places의 열 길이(대기실 세로 길이) = 5
  • places의 원소는 P,O,X로 이루어진 문자열입니다.
    • places 원소의 길이(대기실 가로 길이) = 5
    • P는 응시자가 앉아있는 자리를 의미합니다.
    • O는 빈 테이블을 의미합니다.
    • X는 파티션을 의미합니다.
  • 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
  • return 값 형식
    • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
    • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
    • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

💨 입출력 예Permalink

places result
[[“POOOP”, “OXXOX”, “OPXPX”, “OOXOX”, “POXXP”], [“POOPX”, “OXPXP”, “PXXXO”, “OXXXO”, “OOOPP”], [“PXOPX”, “OXOXP”, “OXPOX”, “OXXOP”, “PXPOX”], [“OOOXX”, “XOOOX”, “OOOXX”, “OXOOX”, “OOOOO”], [“PXPXP”, “XPXPX”, “PXPXP”, “XPXPX”, “PXPXP”]] [1, 0, 1, 1, 1]

💨 입출력 예 설명Permalink

입출력 예 #1

첫 번째 대기실

No. 0 1 2 3 4
0 P O O O P
1 O X X O X
2 O P X P X
3 O O X O X
4 P O X X P
  • 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No. 0 1 2 3 4
0 P O O P X
1 O X P X P
2 P X X X O
3 O X X X O
4 O O O P P
  • (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
  • (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
  • (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No. 0 1 2 3 4
0 P X O P X
1 O X O X P
2 O X P O X
3 O X X O P
4 P X P O X
  • 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No. 0 1 2 3 4
0 O O O X X
1 X O O O X
2 O O O X X
3 O X O O X
4 O O O O O
  • 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No. 0 1 2 3 4
0 P X P X P
1 X P X P X
2 P X P X P
3 X P X P X
4 P X P X P
  • 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

💨 제한시간 안내Permalink

  • 정확성 테스트 : 10초

※ 공지 - 2022년 4월 25일 테스트케이스가 추가되었습니다.

두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.

2️⃣ 문제 풀이Permalink

🔥 나의 문제 풀이Permalink

  1. P : 응시자가 앉아있는 자리 / O : 빈 테이블 / X : 파티션(가림막)
  2. 해당 요소가 P인 경우, 상하좌우에 P가 있는지 확인 → 있으면 0
  3. 해당 요소가 O인 경우, 상하좌우에 P가 2개 이상 있는지 확인 → 있으면 0
  4. 해당 요소가 X인 경우, 무시
  5. 모든 경우를 통과하면 1을 반환하고, 하나라도 통과하지 못하면 0을 반환
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

function adjacentPlace(arr) {
  const place = arr.map((a) => a.split(""));
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, -1, 1];

  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      if (place[i][j] === "P") {
        for (let k = 0; k < 4; k++) {
          const nx = i + dx[k];
          const ny = j + dy[k];
          if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5) {
            if (place[nx][ny] === "P") {
              return 0;
            }
          }
        }
      }
      if (place[i][j] === "O") {
        let count = 0;
        for (let k = 0; k < 4; k++) {
          const nx = i + dx[k];
          const ny = j + dy[k];
          if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5 && place[nx][ny] === "P") {
            count++;
            if (count >= 2) {
              return 0;
            }
          }
        }
      }
    }
  }
  return 1;
}

function solution(places) {
  return places.map((a) => adjacentPlace(a));
}

console.log(
  solution([
    ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"],
    ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"],
    ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"],
    ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"],
    ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"],
  ])
);

솔직하게 말해서 문제를 너무 거창하게 써놨다. 물론 헷갈리게 하려고 이렇게 거창하게 했겠지. 주어진 입력 배열이 2차원 배열로 더욱 더 복잡해 보인다. 하지만, 그냥 하나의 배열만 맞으면 뭐 다른 인덱스의 배열도 성립할 것이다.

단순하게 X는 파티션이므로 고려하지 않아도 되는 사항 같았다. 자리가 P이면 그 주위 8자리 중 사람이 한 명 더 있으면 안되는 것이다. 또한, 자리가 O이면 그 주위 자리 중 사람이 2명이 되면 안되는 것이다.

맨해튼 거리도 복잡하게 생각하라고 낸 것 같다. 그냥 다 복잡하라고 낸 것 같다. 왜 이렇게 부정적이지ㅜㅜ

그래서 저 각 조건이 성립하지 않으면 0을 리턴하고, 그게 아니라면 1을 리턴하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

function adjacentPlace(arr) {
  const place = arr.map((a) => a.split(""));
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, -1, 1];

  // 해당 좌표가 유효한지 확인하는 메서드
  function isValidCell(x, y) {
    return x >= 0 && y >= 0 && x < 5 && y < 5;
  }

  // 해당 좌표에 상하좌우에 사람이 있는지 확인하는 메서드
  function countAdjacentPeople(x, y) {
    let count = 0;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (isValidCell(nx, ny) && place[nx][ny] === "P") {
        count++;
      }
    }
    return 0;
  }

  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      // 해당 좌표가 P인 경우, 상하좌우에 P가 있는지 확인
      if (place[i][j] === "P") {
        for (let k = 0; k < 4; k++) {
          const nx = i + dx[k];
          const ny = j + dy[k];
          if (isValidCell(nx, ny)) {
            if (place[nx][ny] === "P") {
              return 0;
            }
          }
        }
      }
      // 해당 좌표가 O인 경우, 상하좌우에 P가 2개 이상 있는지 확인
      if (place[i][j] === "O") {
        if (countAdjacentPeople(i, j) >= 2) {
          return 0;
        }
      }
    }
  }
  return 1;
}

function solution(places) {
  return places.map((a) => adjacentPlace(a));
}

원래 코드를 리팩토링을 해봤다. 중복되는 코드가 있어서 메서드만 나누어줬다. 가독성으로 보았을 때는 확실히 아래 코드가 더 좋아보인다.

무엇이 좋은 지는 모르겠다. 하지만 메서드를 나누는게 좋지 않을까 라는 생각을 해본다.

3️⃣ 느낀점Permalink

저번 포스팅에서 비슷한 문제를 풀어봤던 것 같다고 했는데 이 문제와 더 유사한 것 같다. [Lv.0-안전지대]

이 문제가 BFS 알고리즘을 사용해서 푸는 것이라고 하던데 BFS랑 비슷한 맥락의 느낌이긴 하다. 그 위치의 주변 8자리를 토대로 검색한 것이니 BFS는 아니긴 하다.

물론 문제를 보고 막막하다고 생각을 했다. 그래서 위에서 계속 거창한 문제라고 생각했던 것이다. 생각도 오래 걸리긴 했지만 문제에 비하면 크게 복잡하지 않았던 문제라고 생각한다.

죠르디처럼 나도 카카오로 면접 보러 가고 싶다 킄 ㅋ💩 그럼 안녕티비다🌀

댓글남기기

참고