inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 등수구하기

빅오 시간 복잡도 알려주세요!!!!!!

435

dgkim3811

작성한 질문수 16

0

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)인거 같은데... 정확하게 알려주시면 감사하겠습니다😭

 

빅오표기법 javascript 빅오 코테 준비 같이 해요! bigO 시간복잡도

답변 1

0

김태원

안녕하세요^^

시간복잡도는 중첩 for 문이라도 안쪽 for문이 반복하는 횟수가 시간복잡도를 결정합니다.

결국 result[index] = rank; 연산을 몇 번 했는가가 중요합니다.

O(n)으로 보여집니다.

 

continue를 사용하는 이유

0

80

2

정렬 가능 여부 판단하기

0

65

2

알고리즘 학습법 관련해서 질문드립니다.

0

86

1

코드 리뷰 부탁드립니다!

0

90

1

indexOf를 사용해서 풀어보았습니다 !!

0

69

1

저는 이런식으로 구현 해보았습니다 !!

0

64

1

12,13,14 강의 소리만 나오고 검은 화면입니다

0

101

3

반복문 최소화하고 indexOf 사용해서 풀어봤습니다

0

63

1

영상 보기 전에 직접 풀어봤습니다.

0

74

1

섹션1의 17번문제 이 풀이로 풀어도 될까요?

0

136

2

정규표현식으로 처리해도 상관없나요 ?

0

120

2

3칸씩 건너뛸 수 있을 경우

0

126

2

강의에 대해 질문있습니다.

0

136

2

Object와 Set을 이용해 풀어봤습니다.

0

117

2

이렇게 해도 되나요?

0

102

2

선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.

0

145

2

이렇게 풀어도 괜찮을까요?

0

138

1

이렇게 풀어도 괜찮을까요?

0

112

1

모든 아나그램 찾기에서 시간복잡도

0

98

1

코드리뷰 부탁드립니다.

0

130

1

for loop 탈출은 return 문으로 해도 되지 않나요?

0

133

1

투포인트알고리즘으로 풀어봤습니다.

0

142

0

코드 리뷰 부탁드립니다.

0

120

1

코드 맞게 작성한 거 아닌가여??

0

146

1