[Inflearn] Special Sort(Google interview source)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

      - 음의 정수는 앞쪽에 양의 정수는 뒷쪽에

      - 양의 정수와 음의 정수의 순서에는 변함이 없도록

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 버블정렬 응용문제니까 버블정렬을 응용해보자.

     라고 하면 너무 꽁으로 푸는 것 같으니..

     인접한 두 수를 비교해서 음수는 왼쪽으로 밀어줘야하므로 버블정렬을 사용해서 풀어보자!

     선택정렬을 사용하게되면 입력된 양수, 음수 순서를 유지할 수 없다.

     

     먼저 음수와 양수는 분리가 되어야지만 또 입력된 순서에는 변함이 없어야 한다.

     그렇다면 대소 비교하기보다는 음수 or 양수를 판단해서 swap 해주면 될 것 같다.

     하나는 음수 다른 하나는 양수라면 곱해서 음수가 나오겠지?

     원하는 결과가 나오지 않아 디버깅을 해보니.. 역시나 생각이 짧았었다..

     곱해서 음수인 경우 swap 을 하게되면, 이미 -3 -2 2 로 정렬되어있는데 -3 2 -2 로 다시 정렬을 망쳐놓게 된다.

     결국 그냥 v[j] 는 양수이고 v[j+1] 이 음수인 경우 swap 하도록 구현하였다. (앞이 양수고 뒤가 음수면)

     1 2 3 -3 -2 5 6 -6 이 입력으로 주어졌을 때,

     자세한 과정은 생략하고..

     i = 0,

     1 2 -3 -2 3 5 -6 6

 

     i = 1,

     1 -3 -2 2 3 -6 5 6

     i = 2,

     -3 -2 1 2 -6 3 5 6

     i = 3

     -3 -2 1 -6 2 3 5 6

   

     i = 4      

     -3 -2 -6 1 2 3 5 6

 

    이렇게 정렬이 완료되었다..!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, j, tmp;       scanf("%d", &n);     vector<int> v(n);       for (i = 0; i < n; i++)         scanf("%d", &v[i]);          for (i = 0; i < n-1; i++)     {         for (j = 0; j < n - i - 1; j++)         {             if (v[j] > 0 && v[j+1] < 0)             {                 tmp = v[j];                 v[j] = v[j+1];                 v[j+1] = tmp;             }         }     }       for (i = 0; i < n; i++)         printf("%d ", v[i]);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<stdio.h>   int main() {     int a[101], n, tmp, min, i, j;       scanf("%d", &n);       for(i=0; i<n; i++)         scanf("%d", &a[i]);          for(i=0; i<n-1; i++){         for(j=0; j<n-i-1; j++){             if(a[j]>0 && a[j+1]<0){                 tmp=a[j];                 a[j]=a[j+1];                 a[j+1]=tmp;             }         }     }       for(i=0; i<n; i++)         printf("%d ", a[i]);          return 0; }     Colored by Color Scripter

cs

이 문제의 핵심은 버블정렬 시 앞 뒤 숫자의 대소비교대신,

앞이 양수이고 뒤가 음수이면 swap 해주는거라 버블의 과정만 잘 이해하면 어렵지 않을 것이다!

#. Result

  - Input --------------------------------------------------------

8

1 2 3 -3 -2 5 6 -6

------------------------------------------------------------------

  - Output --------------------------------------------------------

-3 -2 -6 1 2 3 5 6

------------------------------------------------------------------