image.png

문제 파악

삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이너를 트립으로 두면 문제를 NlogN의 시간 복잡도로 해결할 수 있다. 숫자를 하나씩 원래 수열에 넣는 과정에서 숫자들을 검색하고 삭제하는 과정이 필요하기 때문에 트립 구조가 효율적으로 사용된다. 메모리 오류가 발생하는데 원인을 찾지 못해 정답은 띄우지 못했다.

문제 풀이

대부분의 풀이 과정이 내가 파악한 것과 비슷했다.