정렬 - K번째 수 / 가장 큰 수 / H-Index

K번째 수

배열 조작과 정렬을 포함한 간단한 알고리즘 구현 문제

풀이 전략

1. 명령 처리
   • 각 command의 값 i, j, k를 구조 분해 할당으로 꺼낸다.
   • array.slice(i - 1, j)를 통해 i번째부터 j번째까지를 잘라낸다.
2. 정렬:
   • 자른 배열을 sliced.sort((a, b) => a - b)로 오름차순 정렬한다.
3. k번째 값:
   • 정렬된 배열에서 k - 1번째 인덱스 값을 가져와 answer 배열에 추가한다.
4. 결과 반환:
   • 모든 commands를 처리한 후 결과 배열 answer를 반환한다.

알고리즘 풀이

function solution(array, commands) {
  return commands.map(([i, j, k]) => {
    const sliced = array.slice(i - 1, j).sort((a, b) => a - b);
    return sliced[k - 1];
  });
}

시간 복잡도

1. 배열 자르기: 각 명령에 대해 O(j - i) (평균적으로 약 O(n)).
2. 정렬: 잘라낸 배열의 길이가 최대 n이라면, 정렬은 O(n log n).
3. 전체 명령 반복: 명령 개수 m.

총 시간 복잡도는 O(m × n log n).

---

가장 큰 수

주어진 숫자 배열에서 숫자들을 이어 붙여 만들 수 있는 가장 큰 수를 찾는 문제

주어진 숫자 배열에서 숫자들을 이어 붙여 만들 수 있는 가장 큰 수를 찾는 문제

풀이 전략

1. 문자열 정렬 기준:
   • 주어진 두 숫자 a, b를 문자열로 변환 후: aa bb
     • a+ba + ba+b와 b+a를 비교. b+ab + a
   • 예를 들어 a=”6”,b=”10”: a=”6”,b=”10”a = “6”, b = “10”
     • “610”“610”“610”와 “106”를 비교해 더 큰 쪽으로 정렬. “106”“106”
2. 정렬 및 결합:
   • 정렬 후 문자열을 이어붙여 최종 결과를 얻는다.
3. 예외 처리:
   • 모든 숫자가 0인 경우 ([0, 0, 0] 등) 결과는 "0"이어야 한다.

알고리즘 풀이

function solution(numbers) {
  // numbers를 문자열로 변환하여 정렬
  const sorted = numbers.map(String).sort((a, b) => b + a - (a + b));

  const answer = sorted.join("");

  return answer[0] === "0" ? "0" : answer;
}

시간 복잡도

1. 문자열 변환 및 정렬:
   • 문자열 변환: O(n). O(n)O(n)
   • 정렬: O(nlogn), 정렬 기준 비교는 O(1). O(nlog⁡n)O(n \log n) O(1)O(1)
2. 전체 시간 복잡도:
   • O(nlog⁡n)O(n \log n)O(nlogn), 여기서 n은 numbers 배열의 길이.

---

H-Index

논문 h번 이상 인용된 논문이 h편 이상, 나머지 논문은 h번 이하로 인용되는 특정 조건을 만족하는 최댓값 h를 찾는 문제

풀이 전략

1. 정렬

• 주어진 인용 횟수를 내림차순으로 정렬하여 높은 인용 횟수부터 처리한다.
• 예: citations = [3, 0, 6, 1, 5] → 정렬 후 [6, 5, 3, 1, 0].

1. 조건 확인

• 정렬된 배열에서 각 논문의 인용 횟수를 순회하며 h를 계산한다.
• citations[i] ≥ i+1를 만족하지 않는 순간, h는 i가 된다.

알고리즘 풀이

function solution(citations) {
  citations.sort((a, b) => b - a); // 인용 횟수 내림차순 정렬

  // H-Index 계산
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] <= i) {
      return i;
    }
  }

  return citations.length; // 모든 논문이 조건이 만족할 경우
}

시간 복잡도

1. 정렬: O(nlogn), 여기서 n은 논문의 개수.

   O(nlog⁡n)O(n \log n)

   nn

2. H-Index 계산: O(n).

   O(n)O(n)

3. 전체 시간 복잡도: O(nlogn).

   O(nlog⁡n)O(n \log n)