완전 탐색(Brute Force) - 최소직사각형 / 모의고사

최소직사각형

완전 탐색이나 최적화 로직을 통해 모든 명함을 수납할 수 있는 최소 크기의 지갑을 계산하는 문제

명함을 적절히 회전하여 모든 명함의 긴 변이 하나로 정렬되도록 하면 문제를 간단히 해결할 수 있다.

풀이 전략

1. 명함 회전 처리
   • 각 명함의 가로 길이(w)와 세로 길이(h)를 비교하여, 더 긴 변이 가로가 되도록 회전시킨다.
   • 이는 모든 명함을 한 방향으로 정렬하여 계산을 단순화하기 위함이다.
2. 최대값 계산
   • 회전된 상태에서 모든 명함의 가로 길이 중 최대값과 세로 길이 중 최대값을 구한다.
   • 이 두 값의 곱이 지갑의 최소 크기가 된다.

알고리즘 풀이

function solution(sizes) {
  let w = [];
  let h = [];

  // 명함 사이즈를 가로, 세로 순으로 정렬
  sizes
    .map((size) => size.sort((a, b) => b - a))
    .forEach((size) => {
      w.push(size[0]);
      h.push(size[1]);
    });

  // 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기
  return Math.max(...w) * Math.max(...h);
}

시간 복잡도

• sizes 배열을 한 번 순회하며 최대값을 계산하므로 O(n)
• 명함이 많아도 빠르게 처리 가능하다.

---

모의고사

수포자들의 반복적인 답안 패턴을 고려하여 정답 배열과 비교한 후, 가장 많은 문제를 맞힌 사람을 찾는 문제

풀이 전략

1. 수포자들의 답안 패턴 정의
   • 수포자 1: [1, 2, 3, 4, 5]
   • 수포자 2: [2, 1, 2, 3, 2, 4, 2, 5]
   • 수포자 3: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
2. 정답 비교
   • answers 배열의 길이에 따라 각 수포자의 패턴을 반복적으로 확장하여 정답과 비교한다.
   • 각 수포자가 맞힌 문제 수를 계산한다.
3. 최고 점수 계산
   • 세 수포자가 맞힌 문제 수 중 가장 높은 점수를 구한다.
   • 최고 점수를 받은 수포자를 오름차순으로 정렬하여 반환한다.

알고리즘 풀이

function solution(answers) {
  // 각 수포자의 답안 패턴
  const patterns = [
    [1, 2, 3, 4, 5],
    [2, 1, 2, 3, 2, 4, 2, 5],
    [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
  ];

  // 각 수포자가 맞힌 문제 수를 계산
  const scores = patterns.map((pattern) => {
    return answers.reduce((score, answer, index) => {
      return score + (answer === pattern[index % pattern.length] ? 1 : 0);
    }, 0);
  });

  // 최고 점수 계산
  const maxScore = Math.max(...scores);

  // 최고 점수를 받은 수포자(1번부터 시작하므로 index + 1)
  return scores
    .map((score, index) => (score === maxScore ? index + 1 : null))
    .filter((value) => value !== null);
}

시간 복잡도

• answers 배열의 길이가 최대 10,000이므로 각 수포자와 정답 비교를 수행하는 O(n) 연산이 효율적으로 작동.
• 최고 점수 계산과 결과 필터링은 O(1)에 가깝기 때문에 메인 복잡도는 O(n)이다.