알고스팟 문제 링크: https://algospot.com/judge/problem/read/INSERTION
algospot.com :: INSERTION
삽입 정렬 뒤집기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽
algospot.com
크기가 n이고 1~n까지의 순서없이 섞여있는 수열이 있다.
해당 수열의 원래 형태는 알 수 없지만, 수열을 삽입 정렬하는 경우 각 원소가 왼쪽으로 몇 칸이나 이동했는지가 입력으로 주어진다.
이때 원래 수열을 찾아내는 문제이다.
원래수열이 A[]라 할때 마지막 숫자 A[n-1]이 왼쪽으로 몇 칸 움직였는지를 알면 A[n-1]이 어떤 숫자인지 알 수 있다.
만약 n이 5이고 마지막 숫자가 왼쪽으로3칸 움지였다면, 1~5의 숫자중 마지막 숫자보다 큰게 3개 있다는 것이고
이것은 마지막 숫자가 2라는것을 의미한다.
이러한 방법으로 트립을 이용해 k번째 숫자를 찾고 해당 노드를 삭제하는 방식으로 끝에서부터 수열을 맞춰갈 수 있다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/INSERTION.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 등산로 (문제 ID: MORDOR) c++ (0) | 2021.10.14 |
|---|---|
| algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++ (0) | 2021.10.11 |
| algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++ (0) | 2021.10.07 |
| algospot 요새 (문제 ID: FORTRESS) c++ (0) | 2021.10.06 |
| algospot 트리 순회 순서 변경 (문제 ID: TRAVERSAL) c++ (0) | 2021.10.05 |