[1w] 기본 자료구조

STL 기본 컨테이너

queue, stack

reference
백준 17615
//아이디어

//제가 푼 코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int N, result=2100000000, redCnt, blueCnt, nowCnt;
stack<int> redS, blueS;  //빨 우, 파 우
queue<int> redQ, blueQ;  //빨 좌, 파 좌
int main(){
    string input, s;
    cin>>N>>s;
    s=" "+s;
    //input
    for(int i=1;i<=N;i++){
        if(s[i]=='R') {
            redCnt++;
            redS.push(i);
            redQ.push(i);
        }
        else {
            blueCnt++;
            blueS.push(i);
            blueQ.push(i);
        }
    }   
    //case 1 빨, 좌
    input=s;
    nowCnt=0;
    for(int i=1;i<=redCnt;i++){
        if(input[i]!='R') {
            nowCnt++;
            int changeIndex=redQ.front();
            redQ.pop();
            input[changeIndex]='B';
        }
        else redQ.pop();
    }
    if(result>nowCnt) result=nowCnt;
    //cout<<nowCnt<<"\n";
    //case 2 빨, 우
    input=s;
    nowCnt=0;
    for(int i=N;i>(N-redCnt);i--){
        if(input[i]!='R') {
            nowCnt++;
            int changeIndex=redS.top();
            redS.pop();
            input[changeIndex]='B';
        }
        else redS.pop();
    }
    if(result>nowCnt) result=nowCnt;
    //cout<<nowCnt<<"\n";
    //case 3 파, 좌
    input=s;
    nowCnt=0;
    for(int i=1;i<=blueCnt;i++){
        if(input[i]!='B'){
            nowCnt++;
            int changeIndex=blueQ.front();
            blueQ.pop();
            input[changeIndex]='R';
        }
        else blueQ.pop();
    }
    if(result>nowCnt) result=nowCnt;
    //cout<<nowCnt<<"\n";
    //case 4 파, 우
    input=s;
    nowCnt=0;
    for(int i=N;i>(N-blueCnt);i--){
        if(input[i]!='B'){
            nowCnt++;
            int changeIndex=blueS.top();
            blueS.pop();
            input[changeIndex]='R';
        }
        else blueS.pop();
    }
    if(result>nowCnt) result=nowCnt;
    //cout<<nowCnt<<"\n";
    cout<<result;
    return 0;
}

+@ priority queue(힙)
reference
백준 1927
//아이디어

//제가 푼 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> pQ;
    int N, x;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>x;
        if(x==0){
            if(pQ.empty()) {
                answer.push_back(0);
                continue;
            }
            else{
                answer.push_back(pQ.top());
                pQ.pop();
                continue;
            }
        }
        pQ.push(x);
    }
    for(int i=0;i<answer.size();i++) cout<<answer[i]<<"\n";
    return 0;
}

vector

reference
백준 1138
//아이디어

//제가 푼 코드

#include <iostream>
#include <vector>
using namespace std;
int N;
int main(){
    cin>>N;
    vector<int> line(N+1);
    vector<int> input(N+1);
    for(int i=1;i<=N;i++){
        int n; cin>>n;
        input[i]=n;
    }
    for(int i=N;i>=1;i--){
        line.insert(line.begin()+input[i]+1, i);
    }
    for(int i=1;i<=N;i++) cout<<line[i]<<" ";
}

+@ pair
reference

map

reference
백준 20922
//아이디어

//제가 푼 코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int start = 0, endP = 0, result = 1;
map<int, int> iM;
int N, K;
int main() {
    cin >> N >> K;
    vector<int> iV(N);
    for (int i = 0; i < N; i++) {
        cin >> iV[i];
    }   
    iM[iV[0]]++;
    while (endP < N - 1) {
        endP++;
        iM[iV[endP]]++;
        while (iM[iV[endP]] > K) {
            iM[iV[start]]--;
            start++;
        }
        int len = endP - start + 1;
        if (len > result) result = len;
    } 
    cout << result;
    return 0;
}

set VS unordered set

reference
백준 22233
//아이디어

//제가 푼 코드

#include <iostream>
#include <unordered_set>
#include <vector>
#include <sstream>
#include <algorithm>
#include <string>
using namespace std;
int N,M;
vector<int> result;
unordered_set<string> words;
int main(){
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<N;i++){
        string s; cin>>s;
        words.insert(s);
    }
    for(int i=0;i<M;i++){
        string s; cin>>s;
        stringstream ss(s);
        vector<string> sV;
        string token;
        while(getline(ss, token, ',')){
            sV.push_back(token);
        }
        for(int j=0;j<sV.size();j++){
            string s2=sV[j];
            if(words.find(s2)!=words.end()){
                N--;
                words.erase(s2);
            }
        }
        result.push_back(N);
    }
    for(int i=0;i<result.size();i++){
        cout<<result[i]<<"\n";
    }
    return 0;
}