[ 2024.10.21 TIL ] 알고리즘 중급

박지영·어제
algorithmjs
0

Today I Learned

목록 보기
66/67

📘 알고리즘 중급 문제

문제 2

문제

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

  1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
  2. 같은 문자는 같은 개수 만큼 있다.

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

예제 입력

4
DOG
GOD
GOOD
DOLL

​
예제 출력

2

답

  1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.

  2. 같은 문자는 같은 개수 만큼 있다.

같은 문자를 1개 더하거나 빼거나 하나를 다른 문자로 바꿨을때 구성이 같으면 비슷한 단어 

function solution(words) {
  const firstWord = words[0];
  const firstFreq = getCharFrequency(firstWord);

  let cnt = 0;

  for (let i = 1; i < words.length; i++) {
    const currWord = words[i];
    const currFreq = getCharFrequency(currWord);

    if (areSimilar(firstFreq, currFreq)) {
      cnt++;
    }
  }
  return cnt;
}

function getCharFrequency(word) {
  const freq = new Array(26).fill(0);
  for (let char of word) {
    freq[char.charCodeAt(0) - 65]++;
  }
  return freq;
}

function areSimilar(freq1, freq2) {
  let addCnt = 0;
  let removeCnt = 0;

  for (let i = 0; i < 26; i++) {
    const diff = freq1[i] - freq2[i];

    if (diff > 0) {
      removeCnt += diff;
    } else if (diff < 0) {
      addCnt += -diff;
    }
  }

  return addCnt <= 1 && removeCnt <= 1;
}

const input = ["4", "DOG", "GOD", "GOOD", "DOGG"];

const numWords = parseInt(input[0], 10);
const words = input.slice(1);

console.log(solution(words));

문제 3

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

예제 입력

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

​
예제 출력

((110(0101))(0010)1(0001))

답

function solution(N, arr) {
  let answer = "";

  function compress(x, y, size) {
    const value = arr[y][x];

    let isSame = true;

    for (let i = y; i < y + size; i++) {
      for (let j = x; j < x + size; j++) {
        if (arr[i][j] !== value) {
          isSame = false;
          break;
        }
      }
      if (!isSame) break;
    }

    if (isSame) {
      answer += value;
    } else {
      answer += "(";
      const halfSize = size / 2;
      compress(x, y, halfSize); // 왼쪽 위
      compress(x + halfSize, y, halfSize); // 오른쪽 위
      compress(x, y + halfSize, halfSize); // 왼쪽 아래
      compress(x + halfSize, y + halfSize, halfSize); // 오른쪽 아래
      answer += ")";
    }
  }
  compress(0, 0, N);

  return answer;
}

function input() {
  // 고정된 입력 값
  const N = 8;
  const arr = [
    [1, 1, 1, 1, 0, 0, 0, 0],
    [1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 1, 1, 1, 0, 0],
    [1, 1, 1, 1, 0, 0, 0, 0],
    [1, 1, 1, 1, 0, 0, 0, 0],
    [1, 1, 1, 1, 0, 0, 1, 1],
    [1, 1, 1, 1, 0, 0, 1, 1],
  ];

  return { N, arr };
}

// N과 2차원 배열 arr을 입력받음
const { N, arr } = input();

console.log(solution(N, arr));

문제 4

문제

선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다. 호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다.

선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.

어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.

패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.

파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.

패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.

다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력
총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다.
참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다.
예제 입력 1

3
a*d
abcd
anestonestod
facebook

​
예제 출력 1

DA
DA
NE

예제 입력 2

6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun

예제 출력 2

DA
DA
NE
NE
NE
DA

답

function solution(numWords, words) {
  let answer = Array(numWords).fill("da");
  const fitstWord = words[0].split("*");
  
  for (let i = 1; i < words.length; i++) {
    const currWord = words[i];

    if (fitstWord[0] !== currWord[0]) {
      answer[i - 1] = "ne";
    } else if (
      fitstWord[fitstWord.length - 1] !== currWord[currWord.length - 1]
    ) {
      answer[i - 1] = "ne";
    }
  }

  return answer;
}

const input = [
  "6",
  "h*n",
  "huhovdjestvarnomozedocisvastan",
  "honijezakon",
  "atila",
  "je",
  "bio",
  "hun",
];

const numWords = parseInt(input[0], 10);
const words = input.slice(1);

console.log(solution(numWords, words));
profile
박지영
신입 개발자
이전 포스트

[ 2024.10.18 TIL ] Typescript 및 TCP

다음 포스트

[ 2024.10.22 TIL ] TCP multi-player-game

0개의 댓글