[Inflearn] 마라톤

#. 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 the problem

  2. Redefine the problem + abstract

     - 앞으로 자신이 얻을 수 있는 최선의 등수 구하기

     - 실력이 같다면 앞에 달리는 선수를 앞지를 수 없음

  3. Create a 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. 이 문제도 앞 문제처리 brute force 문제 같지만 최대 N이 10,000 이므로.. 

     이중 반복문 사용 시 N^2 = 100,000,000 아슬아슬하게 딱 될것 같다.

   

     2 8 10 7 1 9 4 15 가 입력되었다고 했을 때,

     최선의 등수를 구하면 되므로 그냥 첫 번째 index 부터 접근하면서 비교하면 될 듯 하다.

     2 는 이대로만 가면 1등일테고,

     8 은 2보다 실력이 높으니 1등,

     10 도 2, 8 보다 실력이 높으니 1등

     7 은 8, 10 보다는 실력이 낮으니 3등

     1 은 2, 8, 19, 7 보다 실력이 낮으니 5등

     9 는 10 보다 실력이 낮으니 2등

     ...

     이런 로직으로 짜면 될 것 같다.

     이제 코드로 옮겨보자!

#. 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

#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]);       printf("1 ");       for (i = 1; i < n; i++)     {         rank = 1;           for (j = 0; j < i; j++)         {             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 26 27 28

#include<stdio.h> #include<vector> #include<algorithm>   using namespace std;   int main(){     int i, j, n, cnt=0;       scanf("%d ", &n);     vector<int> a(n+1);       for(i=1; i<=n; i++)         scanf("%d", &a[i]);          printf("1 ");       for(i=2; i<=n; i++){         cnt=0;           for(j=i-1; j>=1; j--)             if(a[j]>=a[i]) cnt++;                  printf("%d ", cnt+1);     }       return 0; }

cs

최대 N이 커진다면 앞에 자신보다 큰 수를 O(nlogn)만에 찾을 수 있는 병합정렬을 사용하여 이 문제를 해결해야 할 것이다.

강사님과 거의 흡사하게 짠 것 같다 ㅋ..ㅋ

차근차근 공부해보고 병합정렬로도 이 문제를 해결해봐야지!

#. Result

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

8

2 8 10 7 1 9 4 15

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

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

1 1 1 3 5 2 5 1

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