백준: Silver4① - 1015, 1021, 1026, 1049

</br> 실버 4 문제들~
</br>

1015: 수열 정렬

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

처음에 문제가 이해 안 됐었는데, 쉽게 말하면 입력된 수열 A의 각 원소가 A에서 몇 번째로 큰지가 출력 수열 P다.

    sort(v2.begin(), v2.end());

    map<int, int> m, mm;
    for(int i = 0; i < n; i++){
        auto ret = m.insert(pair<int, int>(v2[i], i));
        if( ret.second == false ){
            auto ret = m.insert(pair<int, int>(v2[i], 1));
            if( ret.second == false ){
                mm[v2[i]]++;
            }
        }
    }

    for(int i = 0; i < n; i++){
        if( mm.find(v[i]) != mm.end() ){
            cout << m[v[i]]++ << ' ';
            mm[v[i]]--;
            if( mm[v[i]] < 0 ){
                mm.erase(v[i]);
                m.erase(v[i]);
            }
        }
        else{
            cout << m[v[i]] << ' ';
            m.erase(v[i]);
        }
    }

A에 같은 게 있다면 사전 순으로 작은 것을 우선해서 출력해야 한다.
…는 조건에 집착해서 무지성으로 맵으로 풀었는데 너무 복잡한 것 같다.

이건 다른 사람들 코드 찾아 봐야겠다.
</br>

1021: 회전하는 큐

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

큐를 좌우로 이동시키거나 뽑아내기 완전 덱이랑 똑같음!!

    deque<int> dq;

    for(int i = 1; i < n+1; i++){
        dq.push_back(i);
    }

    int cnt = 0;

    for(int i = 0; i < k; i++){
        int a;
        cin >> a;
        for(int j = 0; j < n; j++){
            if( dq[j] == a ){
                if( n == 1 ){
                    break;
                }
                if( j == 0 ){
                    dq.pop_front();
                }
                else if( j == n-1 ){
                    cnt++;
                    dq.pop_back();
                }
                else if( j < n - j ){
                    cnt += j;
                    for(int k = 0; k < j; k++){
                        dq.push_back(dq.front());
                        dq.pop_front();
                    }
                    dq.pop_front();
                }
                else{
                    cnt += n - j;
                    for(int k = 0; k < n - j - 1; k++){
                        dq.push_front(dq.back());
                        dq.pop_back();
                    }
                    dq.pop_back();
                }
                n--;
                break;
            }
        }
    }

덱에서 원소를 찾고, 좌우 중에 가까운 쪽을 골라 넘겨 주고 뽑아낸다.

덱에 원소가 하나 남았다면 연산 횟수 더할 것 없이 바로 걔를 뽑아낸다.
맨 앞에서 발견해도 연산 횟수를 더하지 않고 바로 빼준다.
맨 뒤에서 발견하면 왼쪽으로 옮겨 줘야 하니 한 번 더하고 빼준다.
왼쪽에 가까운 곳에서 발견하면 앞에 있는 원소들을 다 뒤로 옮겨 주고 빼낸다. 연산 횟수는 j번 오른쪽에 가까운 곳에서 발견하면 뒤에 있는 원소들을 다 앞으로 옮겨 주고 빼낸다. 연산 횟수는 n-j번
</br>

1026: 보물

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

각 배열의 같은 인덱스 원소끼리 곱해서 가장 작은 합 만들기
A의 순서를 바꿀 수 있다.

    priority_queue<int, vector<int>, greater<int>> a;
    priority_queue<int, vector<int>, less<int>> b;
    int n;

    cin >> n;
    for(int i = 0; i < n; i++){
        int k;
        cin >> k;
        a.push(k);
    }
    for(int i = 0; i < n; i++){
        int k;
        cin >> k;
        b.push(k);
    }

    int s = 0;
    while(a.size()){
        s += a.top() * b.top();
        a.pop(); b.pop();
    }

B는 재배열하면 안 된다는데 왜 저런 의미없는 조건이… 어차피 B의 가장 큰 수를 A의 가장 작은 수와 곱해야 합이 작아지므로,

그냥 A 배열은 오름차순 우선순위 큐에, B 배열은 내림차순 우선순위 큐에 넣고 곱해 주면 되겠다.
</br>

1049: 기타줄

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

기타줄 싸게 사기

    int min6 = 1001, min1 = 1001;
    for(int i = 0; i < m; i++){
        int m6, m1;
        cin >> m6 >> m1;
        min6 = min(min6, m6);
        min1 = min(min1, m1);
    }
    if( min6 > min1*6 ) cout << n*min1 << endl;
    else{
        if( min6 < (n%6)*min1 ) cout << (n/6 + 1) * min6 << endl;
        else cout << (n/6) * min6 + (n%6)*min1 << endl;
    }

무슨 브랜드가 여러 개 나오고 하는데 그런 거 상관없고 6줄 세트와 1줄 각각 제일 싼 가격만 저장해 둔다.

만~에 하나 6줄 세트보다 낱개로 6줄 사는 게 더 쌀까 봐? 중간에 if문 한 번 넣어서 체크하고,
세트로 살 수 있을 때까지 사고, 남은 줄들이 세트로 사서 줄은 좀 남아도 싸게 치는 지 아니면 낱개로 딱 맞춰 사는 게 싸게 치는 지를 확인하면 된다.
</br>

---

아직은 막 풀어도 바로 풀리긴 한다…
</br>