인프런 커뮤니티 질문&답변

function solution(scores) {
  let scoreGroup = {};
  let result = [];

  scores.forEach((score, i) => {
    if (scoreGroup[score] === undefined) {
      scoreGroup[score] = [];
    }
    scoreGroup[score].push(i);
  });

  let rank = scores.length;

// 아래 부분 시간 복잡도 질문합니다.
  Object.keys(scoreGroup).forEach((key) => {
    rank -= scoreGroup[key].length - 1;

    scoreGroup[key].forEach((index) => {
      result[index] = rank;
    });

    rank -= 1;
  });

  return result;
}

제가 짠 코드는 다음과 같습니다.

Q) 여기서 이 부분 시간 복잡도가 O(n)인가요 O(n^2)인가요??

Object.keys(scoreGroup).forEach((key) => {
    rank -= scoreGroup[key].length - 1;

    scoreGroup[key].forEach((index) => {
      result[index] = rank;
    });

    rank -= 1;
  });

forEach가 이중으로 실행되지만 key가 n개면 각 value 길이는 1이 되고, key가 1개이면 각 value 길이가 n이 되는 상황이라서 O(n)인거 같은데... 정확하게 알려주시면 감사하겠습니다😭