강의로 돌아가기
김태홍

25~30번 시간초과되시는분 참고

25~30번 시간초과 되시는분들은 아마도 저와같이

닉네임을 Change할때 (기존 유저가 새로운닉네임으로 Enter할때, Change 명령이 들어올때)
지금까지 기록된 모든 result를 순회하면서 해당 아이디의 닉네임을 바꾼다면 시간복잡도 O(n)이 추가로듭니다.
즉, 명령순회 O(n)x Change명령(result순회) O(n) 곱해서 총 시간복잡도 O(n2)이 들어서 시간초과가 납니다.

이걸 해결하기위해선, result형태에 ID + "들어왔습니다" or "나갔습니다" 형태로 저장하고
Map을 이용해, Key:Id value: 닉네임 으로 저장,변경했습니다.
모든 명령을 순회했다면, result를 순회하여 ID의 value값 닉네임으로 바꿔주어 원하던 닉네임+ "들어왔습니다" or "나갔습니다"형태로 출력합니다.
이렇게 짜시면, 명령순회 O(n) + result순회 O(n) = 총 시간복잡도는 2*O(n)이 되어서, 단축이 됩니다.

  • 조대열

    감사합니다!!

    조대열―2021.07.01 14:37
  • ggongjukim

    덕분에 풀었엉요!

    ggongjukim―2022.03.03 23:41
  • M.P.H

    감사합니다 덕분에 통과했습니다

    M.P.H―2023.05.09 23:52
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.