정렬 알고리즘 문제 (Feat : 백준 실버)

1. 소수 찾기

https://www.acmicpc.net/problem/1978

문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

내 풀이

// 소수
function sosu(A, B) {
  function sosuCheck(num) {
    if (num < 2) return false;
    // Math.sqrt 함수를 사용하여 제곱근까지만 반복
    for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
      if (num % i === 0) return false;
    }
    return true;
  }

  let array = [];
  let answer = 0;
  for (let i = A; i <= B; i++) {
    if (sosuCheck(i)) {
      answer += i;
      array.push(i);
    }
  }
  if (array.length === 0) {
    return -1;
  }

  return `${answer}\n${array[0]}`;
}

console.log(sosu(60, 100));

gpt 풀이

• parseInt는 실수를 정수로 변환하지만, 이 경우 Math.floor가 좀 더 의도를 명확하게 나타냅니다. 예를 들어, 소수점 아래를 버리는 연산임을 보다 직관적으로 표현할 수 있습니다.
• array.push(i)를 생략됨

function sosu(A, B) {
  function sosuCheck(num) {
    if (num === 1) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;
    for (let i = 3; i <= Math.floor(Math.sqrt(num)); i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }

  let sum = 0;
  let min = null;
  for (let i = A; i <= B; i++) {
    if (sosuCheck(i)) {
      sum += i;
      if (min === null) min = i;
    }
  }
  if (min === null) {
    return -1;
  }
  return `${sum}\n${min}`;
}

2. 시리얼 번호

https://www.acmicpc.net/problem/1292

문제
다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

출력
첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

내 풀이

function serial(T, cases) {
  // 요소의 길이 부터 비교
  // 길이 같다면, 요소의 숫자만 더한값으로 비교
  // 이제는 사전순으로 비교

  cases.sort((a, b) => {
    // 요소의 길이 부터 비교
    if (a.length !== b.length) {
      //길이가 긴 게 앞으로 정렬되게
      return a.length - b.length;
    }

    //길이가 같다면
    if (a.length === b.length) {
      function numberSum(str) {
        let total = 0;
        str.split("").map((item) => {
          if (!isNaN(item)) {
            total += item;
          }
        });
        return total;
      }

      // 작은 합
      return numberSum(a) - numberSum(b);
    }

    // 이제 나머지
    return a.localeCompare(b);
  });
  console.log("cases", cases);
}
serial(5, ["ABCD", "145C", "A", "A910", "Z321"]);

gpt 풀이

• map 대신 forEach 사용
• 불필요한 길이 비교 - if (a.length === b.length)

function serial(T, cases) {
  cases.sort((a, b) => {
    // 길이 우선 비교
    if (a.length !== b.length) {
      return a.length - b.length;
    }

    // 길이가 같다면 숫자 합계로 비교
    function numberSum(str) {
      let total = 0;
      str.split("").forEach((item) => {
        if (!isNaN(item)) {
          total += Number(item);  // 문자열을 숫자로 변환하여 더하기
        }
      });
      return total;
    }

    let sumA = numberSum(a);
    let sumB = numberSum(b);

    if (sumA !== sumB) {
      return sumA - sumB;
    }

    // 숫자 합도 같다면 사전순으로 비교
    return a.localeCompare(b);
  });

  console.log("cases", cases);
}

serial(5, ["ABCD", "145C", "A", "A910", "Z321"]);

3. 베스트 셀러

https://www.acmicpc.net/problem/1302

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력
첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

내 코드

// 베스트 셀러
function bestseller(cases) {
  //
  cases.sort((a, b) => {
    return a.localeCompare(b);
  });

  let arr = [];
  let count = 0;
  let str = cases[0];

  cases.map((item, index) => {
    if (index === cases.length - 1) {
      arr.push({ key: str, count: count + 1 });
    }
    if (str === item) {
      count++;
    } else {
      arr.push({ key: str, count: count });
      str = item;
      count = 1;
    }
  });
  const result = arr.sort((a, b) => {
    return b.count - a.count;
  });
  return result[0].key;
}
console.log(
  bestseller([
    "table",
    "chair",
    "table",
    "table",
    "lamp",
    "door",
    "lamp",
    "table",
    "chair",
  ])
);

gpt 코드

개선된 점

• map 대신 forEach: map 대신 forEach를 사용하는 것이 더 적합합니다. map은 값을 반환하는데, 여기서는 반환값을 사용하지 않기 때문입니다.
• 정렬 두 번 필요 없음: 첫 번째 cases.sort((a, b) => a.localeCompare(b))에서 사전 순으로 정렬하고 있지만, 이는 이미 마지막에 조건으로 들어가므로 처음부터 정렬할 필요가 없습니다.
• 효율성 개선: 정렬 후에 다시 빈도를 확인하는 대신, 한 번의 루프에서 빈도와 사전순을 동시에 처리할 수 있습니다.

function bestseller(cases) {
  let bookMap = new Map();

  // 책의 빈도를 계산
  cases.forEach((book) => {
    bookMap.set(book, (bookMap.get(book) || 0) + 1);
  });

  let maxCount = 0;
  let bestBook = '';

  // 최대 빈도와 사전 순으로 가장 앞서는 책을 찾음
  bookMap.forEach((count, book) => {
    if (count > maxCount || (count === maxCount && book < bestBook)) {
      maxCount = count;
      bestBook = book;
    }
  });

  return bestBook;
}

4. 크로스워드

문제
동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.

세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다.

다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오.

입력
첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.

출력
첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다.

내 풀이

function crossWord(M, N, cases) {
  const arr = new Array(M).fill(0).map(() => new Array(N).fill(0));

  cases.split(`\n`).map((item, index) => {
    const arr2 = item.split("");
    for (let i = 0; i < arr2.length; i++) {
      arr[index][i] = arr2[i];
    }
  });
  let wordArr = [];

  //가로만 체크
  for (let i = 0; i < M; i++) {
    let rowStr = "";
    for (let j = 0; j < N; j++) {
      // 가로줄 단어 체크
      if (arr[i][j] === "#") {
        // 빈문자열 방지
        if (rowStr.length > 1) wordArr.push(rowStr);
        rowStr = "";
      } else {
        rowStr += arr[i][j];
      }
    }
    if (rowStr.length > 1) wordArr.push(rowStr);
  }

  //세로만 체크
  for (let i = 0; i < N; i++) {
    let colStr = "";
    for (let j = 0; j < M; j++) {
      if (arr[j][i] === "#") {
        if (colStr.length > 1) wordArr.push(colStr);
        colStr = "";
      } else {
        colStr += arr[j][i];
      }
    }
    if (colStr.length > 1) wordArr.push(colStr);
  }
  console.log("wordArr", wordArr);

  const result = wordArr.sort((a, b) => {
    return a.localeCompare(b);
  });
  return result[0];
}

crossWord(4, 5, `adaca\nda##b\nabb#b\nabbac`);

GPT

• 2차원 배열 정의해서 개선

function crossWord(M, N, cases) {

  const arr = cases.split('\n').map(row => row.split(''));

  let wordArr = [];

  // 가로 단어 추출
  for (let i = 0; i < M; i++) {
    let rowStr = "";
    for (let j = 0; j < N; j++) {
      if (arr[i][j] === "#") {
        if (rowStr.length > 1) wordArr.push(rowStr);
        rowStr = "";
      } else {
        rowStr += arr[i][j];
      }
    }
    if (rowStr.length > 1) wordArr.push(rowStr);
  }

  // 세로 단어 추출
  for (let i = 0; i < N; i++) {
    let colStr = "";
    for (let j = 0; j < M; j++) {
      if (arr[j][i] === "#") {
        if (colStr.length > 1) wordArr.push(colStr);
        colStr = "";
      } else {
        colStr += arr[j][i];
      }
    }
    if (colStr.length > 1) wordArr.push(colStr);
  }

  // 사전순 정렬 후 첫 번째 단어 반환
  wordArr.sort((a, b) => a.localeCompare(b));

  return wordArr[0];
}

console.log(crossWord(4, 5, `adaca\nda##b\nabb#b\nabbac`));  // 예제 입력

마무리

• 여러 메서드 정의에 좀 더 익숙해지면 좋을 것 같습니다.