프로그래밍

https://programmers.co.kr/learn/courses/30/lessons/81303

[난이도] level3
[유형] set

[풀이]
행의 최대 수가 100만이기 때문에 단순히 vector를 이용하면 삽입,삭제시 비용이 많이 들기 때문에
다른 자료구조를 이용해야 합니다. 물론 커서를 움직일 때는 배열의 경우 특정 index에 O(1)로 접근이 가능하기 때문에
유리하지만 문제 조건에서 모든 cmd의 커서를 움직이는 총 횟수의 합이 1000000 이하이기 때문에 삽입/삭제 연산을 효율적으로
하는 것이 더 중요합니다.

vector는 특정한 위치에 삽입,삭제시 그곳을 기준으로 모든 원소를 움직여 빈공간이 생기지 않도록 하기 때문에 삽입/삭제시 불리합니다.

그렇다고 stl list를 이용하면 복구 연산시 복구 되어야할 위치를 찾기가 어렵습니다.

그래서 set을 이용하였습니다. set은 balanced tree 형태로 되어있어 O(logN)으로 삽입/삭제가 가능하기 때문입니다.
커서의 이동도 iterator를 유지하면 위,아래로 자유롭게 할 수 있습니다.

삭제시에는 set에서 현재 iterator 위치의 원소를 삭제하고, 그 원소를 stack에 넣어주고 복원시에 꺼내서 set에 insert 해주기만 하면
자동으로 복구가 됩니다.
주의할 점이 삭제시 반환된 iterator가 end()인 경우(마지막 원소를 삭제한 경우) iterator를 한 칸 앞으로 (-- 연산) 옮겨주어야 합니다.
왜냐하면 end()는 마지막 원소의 한 칸 뒤를 가르키기 때문에 커서를 위로 올리는 연산시 (-- 연산) 한칸 덜 올라가게 되기 때문입니다.

#include <string>
#include <vector>
#include <set>
#include <stack>
using namespace std;
stack<int> st;
set<int> a;
string solution(int n, int k, vector<string> cmd) {
    string ans;
    for(int i=0;i<n;i++) {
        a.insert(i);
        ans+='X';
    }
    auto it = a.begin();
    while(k--) it++; 
    for(auto c : cmd){
        char q = c[0];
        int num;
        if(c.size()>1) num = stoi(c.substr(2));

        if(q=='U') while(num--) it--;
        else if(q=='D') while(num--) it++;
        else if(q=='Z') {
            a.insert(st.top()); st.pop();
        }
        else {
            st.push(*it);
            it = a.erase(it);
            if(it==a.end()) it--;
        }
    }
    for(auto v : a) ans[v]='O';
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/표_편집.cpp

https://www.acmicpc.net/problem/1764

[난이도] Silver4
[유형] Set

[풀이]
Set,정렬

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
import kotlin.collections.HashSet
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N,M) = readLine().split(' ').map{it.toInt()}

    var st = HashSet<String>()
    var arr = mutableListOf<String>()
    while(N-->0) st.add(readLine())
    while(M-->0){
        var s = readLine()
        if(st.contains(s)) arr.add(s)
    }
    arr.sort()
    println(arr.size)
    for(a in arr) println(a)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver4/1764.cpp