주어진 수를 key로 하고 주어진 수의 원래 인덱스를 value로 하는 맵 또는 딕셔너리 또는 해시맵 등의 연관 자료구조를 이용하면 됩니다
즉 NlgN에 정렬을 한번하시고 그렇게 정렬을 할때 원래의 인덱스 정보도 함께 남겨놔서, 정렬 전의 배열과 비교하면서 풉니다.
23883번 - 알고리즘 수업 - 선택 정렬 3
주어진 수를 key로 하고 주어진 수의 원래 인덱스를 value로 하는 맵 또는 딕셔너리 또는 해시맵 등의 연관 자료구조를 이용하면 됩니다
즉 NlgN에 정렬을 한번하시고 그렇게 정렬을 할때 원래의 인덱스 정보도 함께 남겨놔서, 정렬 전의 배열과 비교하면서 풉니다.
잘 설명해주셔서 고맙습니다.
여전히 이해는 못하겠지만 말씀하신데로 최대한 노력해보겠습니다.
진짜 고맙습니다 ckdgus2482님 힌트를 받은 후 map이 어떻게 시간을 줄이고 왜 그런지 생각을 하다가
map을 하면 한 인덱스를 i라 할때 그 앞의 0부터 i-1사이중 가장 큰 값을 찾을때까지 걸리는 시간 없이 바로 어느 위치에 있는지 알 수 있어서 쓴다는 것을 안 후
코딩으로 만들어서 바로 맞췄습니다
감사합니다
댓글을 작성하려면 로그인해야 합니다.
ksoosung77 2년 전
이 문제를 시간초과 없이 풀기 위해서는 어떻게 해야 할 지 잘 모르겠습니다.
힌트로는 트리를 이용한 집합과 맵이라는데 그런데도 잘 모르겠습니다.
저에게 어떻게 시작해야 할지에 대한 다른 힌트를 줄 수 있나요?