[질문] C언어 삽입 정렬 알고리즘 문제 질문이 있읍니다.

[서련앓이]

너무 오래 쉬었다가 학교를 복학해서 (컴공) ,

하나도 손에 못 잡히더군요...  insertion sort 의 메커니즘은 이해가 얼추 됬는데,

문제가 이해가 안됩니다..

Input (Standard input)     

In the first line, the number of input keys N, is given(1≤N≤30,000).     

In the next N lines, a key is given in each line. 

Output (Standard output)     

Print the input keys sorted in decreasing order. 

ex)

input  3 3 1 2

output 3 2 1

아웃풋은 입력값을 내림차순으로 정렬해서 프린트 하라는거 같은데

인풋에서 독해는 좀 하겠는데 이해가 영 안가는게 있군여 

첫번째 라인에서 , 입력값 N의 수는 (1<=N<=30000)로 주어진다

다음 N라인에서, 키는 각각의 라인에 주어진다.

인데 .. 구현은 고사하고 문제에서부터 막혔습니다..

저 N의 범위가 인풋으로 주어졌는데  저 N범위내에 모든 값을 소트하라는건지 아니면 배열의 크기를 저 범위로 잡고  입력값을 받은 후

아웃풋으로 소트된 값을 출력하라는건지 아니면 저 범위내에서 랜덤값을 받고 소트를 하라는건지.,. 아니면 그냥 다

씹고 저 예제에 나온대로만 출력해도 되는건지...

두번째 줄도 뭔가 해석이 잘못된거같고... 

구현된 코드도  보고 싶습니다 감사합니다 .

[츄로스님]

N의 값이 30,000은 넘지 않는다는걸 말하는거같습니다. 예를들어 input이 30,001이상이거나, 0 이하인 경우가 없으니 그런상황은 무시해도 되는거같네요.

[츄로스님]

구현되어있는 코드는 https://www.geeksforgeeks.org/insertion-sort/ 이곳에서 보시면 될거같습니다. C뿐만 아니라 다른 언어로도 나와있네요.

[네푸네푸~]

저런 식의 input 방식은, 이런 알고리즘 문제에서는 가장 일반적인 방식입니다.
만약 문제에 쓰이는 입력을 100줄을 주고 싶다면, 제일 첫 줄에 입력의 개수인 100 을 주고 그 다음 줄부터는 100 라인의 입력이 나옵니다.

↲ 를 <CR>으로 본다면
문제에 있는 입력인 '3↲ 3↲ 1↲ 2↲' 은 입력 숫자가 '3'개인데, 그것은 순차적으로 '3↲ 1↲ 2↲' 가 다음 라인에 나온다는 뜻입니다. 그래서 제일 앞의 3이 N이 됩니다.

N의 범위를 명시한 이유는 0보다는 항상 크게 문제를 줄테니 key가 없는지 체크할 필요는 없다는 것을 의미하고,
30000 이 최대라고 했으니, static 배열을 잡든 new를 하든 그런 알아서 하라라는 것입니다. (300000000...0000 이라면 static 배열은 불가능 할테니)
예를 들어, 저 문제의 경우에는 int input[30000]; 으로 하는 것이 최선일 수 있습니다. insert. sort는 공간 복잡도가 O(1) 이니.

[서련앓이]

결국
3을 입력받고 3 ,1,2,를 입력하면
인풋 아웃풋
3 3
3 2
1 1
2
이렇게 출력하라는거고 조교님께서 test case 에서 저 N범위 내의 임의의 값을 넣어준다 즉 첫번째에는 몇개를 출력할지를 입력하는거고 그밑은 N개의 엘리먼트더군요 문제의 테스트 케이스가 10번 시행되고 러닝타임과 메모리를 판독하여 아웃풋을 비교하여 결과를 알려주는 과제였습니다 감사합니당 해결이 되었어용

[네푸네푸~]

(제대로 하셨다고는 하나, 혹시나 잘 못 이해하셨을까봐 말씀 하신 부분의 정정을 하면요)

"N범위 내의 임의의 값을 넣어준다" -> "그 뒤로 N개의 입력이 들어 온다"
"첫번째에는 몇개를 출력할지를 입력하는거고 " -> "첫번째에는 몇개를 입력 받을지를 <입력>받는것이고 "

N의 범위는, 이후의 입력 줄의 갯수가 1~30000개 라는 의미니지, 그 다음 수가 그 범위 안이라는 것은 아닙니다.

<INPUT>
3
300003
300001
300002

<OUPUT>
300003
300002
300001

도 가능합니다.

요새 IT 기업의 온라인 사전 면접 문제가 다 이런 방식으로 문제를 줍니다.
그래서 이런 문제 방식은 꼭 제대로 아셔야 할 것 같네요. (몇 번 하시다 보면 자연스레 아시게 될 것 같긴하지만...)

[서련앓이]

처음 보자마자 뇌정지가 쎄게 와서 고생했네용 상세하게 알려주셔서ㅠ 매우 감사합니당