20200503 프로그래머스 level 2 - 프린터

 프린트의 끝은 뭐랄까.

 허무함이었다.

 여태까지 효용성, 그중에서도 시간 초과의  덫에 너무 크게 데었었다.

 일단 성공한 코드를 보겠다.

 

int solution(vector priorities, int location)
{
     //답
     int answer = 0;
     //순위가 몇 개 있는지 확인
     int num[10][2] = { 0, };

     for (int i = 0; i < priorities.size(); i++)
     {
          //순위가 몇 개 있는지 전부 파악
          num[priorities[i]][1]++;
     }
     int max;
     for (int i = 9; i > 0; i--)
     {
          if (num[i][1] != 0)
          {
               max = i;
               break;
          }
     }
     //계속 돌리다가 조건에 맞으면 브레이크
     while (true)
     {
          int print;
          for (int i = 0; i < priorities.size(); i++)
          {
               if (priorities[i] == max)
               {
                    print = i;
                    break;
               }

          }

         //while문을 나가는 브레이크
          if (max == priorities[location] && print == location)
          {
               answer++;
               break;
          }
          while (print > -1)
          {
               if (print != 0)
               {
                    priorities.push_back(priorities[0]);
                    priorities.erase(priorities.begin());
                    print--;
                    location--;
                    if (location == -1)
                         location = priorities.size() - 1;
               }
               else
               {

                    priorities.erase(priorities.begin());
                    print--;
                    location--;
               }
          }
          num[max][1]--;

         //max가 0이 되었으면 다음 max를 찾는다.
          if (num[max][1] == 0)
          {
               for (int i = max - 1; i > 0; i--)
               {
                    if (num[i][1] != 0)
                    {
                         max = i;
                         break;
                    }
               }
          }
          answer++;
          }

     return answer;
}

어제보다 코드가 2배 가까이 늘어났다. 하지만 정답이다.

 로직은 간단하게 2차 배열을 사용해 순위 별로 몇 개씩 있는지 먼저 찾은 다음 가장 높은 순위별로 지우면서 그 앞에 있는 숫자들을 뒤로 돌려줬다. 그리고 앞에서부터 가장 높은 순위 중 가장 앞에 있는 숫자까지 제거해줬다.

 그것을 반복하다가 중간에 최댓값인 max가 지정된 값이고, location(location도 움직이는 만큼 함께 움직여줬다.)과 삭제해야 할 최댓값의 인덱스와 같으면 나오게 된다.

 시간 초과로 인해 수학적 접근을 의식한 덕분에 그냥 단순하게 지우고 앞에 것을 뒤로 돌리면 되는 간단한 문제를 4일에 걸쳐서 풀어야 했다.

 계속 백터를 erase 하고 push.back 하면 시간이 너무 오래 걸릴 거 같았기 때문이다. 지금 생각해보면 7천 분 넘게 푸셨고, 인덱스가 최대 100이라는 것을 감안했어야 했다고 생각한다.

 어쨌든 나의 괜한 걱정 때문에 이상한 접근을 수없이 시도했다. 아마 그것만 아니었다면 하루 3시간 안에 풀었을 것이다.

 다음부턴 가장 쉬운 방법부터 차근차근 올라가도록 해야겠다.