정렬 문제 풀이 (feat :프로그래머스)

K번째 수

https://school.programmers.co.kr/learn/courses/30/lessons/42748

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해 주세요.

제한 사항

array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.

function solution(array, commands) {
  let answer = [];
  for (let i = 0; i < commands.length; i++) {
    const one = commands[i][0];
    const two = commands[i][1];
    const third = commands[i][2];

    // 자르기 시작점과 끝점이 같은 경우
    if (one === two) {
      // 위치가 1인 경우에만
      third === 1 && answer.push(array[one - 1]);
    } else if (one > two) {
      // console.log("one", one);
    } else {
      const cutArray = array
        .slice(one - 1, two)
        .sort((a, b) => a - b);

      answer.push(cutArray[third - 1]);
    }
  }
  console.log("answer", answer);

  return answer;
}

가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]을 만들 수 있고, 이 중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해 주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

function solution(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = 0; j < numbers.length - 1 - i; j++) {
      // 문자열 비교로 교환 여부 결정
      const a = String(numbers[j]) + String(numbers[j + 1]);
      const b = String(numbers[j + 1]) + String(numbers[j]);

      if (a < b) {
        let temp = numbers[j];
        numbers[j] = numbers[j + 1];
        numbers[j + 1] = temp;
      }
    }
  }

  // 정렬된 배열을 문자열로 변환 및 결합
  let result = numbers.join("");

  // 결과가 "0"으로 시작할 경우 처리
  return result[0] === "0" ? "0" : result;
}

⇒ 버블 정렬 사용으로 시간 초과 발생
⇒ O(n²)
⇒ sort()를 사용하면 O(n log n)의 시간 복잡도로 풀이 가능

퀵 정렬로 구현해서 해결

• 해당 풀이로는 시간 초과 문제가 발생하지 않음

function quickSort(arr) {
  if (arr.length <= 1) return arr;  // 재귀 탈출 조건

  const pivot = arr[Math.floor(arr.length / 2)]; // 중간값을 기준점으로 설정
  const left = [];
  const right = [];
  const equal = [];

  for (let i = 0; i < arr.length; i++) {
    const a = String(arr[i]);
    const b = String(pivot);

    if (a + b > b + a) {
      left.push(arr[i]);  // 왼쪽 그룹: pivot보다 큰 값
    } else if (a + b < b + a) {
      right.push(arr[i]); // 오른쪽 그룹: pivot보다 작은 값
    } else {
      equal.push(arr[i]); // pivot과 같은 값
    }
  }

  // 재귀적으로 정렬 후 병합
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

function solution(numbers) {
  const sortedNumbers = quickSort(numbers);
  const result = sortedNumbers.join('');

  // 결과가 "0000..."인 경우, "0" 반환
  return result[0] === '0' ? '0' : result;
}

GPT의 간단한 풀이

• JS의 sort 정렬에도 이미 최적화된 로직이 들어가 있어서 시간 초과에 걸리지 않는다.

function solution(numbers) {
  // 숫자 배열을 문자열로 변환
  const numbersStr = numbers.map(String);

  // 정렬 기준: (a + b)와 (b + a)를 비교
  numbersStr.sort((a, b) => (b + a) - (a + b));

  // 정렬된 배열을 이어 붙임
  const result = numbersStr.join('');

  // 결과가 '0'으로 시작하는 경우(즉, '000...')는 '0'을 반환
  return result[0] === '0' ? '0' : result;
}

H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해 주세요.

제한 사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations	return
[3, 0, 6, 1, 5]	3

내 풀이

function solution(citations) {
  let answer = -1;

  // 배열 복사 후 내림차순 정렬
  const arr = [...citations].sort((a, b) => b - a); // 내림차순

  for (let i = 0; i < arr.length; i++) {
    const des = arr[i];
    let count = 0;

    for (let k = 0; k < arr.length; k++) {
      // 현재 논문의 수가 des 이상이면 count 증가
      if (arr[k] >= des) {
        count += 1;
      }
    }

    // des가 해당 숫자 이상일 때 answer에 할당
    if (des <= count) {
      answer = des;
      break; // 조건을 충족한 경우 더 이상의 비교는 필요하지 않으므로 루프를 종료
    }
  }

  console.log("answer", answer);

  return answer;
}

GPT 풀이

function solution(citations) {
  const n = citations.length;
  
  // 내림차순 정렬
  citations.sort((a, b) => b - a);
  
  let hIndex = 0;
  
  // H-Index 계산
  for (let i = 0; i < n; i++) {
    if (citations[i] >= i + 1) {
      hIndex = i + 1; // H-Index 업데이트
    } else {
      break; // 조건이 더 이상 충족되지 않으면 루프 종료
    }
  }
  
  return hIndex;
}

// 테스트
console.log(solution([3, 0, 6, 1, 5])); // 3

KAKAO 블라인드 파일명 정렬

https://school.programmers.co.kr/learn/courses/30/lessons/17686

내 풀이

function solution(files) {
  function searchIndex(c) {
    let startIndex = -1;
    let endIndex = -1;
    for (let i = 0; i < c.length; i++) {
      if (!isNaN(c[i]) && c[i] !== " ") {
        if (startIndex === -1) startIndex = i;
        endIndex = i;
      } else if (startIndex !== -1) {
        break; // 숫자가 끝나면 종료
      }
    }
    return [startIndex, endIndex];
  }

  // 파일 정렬
  const sortedArray = files.sort((a, b) => {
    const aIndex = searchIndex(a);
    const bIndex = searchIndex(b);

    // HEAD 추출 및 비교(대소문자 무시)
    const headA = a.substring(0, aIndex[0]).toUpperCase();
    const headB = b.substring(0, bIndex[0]).toUpperCase();

    // HEAD 비교가 같을 경우 NUMBER 비교
    if (headA === headB) {
      const numA = parseInt(a.substring(aIndex[0], aIndex[1] + 1), 10);
      const numB = parseInt(b.substring(bIndex[0], bIndex[1] + 1), 10);
      return numA - numB;
    }

    // HEAD가 다를 경우 사전순 정렬
    return headA.localeCompare(headB);
  });

  return sortedArray;
}

GPT 풀이

• 정규식을 이용한 풀이로, 내가 직접 사용하기에는 좀 무리가 있어 보였다.

function solution(files) {
  // 파일명에서 HEAD, NUMBER, TAIL 추출
  function parseFileName(file) {
    const match = file.match(/^([a-zA-Z-\. ]+)(\d{1,5})/);
    // HEAD: match[1], NUMBER: match[2], TAIL은 필요 없음
    return {
      head: match[1],
      number: match[2],
      original: file
    };
  }

  // 정렬 함수
  return files
    .map(parseFileName) // 파일명을 HEAD, NUMBER로 나누어 저장
    .sort((a, b) => {
      const headA = a.head.toUpperCase();
      const headB = b.head.toUpperCase();

      // HEAD가 같으면 NUMBER 비교
      if (headA === headB) {
        return Number(a.number) - Number(b.number);
      }
      // HEAD가 다르면 사전순으로 정렬
      return headA.localeCompare(headB);
    })
    .map(file => file.original); // 정렬 후 원본 파일명을 반환
}

마무리

• 정렬 문제에는 여러 정렬 기법을 넣어서 풀어 보는 것이 좋겠다고 생각했으나, 내장 함수를 이용하는 것이 속도 측면에서 확실히 효율이 좋을 수밖에 없는 듯하다.
• 어떤 정렬 기법이 있는지와 구현 방법 정도만 알아 두면 되겠다는 생각이 들었습니다.