백준 정렬 문제 풀기(feat :골드)

성찬홍·2024년 9월 28일
정렬

자료구조

목록 보기
18/29
post-thumbnail

정렬 게임

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

내 풀이

// 카드 정렬하기
function jungyeolGame(str) {
  let a = str.split("\n");
  console.log(a);

  // 수열의 개수
  const count = a[0];
  a.shift();

  // 수열들
  let arr = a[0].split(" ");
  a.shift();

  // 세트의 개수 K
  let setCount = a[0];
  a.shift();

  // 네 번째 줄부터는 한 줄에 한 개씩 오름차순, 내림차순 // 여기부터는 카운트들
  let set = [...a];

  console.log(set);
  function sortFunc(asc, desc) {
    let temArr = arr;
    let tempArr2 = arr;

    let a2 = temArr.slice(0, asc).sort((a, b) => a - b);
    let b2 = tempArr2.slice(asc);

    let tempAnswer = [...a2, ...b2];

    let temDesc1 = tempAnswer;
    let temDesc2 = tempAnswer;
    let c = temDesc1.slice(0, desc).sort((a, b) => b - a);
    let d = temDesc2.slice(desc);

    return [...c, ...d].join(" ");

    // asc 지점까지만 오름차순 실행
  }

  let answer = "";
  for (let i = 0; i < setCount; i++) {
    console.log("찍힘");
    let temp = set[i].split(" ");
    let asc = parseInt(temp[0]);
    let desc = parseInt(temp[1]);
    let result = sortFunc(asc, desc);
    answer += i === setCount - 1 ? result : result + "\n";
  }
  return answer;
}

GPT 풀이

  • 줄여진 코드로 정리됐다.
function jungyeolGame(str) {
  let a = str.trim().split("\n");

  // 수열 배열
  let arr = a[1].split(" ").map(Number);
  
  // 세트의 개수 K
  let setCount = parseInt(a[2], 10);
  
  // 오름차순, 내림차순 범위 정보
  let operations = a.slice(3).map((op) => op.split(" ").map(Number));
  
  // 정렬 세트를 반복
  for (let i = 0; i < setCount; i++) {
    let [asc, desc] = operations[i];

    // 오름차순 정렬
    let ascSorted = arr.slice(0, asc).sort((a, b) => a - b);
    
    // 정렬된 부분과 나머지 결합
    arr = [...ascSorted, ...arr.slice(asc)];

    // 내림차순 정렬
    let descSorted = arr.slice(0, desc).sort((a, b) => b - a);
    
    // 정렬된 부분과 나머지 결합
    arr = [...descSorted, ...arr.slice(desc)];
  }

  // 최종 결과 반환
  return arr.join(" ");
}

순회 강연

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

풀이

function circuitUniv(arr) {
  // day 순으로 정렬
  arr.sort((a, b) => a.day - b.day);

  // 강의의 최대 남은 기간 찾기
  let maxDate = Math.max(...arr.map((item) => item.day));

  // 끼워 넣을 날짜를 만들어 준다.
  const arr2 = new Array(maxDate + 1).fill(0);

  for (let i = 0; i < arr.length; i++) {
    // 강의의 남은 기간을 거꾸로 검사
    for (let j = arr[i].day; j > 0; j--) {
      arr2[j] = Math.max(arr2[j], arr2[j - 1] + arr[i].pay);
    }
  }

  console.log("arr2", arr2);
  return Math.max(...arr2); // 최종 최대 수익 반환
}

// 예시 데이터
console.log(
  circuitUniv([
    { pay: 20, day: 1 },
    { pay: 2, day: 1 },
    { pay: 10, day: 3 },
    { pay: 100, day: 2 },
    { pay: 8, day: 2 },
    { pay: 5, day: 20 },
    { pay: 50, day: 10 },
  ])
);

수열의 점수

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

문제

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총합의 최댓값을 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총합이 29가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.

출력

첫째 줄에 최대 점수를 출력한다.

내 풀이

function score(array) {
  // 한 개의 정수 제거 => 이 정수가 점수가 됨
  // 두 개의 정수를 제거 => 두 정수의 곱이 점수가 됨
  // 이를 반복해서 아무 수도 남지 않게 됐을 때 점수 총합의 최댓값을 구하는 프로그램
  // 내림차순 정렬
  let answer = 0;
  array.sort((a, b) => a - b);

  let negative = [];
  let positive = [];

  array.forEach((element) => {
    if (element < 0) {
      negative.push(element);
    } else {
      positive.push(element);
    }
  });
  positive.reverse();

  while (positive.length !== 0) {
    // 1이면 그냥 더하기
    if (positive[0] === 1) {
      answer += positive[0];
      positive.shift();
    }

    // 1은 아니지만 뒤에 값이 없으면 그냥 더하기
    else if (positive[0] && positive[0] !== 1 && !positive[1]) {
      answer += positive[0];
      positive.shift();
    }

    // [0]이 1은 아니고 뒤에 [1]도 있지만 1인 경우는 그냥 더하기
    else if (
      positive[0] &&
      positive[0] !== 1 &&
      positive[1] &&
      positive[1] === 1
    ) {
      answer += positive[0];

      positive.shift();
    }

    // [0]이 1이 아니고 [1]도 1을 넘으면 곱해서 더하기
    else if (positive[0] && positive[0] > 1 && positive[1] && positive[1] > 1) {
      answer += positive[0] * positive[1];

      positive.shift();
      positive.shift();
    }

    console.log(positive);
  }

  console.log("po answer", answer);

  while (negative.length !== 0) {
    if (negative[0] && negative[1]) {
      answer += negative[0] * negative[1];
      // 앞의 두 요소를 제거
      negative.shift();
      negative.shift();
    } else {
      console.log("negative[0]", negative[0]);
      answer += negative[0];
      // 앞의 한 요소만 제거
      negative.shift();
    }
  }

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

score([5, -1, 5, -3, 5, 1]);

GPT 풀이 및 개선점

  • shift() 대신 slice()를 사용하거나 단순한 인덱스를 통해 배열의 요소에 접근하여 처리합니다.
  • 정렬과 순회(양수, 음수 분리) 후 필요한 계산을 수행하기 때문에 전체 시간 복잡도가 O(n log n)입니다. 이는 배열을 정렬하는 시간과 두 번의 순회에 따른 것입니다.
function score(array) {
  let answer = 0;

  // 배열을 음수, 양수, 0으로 나누어 처리
  let negative = [];
  let positive = [];
  let oneCount = 0; // 1을 따로 카운트

  array.forEach((element) => {
    if (element < 0) {
      negative.push(element);
    } else if (element === 1) {
      oneCount++; // 1은 따로 더함
    } else if (element > 0) {
      positive.push(element);
    }
  });

  // 음수는 오름차순으로 정렬(작은 수일수록 두 개를 곱했을 때 값이 커짐)
  negative.sort((a, b) => a - b);

  // 양수는 내림차순으로 정렬(큰 수일수록 두 개를 곱했을 때 값이 커짐)
  positive.sort((a, b) => b - a);

  // 1 처리(1은 무조건 더하는 것이 유리)
  answer += oneCount;

  // 양수 처리
  while (positive.length > 1) {
    // 두 개씩 묶어서 곱한 값을 더함
    answer += positive[0] * positive[1];
    positive.shift();
    positive.shift();
  }

  // 양수가 하나 남아 있으면 더함
  if (positive.length === 1) {
    answer += positive[0];
  }

  // 음수 처리
  while (negative.length > 1) {
    // 두 개씩 묶어서 곱한 값을 더함
    answer += negative[0] * negative[1];
    negative.shift();
    negative.shift();
  }

  // 음수가 하나 남아 있으면 그냥 더함
  if (negative.length === 1) {
    answer += negative[0];
  }

  return answer;
}

console.log(score([5, -1, 5, -3, 5, 1])); // 34

1. 속도 차이

  • 내 풀이

    • 여러 번의 shift() 호출로 인해 배열의 앞쪽 요소를 제거하는데, 이는 O(n)의 시간 복잡도를 가지므로 반복적으로 수행할 경우 성능 저하가 발생합니다.
    • 예를 들어 shift()를 호출할 때마다 배열의 모든 요소를 한 칸씩 이동해야 하므로, 최악의 경우 O(n²)의 시간이 걸릴 수 있습니다.

  • 개선된 풀이

    • shift() 대신 slice()를 사용하거나 단순한 인덱스를 통해 배열의 요소에 접근하여 처리합니다.
    • 정렬과 순회(양수, 음수 분리) 후 필요한 계산을 수행하기 때문에 전체 시간 복잡도가 O(n log n)입니다. 이는 배열을 정렬하는 시간과 두 번의 순회에 따른 것입니다.

2. 코드 간결성

  • 내 풀이

    • 중복된 조건문이 많고, 각 조건의 처리 로직이 복잡하게 얽혀 있습니다.
    • 가독성이 떨어지며 변경이나 디버깅이 어려운 구조입니다.

  • 개선된 풀이

    • 각 로직이 명확히 구분되어 있으며, 양수와 음수를 처리하는 로직이 간결합니다.
    • 불필요한 조건문을 제거하고 while문을 통해 같은 패턴을 반복 처리하여 코드가 간단해졌습니다.
    • oneCount를 따로 처리하여 1을 다루는 방식을 명확하게 하였습니다.

3. 비교 요약

요소내 풀이개선된 풀이
시간 복잡도O(n²)O(n log n)
가독성중복된 조건, 복잡한 로직간결한 로직, 명확한 처리
유지 보수성어려움용이

결론

개선된 풀이는 속도와 가독성 면에서 모두 우수합니다. 특히 대량의 데이터에 대한 성능 차이가 크게 나타날 수 있으므로, 가능한 효율적인 알고리즘을 선택하는 것이 중요합니다. 복잡성을 줄이고 가독성을 높이기 위해 불필요한 로직을 제거하고, 반복적인 패턴을 명확하게 처리하는 것이 좋은 코드 작성에 도움이 됩니다.

마무리

  • 골드 단계로 넘어오니 생각해야 할 것들이 많아지고 난이도가 확실히 올라갔다.
  • 어떤 방식으로 풀지 정리해 보고 푸는 연습이 필요할 것 같다.
profile
성찬홍
꾸준한 개발자
이전 포스트

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

다음 포스트

이진 탐색 문제풀이(feat:프로그래머스 입국심사)

0개의 댓글