반응형
1071
-
1071번 : 소트알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 19:18
https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 문제는 단순하다. A[i] + 1 != A[i+1] 을 만족하도록 모든 수를 다시 배치하는 것이다. 아이디어 : 두 수를 비교해서 위치를 바꾸는 일반적인 정렬 방식은 사용하지 않는다. 수들을 처음부터 하나하나 다시 배치하는 아이디어로 접근한다. 우선, 수를 하나 택한다고 생각해보자. 이 수를 뺀 나머지 수들을 이용해서 절대로 배열을 완성할 수 없다면, 그 수를 택할 수 없다. 반대로 말하면 -> ..