[코드포스 Practice17] B. Bus of Characters

 

문제 읽고 뭐지?? 싶었는데 푸는 건 쉬웠다.

그냥 배열로 받은 다음 정렬해주고

내향적인 사람 들어오면 순서대로 배정하고 그 위치를 다시 저장한다.

다음으로 외향인 들어오면 내향인 자리 옆에 앉게했다.

 

내향인 여러사람 들어오면 1->2->3  순으로 자리를 내어주면

여기서 3이 가장 큰 자리 일테니 외향인은 3부터 줬다. 

 

그래서 큐랑 스택을 이용했음

 

정렬한 다음 정렬 순서대로 큐에 넣어주고 내향인이 들어오면 queue.pop()을 해준다.

그리고 내향인 자리는 stack에 넣어주고 외향인 오면 pop..

 

아, 크기 순으로 정렬하면서 인덱스도 함께 저장했다.

요즘 느끼는 건데 인덱스 같이 저장해야 하는 경우 많은듯.

그래서 pair 만들어서 first에 크기 저장하고 second에 인덱스 저장한 다음 first만 정렬하게 함수 사용했다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
 
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.first < b.first); 
} 
 
int main() {
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> v(n);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &v[i].first);
        v[i].second = i;
    }
    
    sort(v.begin(), v.end(), sortbysec);
    
    queue<int> introvert;
    stack<int> extrovert;
    
    for (int i = 0; i < n; i++)
        introvert.push(v[i].second + 1);
    
    for (int i = 0; i < 2*n; i++)
    {
        int tmp;
        scanf("%1d", &tmp);
        if (tmp == 0)
        {
            cout << introvert.front() << " ";
            extrovert.push(introvert.front());
            introvert.pop();
        }
        else
        {
            cout << extrovert.top() << " ";
            extrovert.pop();
        }
    }
    
    return 0;
}

 

끝~

 

---

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
 
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.first < b.first); 
} 
 
int main() {
    int n;
    scanf("%d", &n);
    set<pair<int, int>> introvert, extrovert;
    
    for (int i = 1; i <= n; i++)
    {
        int input;
        scanf("%d", &input);
        introvert.emplace(input, i);
    }
    
    for (int i = 0; i < 2*n; i++)
    {
        int tmp;
        scanf("%1d", &tmp);
        
        if (tmp == 0)
        {
            cout << introvert.begin()->second << " ";
            extrovert.insert(*introvert.begin());
            introvert.erase(introvert.begin());
        }
        else
        {
            cout << extrovert.rbegin()->second << " ";
            extrovert.erase(--extrovert.end());
        }
    }
    
    return 0;
}

아 어차피 정렬해야 하는거 set으로 바로 집어넣었구나

난 set 싫음,, 어려워

하지만 익숙해져야지 컹

 

set-pair는 emplace로 값 집어넣고..

 

오.. begin() 저게 포인터 비스무리 한 걸로 이해하고 있는데 

pair의 요소 접근 할 때 -> 쓰는구나

 

아ㅋㅋㅋ 복잡하다!

저 begin rbegin end 저건 위처럼 값 가리키는 듯