챕터5-5. 정렬 | 문제풀이(2)

정렬을 적용한 문제풀이

# 가장 빈도가 높은 수를 출력하는 문제
- https://www.acmicpc.net/problem/11652

- 방법1) 정렬한 뒤 하나씩 카운트하기, if (a[i-1] != a[i]) 으로 서로 다른 수의 경계값을 인식함.
                시간복잡도 = 정렬(NlogN) + 카운트(N)
                정렬된 수에서 경계값을 인식시켜줄 때는 a[i] a[i+1]을 비교하고,
                제일 마지막 값은 경계값을 인식 못 하므로 꼭 따로 조건 추가해주기!
- 방법2) C++ STL의 map을 이용하여 개수를 카운트 하고, 가장 등장빈도가 높으면서 작은 수 인 것을  출력.
                시간복잡도 = 하나씩 카운트(N) + 비교(N이하)
* count 메소드를 사용할 수 없는 이유는 시간복잡도가 N*N이 되어버리기 때문.

# 오름차순으로 정렬했을 때 앞에서 K번째 수 찾는 문제
- https://www.acmicpc.net/problem/11004

- 퀵 정렬을 응용하는 문제이다.
   퀵 정렬은 피봇을 기준으로 왼쪽은 피봇보다 작은 값, 오른쪽은 피봇보다 큰 값 으로 나뉘어 지는데,
   이때 K번째가 두 부분 중 한쪽에만 속하게 되므로 K번째가 속하는 한쪽만 퀵 정렬을 진행하여
   전체를 정렬하지 않고도 이를 구해낼 수 있게 된다.
   직접 퀵소트를 구현할 수 있지만 그것은 너무 복잡하니
   부분 정렬 알고리즘인 STL의 nth_element()를 사용하면 이를 쉽게 구할 수 있다.
   이 함수는 특정 자리가 찾아질 때 까지만 정렬을 진행한다.
   * 이 방법으로 문제를 해결해도 ios::sync_~~ 이 스킬을 사용해야 시간초과가 안난다.
-  ios::sync_~~ 이 스킬을 사용하니 STL의 sort()로도 풀 수는 있다. 그런데 출제의도는 그게 아닐것이라 생각한다.

 

# 버블정렬의 정렬단계를 구하는 문제
- https://www.acmicpc.net/problem/1377

- 버블정렬의 코드를 그대로 이용하여 구하면 시간복잡도가 N^2가 되어버리는데 이는 최대 입력에 의해 
   250000000000 가 되어버려서 시간초과를 하게된다.
   따라서, 시간복잡도가 O(NlogN) 인 STL의 sort를 이용하여 정렬시키고, 버블 정렬의 특징을 이용해서 해결함.
   ex) 10  1  5  2  3 의 정렬된 결과는 아래와 같다.
          1  2  3  5  10
   버블정렬의 특성상 현재 위치보다 앞으로 이동한 수들은 한 단계에 한칸 이상을 움직일 수 없다.
   현재 위치보다 뒤로 이동한 수들은 한 stage에 끝까지 이동하기 때문에 그렇지 않지만 말이다.
   따라서 정렬한 뒤, 정렬전 자리에서 앞으로 이동한 수들이 몇index를 이동했는지 계산하여 이것의 최대값에 + 1을 해주면
   답을 구할 수 있다.
- 정렬되기전 index를 저장해줘야 하기 때문에 pair를 이용하며 정렬전 index는 입력과 동시에 저장한다.

@ 버블정렬로 예시가 정렬되는 과정

<stage1>
10 1 5 2 3

1 10 5 2 3

1 5 10 2 3

1 5 2 10 3

1 5 2 3 10

<stage2>
1 5 2 3 10
1 5 2 3 10

1 2 5 3 10

1 2 3 5 10

1 2 3 5 10

1 2 3 5 10

<stage3>

swap이 없어서 종료