17505번 링고와 수열

문제 설명

이번 문제는 1~N까지의 수로 이루어진 수열 A에서 i < j면서 A[i] > A[j]인 개수가 K개일 수 있는지 구하는 문제입니다.

K개인 수열이 있다면 해당 수열을 출력(조건을 만족하는 수열의 개수가 여러 개라면 한 개만 출력)합니다.

K개인 수열이 없다면 -1을 출력합니다.

 

문제 풀이

아이디어

문제의 조건을 이용하는 방법

수열 A에서 i < j면서 A[i] > A[j]를 만족할 수 있는 경우는 앞쪽의 원소가 뒤쪽의 원소보다 큰 경우입니다.

 

N=5인 경우에 대한 예시를 들어보도록 하겠습니다. (A = [1,2,3,4,5])

위의 조건을 만족하는 개수가 0인 경우를 생각해보면 앞쪽의 원소가 뒤쪽의 원소보다 항상 작은 경우입니다.

-> [1, 2, 3, 4, 5]

 

위의 조건을 만족하는 개수가 1인 경우는 위 조건을 한 가지만 만족하면 되므로 가장 큰 원소와 두 번째로 큰 원소의 개수를 옮기는 경우가 될 수 있습니다.

-> [1, 2, 3, 5, 4]

 

위의 조건을 만족하는 원소의 개수가 4인 경우는 가장 큰 원소 5가 가장 앞에 있는 경우입니다.

-> [5, 1, 2, 3, 4]

 

위의 조건을 만족하는 원소의 개수가 5인 경우는 가장 큰 원소 5가 가장 앞에 있고, 두 번째로 큰 4가 세 번째로 큰 3보다 앞에 있는 경우입니다.

-> [5, 1, 2, 4, 3]

 

위와 같이 처음에 오름차순으로 sorting한 뒤 찾게 되면, 큰 원소를 어디에 배치하느냐에 따라 조건을 만족하는 개수를 구할 수 있습니다.

 

 

풀이

현재 내가 관여하고 있는 배열에서 가장 큰 수를 움직이면서 조건을 만족하는 개수가 K개를 만족할 때까지 가장 큰 수를 움직이도록 했습니다.

 

while문을 반복하면서 가장 큰 원소를 가장 앞쪽으로 옮길 때 조건을 만족하는 개수를 K에서 빼주면서, K가 0이 될 때까지 반복해줍니다.

 

조건을 만족하는 개수의 최대값은 (N-1+1)*N/2이고 문제의 조건에서 0<=K<=N*(N-1)/2 라고 되어 있으므로 조건을 만족하는 개수가 K가 되지 않을 경우는 없으므로 -1은 출력되지 않습니다.

 

 

 

해결

앞쪽의 원소가 뒤쪽의 원소보다 큰 경우라고 말로 쉽게 풀어내니 잘 풀렸던 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/17505

17505번: 링고와 순열

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/17505.py