[Inflearn] 석차 구하기(brute force)

#. 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. N이 최대 100이므로 완전 탐색으로 충분히 풀어낼 수 있을 것 같다.

     우선 무식하게 가능한 모든 경우의 수를 탐색해보자.

     90 85 92 95 90 이 입력되었다고 했을 때, 

     최대 N이 100이니까 이중 반복문으로 풀어내도 N^2 = 10000, 1초 안에 충분하모로..  

     각 점수는 자신을 제외한 모든 다른 점수와 비교를 하게 된다. 

     자신보다 큰 점수가 있다면 등수가 밀려날 것이고 같은 점수가 있다면 같은 등수를 갖게 될 것이다.

    

     rank = 1

     (자신의 index는 continue)

     90 -> [92(rank++), 95(rank++)] 보다 작으므로  3등이 된다.

     85 -> [90, 92, 95, 90] 보다 작으므로 5등이 된다.

     92 -> [95] 보다 작으므로 2등이 된다. 

     95 -> 자신보다 큰 수가 없으므로 1등이 된다.

     90 -> 92, 95 보다 작으므로 3등이 된다.  

     이 로직을 코드로 구현해보자!

    

#. 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>   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, j, rank = 1;          scanf("%d", &n);     std::vector<int> v(n);          for (i = 0; i < n; i++)         scanf("%d", &v[i]);       for (i = 0; i < n; i++)     {         rank = 1;           for (j = 0; j < n; j++)         {             if (j == i)                 continue;               if (v[i] < v[j])                 rank++;         }           printf("%d ", rank);     }       puts("");       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

#include<stdio.h>   int main(){     int i, j, a[200], b[200], n;       scanf("%d", &n);       for(i=1; i<=n; i++){         scanf("%d", &a[i]);           b[i]=1;     }       for(i=1; i<=n; i++){         for(j=1; j<=n; j++){             if(a[j]>a[i])                 b[i]++;         }     }       for(i=1; i<=n; i++)         printf("%d ", b[i]);          return 0; }

cs

rank를 저장할 배열 사용유무차이를 제외하고는 유사하게 해결하였다.

사실 최대 N이 워낙에 작은지라 어떻게 짜도 비스무리 할 것 같다.

다만 나는 불필요한 if(j == i) continue; 연산이 들어가서.. 이런 부분은 참고해야겠다. 

continue 밑에 연산이 비싸다면 뭐 상관없긴 하다만ㅋ..ㅋ

#. Result

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

5

90 85 92 95 90

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

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

3 5 2 1 3

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