13884번 - 삭삽 정렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 210 | 84 | 72 | 47.682% |
문제
선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.
- 배열의 요소 하나를 선택합니다.
- 배열에서 해당 요소를 삭제합니다.
- 해당 요소를 배열의 맨 뒤에 삽입합니다.
선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.
입력
입력의 첫 번째 줄에는 테스트케이스를 나타내는 P(1 ≤ P ≤ 100)가 주어집니다. 이후 이어지는 행에서 각각 테스트케이스에 해당하는 데이터 세트가 주어집니다.
각각 데이터 세트는 조건에서 주어진 대로 삭삽 정렬을 수행해야하며, 독립적으로 처리되어야 합니다. 각 데이터 세트는 최소 두 행 이상이 주어집니다.
첫 번째 행에서 데이터 세트의 번호인 K와 공백 이후 정렬 할 배열의 길이인 N(1 ≤ N ≤ 1000)이 주어집니다.
그 이후 행에서 정렬 할 배열을 구성하는 N개의 양의 정수가 주어지는데, 마지막 행을 제외한 모든 행에서 10개로 이루어진 109 보다 작은 숫자들이 주어집니다. (마지막 행은 10개 보다 적은 숫자들이 주어집니다.)
주어지는 숫자들은 동일한 숫자가 여러 번 주어질 수 있습니다.
출력
각각의 데이터 세트의 번호를 나타내는 K와 공백 이후 최소 삭삽 정렬 과정 수행 횟수를 한 행으로 출력합니다.
예제 입력 1
3 1 3 1 3 2 2 6 1 5 2 4 3 6 3 23 67890 56312 999999999 12345 23456 38927 45632 100345 98765 23456 87654 43278 23456 117654 321899 25432 54326 217435 26845 31782 33456 41234 56213
예제 출력 1
1 1 2 3 3 15
힌트
예제 입력의 첫 번째 데이터 세트인,
1 3
1 3 2
는 다음과 같은 삭삽 정렬 과정을 거칩니다.
3을 선택하여 삭제하고, 배열의 맨 뒤에 삽입하여
1 2 3
으로 1번의 삭삽 정렬 과정을 수행하여 정렬을 종료하여
1 1
을 출력합니다.
출처
ICPC > Regionals > North America > Greater New York Region > 2016 Greater New York Programming Contest H번
- 문제를 번역한 사람: devetude
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호