[코이] 줄 세우기(2004)

문제 링크

https://codeup.kr/problem.php?id=4502 <-- CodeUp

 

목차

1. Native한 구현( AC )

2. vector 심화 ( AC )

 

Native한 구현

솔직히 주어지는 수의 범위가 크지 않아서 O(2n^2) 을 돌려도 시간초과가 안나서 stack을 이용해 직접 구현을 해 보았으나...이렇게 노가다 하라고 낸 문제는 아닐테니  신들의 세계? 에서 사용하는 방법으로 풀어보자. 그리고 대회 나가서 코드를 노가다로 짜고 있으면 시간이 부족하니 더 짧고 효율적이게 짜는 방법을 알기 위함이기도 하다. 그래도 일단! stack으로 짠 코드는 다음과 같다.

void solve()
{
  for(int i=1; i<=n; i++)
    if(S.empty()) S.push(i);
    else
      if(d[i] == 0) S.push(i);
      else
      {
        for(int j=1; j<=d[i]; j++)
        {
          St.push(S.top());
          S.pop();
        }
        S.push(i);

        while(!St.empty())
        {
          S.push(St.top());
          St.pop();
        }
      }
}

무지성 코드 복붙을 막기 위한? 중요 코드만 올려놓기!!

 

vector 심화

std::vector를 이용한 풀이를 알아보자! vector를 iterator 로 선언하면 다음과 같은 기능을 사용할 수 있다.

find : vector 안에서 원하는 수의 위치를 찾을 수 있는 기능

erase : vector 안에서 원하는 수를 지울 수 있는 기능

insert : vector 안에서 원하는 위치에 수를 넣을 수 있는 기능

( 링크 타고 들어가면 reference를 볼 수 있음!! )

 

이 기능을 이용해서 코드를 한번 짜 보자. 접근하는 방식은 찾은 위치 찾고 위치 저장해 놓은 다음에 vector에서 해당 수를 지우고 저장된 위치에서 t만큼 뺀 값을 i를 넣는 형식이다. 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

typedef vector<int>::iterator it;

int n, t;

int main()
{
  scanf("%d", &n);
  vector<int> V(n+1);
  for(int i=1; i<=n; i++)
    V[i] = i;
  for(int i=1; i<=n; i++)
  {
    scanf("%d", &t);
    it f = find(V.begin(), V.end(), i);
    it a = f;

    a -= t;
    V.erase(f);
    V.insert(a, i);
  }

  for(int i=1; i<=n; i++)
    printf("%d ", V[i]);

  return 0;
}

v(n+1)은 v라는 이름의 vector에 크기를 n+1로 정한다는 뜻 입니다.

 

이렇게 stack으로 노가다(?)를 돌리지 않고도 vector를 이용해 빠르고 정확하게 코드를 짤 수 있습니다!.