백준 2751 (정렬)

2751번: 수 정렬하기 2

핵심

• 가장 먼저 든 생각 : 범위가 커서 시간초과가 날거같다. → 저번에 쓴 https://ssin-estella.tistory.com/28 관련 방법 사용해야지
• 두번째로 든 생각 : (sort()는 안써본다는 고집)아니, 중간에 요소를 넣어야한다고?? 이거 연결리스트 써야겠는걸?
  → 이게 문제가 되었다..

일단 연결리스트로 중간삽입을 쉽게 하겠다는 발상은 좋았을지 모르지만, 1개만 기억하는 금붕어덕분에 1시간을 날렸다.

연결리스트는 중간삽입은 유용하지만 탐색에는 영.. 쥐약이다..

 

그래서 또 생각한게, 

• 부여되는 숫자를 인덱스로 가지는 벡터값을 +1씩 올려서 출력하는거지!
  ex) 1 6 4 2 1 이렇게 입력되면, V[1] = 2가 되어서 출력할 때는 벡터전체를 순회하면서 0이면 안들어온거고, 1이상이면 그만큼 반복해서 인덱스 값 (인덱스 값 = 들어온 값이니까) 을 출력하면 되겠다.

이 생각에는 문제를 읽지 않은 자의 오점이 허다하다.

• 입력되는 수는 절댓값이 1,000,000보다 작거나 같은 정수이다.
  → 음수출력도 고려해야하고, 기본적으로 메모리크기가 1,000,000이 되어야한다는 뜻
  
• 수는 중복되지 않는다.
  → .... 벡터값을 +1 할 필요가 없다는 뜻..
  

 

결국에는 sort()를 사용했다. 

코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int numLength = 0;  // 입력받을 숫자 총 개수

    int num = 0;        // 입력받을 숫자들

    cin >> numLength;

    vector<int> numV(numLength);

    for (int i = 0; i < numLength; i++)

    {

        cin >> numV[i];

    }

    sort(numV.begin(), numV.end());

    for (int i = 0; i < numLength; i++)

    {

        cout << numV[i] << '\n';

    }

}