백준: Class 2 ② - 4949, 10814, 10828, 10989, 15829, 18111

</br> 클래스 2 계속
</br>

4949: 균형잡힌 세상

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

    while( 1 ){
        string s;
        getline(cin, s);
        if( s == "." ) break;
        stack<int> st;
        int i = 0;
        for( ; i < s.size(); i++){
            if( s[i] == '(' ) st.push(0);
            else if( s[i] == '[' ) st.push(1);
            if( s[i] == ')' ){
                if( st.size() && st.top() == 0 ) st.pop();
                else break;
            }
            if( s[i] == ']' ){
                if( st.size() && st.top() == 1 ) st.pop();
                else break;
            }
        }
        if( i != s.size() || st.size() ) cout << "no\n";
        else cout << "yes\n";
    }

문제 번호도 마음에 드네 기본적인 스택 문제다
스택이 비었는데 .top()이나 .pop() 하지 않게 꼭 사이즈 확인하고 하기
</br>

10814: 나이순 정렬

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

stable_sort(v.begin(), v.end(), cmp);

stable_sort()는 처음 써 봤다 오~~
원래 sort() 함수는 유저 지정 함수 cmp에서 하나 하나 다 안 정해 주면 다른 거는 원래 있던 순서가 아닌 뒤죽박죽이 될 수 있다.

ex) (7, a), (7, b)를 앞의 숫자로 비교해서 sort()로 정렬
결과 -> (7, a), (7, b) 일 수도 있고     ... 1
        (7, b), (7, a)가 될 수도 있다   ... 2

이 때 stable_sort()를 사용하면 1번 결과로, 원래 있던 순서로 된다.
</br>

10828: 스택

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

    int now = 0;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if( s == "push" ){
            int a;
            cin >> a;
            st[now++] = a;
        }
        else if( s == "top" ){
            if( now > 0 ) cout << st[now-1] << '\n';
            else cout << -1 << '\n';
        }
        else if( s == "size" ){
            cout << now << '\n';
        }
        else if( s == "empty" ){
            if( now == 0 ) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else if( s == "pop" ){
            if( now > 0 ){
                cout << st[now-1] << '\n';
                now--;
            }
            else cout << -1 << '\n';
        }
    }

그냥 스택 쓰는 건 얌체 같아서 배열로 해 봤다
</br>

10989: 수 정렬하기 3

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

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        nums[a]++;
    }
    for(int i = 1; i <= 10000; i++){
        for(int j = 0; j < nums[i]; j++){
            cout << i << '\n';
        }
    }

메모리 제한이 있다
우짜냐 했는데 들어오는 수의 범위가 10000보다 작거나 같은 자연수래서 몇 갠지 세주는 식으로 했다.
</br>

15829: Hashing

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

백준 예제 1: abcde의 해시 값은 1 × 31^0 + 2 × 31^1 + 3 × 31^2 + 4 × 31^3 + 5 × 31^4 = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.

해싱 문제다~

    long long ans = 0, t = 1;
    for(int i = 0; i < n; i++){
        ans += (s[i]-'a'+1) * t;
        t *= 31;
        t %= 1234567891;
        ans %= 1234567891;
    }
    cout << ans % 1234567891 << endl;

오버플로우 안 나게 조심 조심하면 된다
</br>

18111: 마인크래프트

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

    map<int, int> mp;
    int hmax = -1, hmin = 64000001;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int a;
            cin >> a;
            hmax = max(hmax, a);
            hmin = min(hmin, a);
            if( mp.count(a) ) mp[a]++;
            else mp[a] = 1;
        }
    }

    vector< pair<int, int> > v(mp.begin(), mp.end());
    sort(v.begin(), v.end(), cmp);

    int ans = INT_MAX, height;
    for(int i = hmin; i <= hmax; i++){
        int bb = b;
        int j = 0;
        int t = 0;
        for( ; j < v.size(); j++){
            if( v[j].first > i ){
                int blocks = (v[j].first - i) * v[j].second;
                bb += blocks;
                t += 2 * blocks;
                if( t > ans ) break;
            }
            else{
                int blocks = (i - v[j].first) * v[j].second;
                bb -= blocks;
                t += blocks;
                if( t > ans || bb < 0 ) break;
            }
        }
        if( j != v.size() ) continue;
        if( t < ans ){
            ans = t;
            height = i;
        }
        else if( t == ans ) height = max(height, i);
    }

마인크래프트~~
문제를 보다 보니 굳이 이차원 배열 형태로 입력을 저장할 필요는 없어서 맵에다 높이와 블럭 수로 저장했다
현재 높이 최소값부터 최대값까지 전부 탐색해 본다.
</br>

---

클래스 2 성공~~
</br>