Algorithm - Programmers Problem (week 6)

이소라·2023년 3월 6일

Algorithm

목록 보기

40/77

Problem : 바탕화면 정리

컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"의 값을 가집니다. 드래그를 하면 파일들을 선택할 수 있고, 선택된 파일들을 삭제할 수 있습니다. 머쓱이는 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 하며 드래그로 파일들을 선택하는 방법은 다음과 같습니다.
- 드래그는 바탕화면의 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클릭한 상태로 격자점 E(rdx, rdy)로 이동한 뒤 마우스 왼쪽 버튼을 떼는 행동입니다. 이때, "점 S에서 점 E로 드래그한다"고 표현하고 점 S와 점 E를 각각 드래그의 시작점, 끝점이라고 표현합니다.
- 점 S(lux, luy)에서 점 E(rdx, rdy)로 드래그를 할 때, "드래그 한 거리"는 |rdx - lux| + |rdy - luy|로 정의합니다.
- 점 S에서 점 E로 드래그를 하면 바탕화면에서 두 격자점을 각각 왼쪽 위, 오른쪽 아래로 하는 직사각형 내부에 있는 모든 파일이 선택됩니다.
예를 들어 wallpaper = [".#...", "..#..", "...#."]인 바탕화면을 그림으로 나타내면 다음과 같습니다.

이러한 바탕화면에서 다음 그림과 같이 S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택되므로 드래그 한 거리 (3 - 0) + (4 - 1) = 6을 최솟값으로 모든 파일을 선택 가능합니다.

(0, 0)에서 (3, 5)로 드래그해도 모든 파일을 선택할 수 있지만 이때 드래그 한 거리는 (3 - 0) + (5 - 0) = 8이고 이전의 방법보다 거리가 늘어납니다.
머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.

제한사항

1 ≤ wallpaper의 길이 ≤ 50
1 ≤ wallpaper[i]의 길이 ≤ 50
- wallpaper의 모든 원소의 길이는 동일합니다.
wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
바탕화면에는 적어도 하나의 파일이 있습니다.
드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

Solution

function solution(wallpaper) {
    const height = wallpaper.length;
    const width = wallpaper[0].length;
    let minHeight = wallpaper.length;
    let minWidth = wallpaper[0].length;
    let maxHeight = 0;
    let maxWidth = 0;
    
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (wallpaper[i][j] === '#') {
                if (i <= minHeight) {
                    minHeight = i;
                }
                if (i >= maxHeight) {
                    maxHeight = i;
                }
                if (j <= minWidth) {
                    minWidth = j;
                }
                if (j >= maxWidth) {
                    maxWidth = j;
                }
            }
        }
    }
    return [minHeight, minWidth, maxHeight + 1, maxWidth + 1];
}

Problem : 덧칠하기

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.
이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

제한사항

1 ≤ m ≤ n ≤ 100,000
1 ≤ section의 길이 ≤ n
- 1 ≤ section의 원소 ≤ n
- section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
- section에서 같은 원소가 두 번 이상 나타나지 않습니다.
- section의 원소는 오름차순으로 정렬되어 있습니다.

Solution

function solution(n, m, section) {
    let answer = 0;
    let lastPaintedWall = 0;
    for (let i = 0; i < section.length; i++) {
        if (section[i] < lastPaintedWall) {
            continue;
        }
        if (section[i] >= lastPaintedWall) {
            lastPaintedWall = section[i] + m;
            answer += 1;
        }
    }
    return answer;
}

Problem : 카드 뭉치

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.
- 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
- 한 번 사용한 카드는 다시 사용할 수 없습니다.
- 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
- 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.
문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

제한사항

1 ≤ cards1의 길이, cards2의 길이 ≤ 10
- 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
- cards1과 cards2에는 서로 다른 단어만 존재합니다.
2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
- 1 ≤ goal[i]의 길이 ≤ 10
- goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

Solution

function solution(cards1, cards2, goal) {
    const cards1Count = cards1.length;
    const cards2Count = cards1.length;
    let cards1Index = 0;
    let cards2Index = 0;
    
    for (let i = 0; i < goal.length; i++) {
        const word = goal[i];
        if (cards1[cards1Index] === word) {
            cards1Index += 1;
        } else if (cards2[cards2Index] === word) {
            cards2Index += 1;
        } else {
            return 'No';
        }
    }
    return 'Yes';
}

Problem : 혼자서 하는 틱택토

틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.
할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.
- 혼자서 선공과 후공을 둘 다 맡는다.
- 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.
틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.
- "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
- 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.
게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.
머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

제한 사항

board의 길이 = board[i]의 길이 = 3
- board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
- "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

Solution

전반적인 접근법 (참고)
1. 순서를 잘못 놓은 경우
  - O의 개수가 X의 개수보다 2개 이상 많은 경우
  - X의 개수가 O의 개수보다 많은 경우
2. O Bingo 후 X를 놓은 경우
  - O의 Bingo가 있으면서, X의 개수가 O의 개수와 같거나 큰 경우
3. X Bingo 후 O를 놓은 경우
  - X의 Bingo가 있으면서, O의 개수가 X의 개수를 초과하는 경우
4. O와 X 둘 다 Bingo한 경우
  - O와 X 모두 Bingo가 있는 경우
5. 같은 방향의 빙고가 겹치는 경우
  - 가로/세로/대각선 방항의 Bingo 수가 여러 개인 경우

function solution(board) {
    const boardLength = 3;
    let countO = 0;
    let countX = 0;
    let bingoO = [0, 0, 0];
    let bingoX = [0, 0, 0];

  for (let row = 0; row < boardLength; row++) {
      // 가로 빙고
      if (board[row][0] === board[row][1] && board[row][1] === board[row][2] && board[row][0] !== '.') {
          board[row][0] === 'O' ? bingoO[0] += 1 : bingoX[0] += 1;
      }
      
      // 세로 빙고
      if (board[0][row] === board[1][row] && board[1][row] === board[2][row] && board[0][row] !== '.') {
          board[0][row] === 'O' ? bingoO[1] += 1 : bingoX[1] += 1;
      }
      
      // O, X 개수
      for (let col = 0; col < boardLength; col++) {
          const value = board[row][col];
          if (value === 'O') {
              countO++;
          }
          if (value === 'X') {
              countX++;
          }
      }
  }
    // 대각 빙고
    if (board[0][0] === board[1][1] && board[1][1] === board[2][2] && board[1][1] !== '.') {
        board[1][1] === 'O' ? bingoO[2] += 1 : bingoX[2] += 1;
    }
    if (board[0][2] === board[1][1] && board[1][1] === board[2][0] && board[1][1] !== '.') {
        board[1][1] === 'O' ? bingoO[2] += 1 : bingoX[2] += 1;
    }
    
    
    const totalBingoO = bingoO.reduce((acc, num) => acc += num, 0);
    const totalBingoX = bingoX.reduce((acc, num) => acc += num, 0);
    
  	// 선공이 후공보다 적거나 후공보다 2개 이상 앞선 경우
    if (countO < countX || countO >= countX + 2) {
        return 0;
    }
    // O, X 둘 다 빙고에 성공한 경우
    if (totalBingoO > 0 && totalBingoX > 0) {
        return 0;
    }
    // 빙고에 성공한 줄이 2개보다 많은 경우
    if (bingoO.filter((num) => num > 1).length > 0 || bingoX.filter((num) => num > 1).length > 0) {
        return 0;
    }
    // O의 승리 상황에서 X의 개수가 O의 개수와 같거나 큰 경우
    if (totalBingoO > 0 && countX >= countO) {
        return 0;
    }
    // X의 승리 상황에서 O의 개수가 X의 개수보다 많은 경우
    if (totalBingoX && countO > countX) {
        return 0;
    }
    // 그 외의 경우
    return 1;
}