ksoosung77   2년 전

이 문제를 시간초과 없이 풀기 위해서는 어떻게 해야 할 지 잘 모르겠습니다.

힌트로는 트리를 이용한 집합과 맵이라는데 그런데도 잘 모르겠습니다.

저에게 어떻게 시작해야 할지에 대한 다른 힌트를 줄 수 있나요?

ckdgus2482   2년 전

주어진 수를 key로 하고 주어진 수의 원래 인덱스를 value로 하는 맵 또는 딕셔너리 또는 해시맵 등의 연관 자료구조를 이용하면 됩니다

즉 NlgN에 정렬을 한번하시고 그렇게 정렬을 할때 원래의 인덱스 정보도 함께 남겨놔서, 정렬 전의 배열과 비교하면서 풉니다.

ksoosung77   2년 전

잘 설명해주셔서 고맙습니다.

여전히 이해는 못하겠지만 말씀하신데로 최대한 노력해보겠습니다.

ksoosung77   2년 전

진짜 고맙습니다 ckdgus2482님 힌트를 받은 후 map이 어떻게 시간을 줄이고 왜 그런지 생각을 하다가

map을 하면 한 인덱스를 i라 할때 그 앞의 0부터 i-1사이중 가장 큰 값을 찾을때까지 걸리는 시간 없이 바로 어느 위치에 있는지 알 수 있어서 쓴다는 것을 안 후

코딩으로 만들어서 바로 맞췄습니다

감사합니다

댓글을 작성하려면 로그인해야 합니다.