[Altu-Bitu/알고리즘] 1주차 정렬, 맵, 셋 문제풀이

03.13(금)-03.15(일) 기록

BOJ 19636번: 요요 시뮬레이션

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long w0, I0, T;
    cin >> w0 >> I0 >> T;

    long long days, I, A;
    cin >> days >> I >> A;

    long long D=I0;
    long long weight = w0;
    string result=" ";
    bool danger = false;


    for (int i=0; i<days; i++) {
        weight += I-(D + A);
        if (weight <=0 ) {
            cout << "Danger Diet\n";
            danger = true;
            break;
        }
    }
    if (!danger) cout << weight << " " << D << "\n";

    weight = w0;
    D = I0;
    for (int i=0; i<days; i++) {
        weight += I-(D+A);
        if (weight <=0 || D <=0) {
            cout << "Danger Diet\n";
            return 0;
        }

        if (abs(I-(D+A)) > T) {
            D += (long long)floor((I-(D+A))/2.0);
        }

        if (D<=0) {
            cout << "Danger Diet";
            return 0;
        }
    }

   if (I0-D > 0) result = "YOYO";
   else result = "NO";
    cout << weight << " " << D << " " << result;
}

진짜 처음에 엄청 헤맸다. 근데 사실 진짜 쓸데없이 헤맸다. 이번주가 정렬, 맵, 셋이라 무조건 이 셋 중 하나의 개념을 사용해야한다고 생각했는데...?

도대체 왜? ㅎㅎ 그냥 주어진 조건, 수학적 식 잘 사용해서 구현하는 문제였다.

주의할 부분은 floor() 사용해주는 부분. 내림 처리하는 것인 것같고... 어디서 D, 즉 일일 활동 대사량(?) 단어가 정확히 기억이 안나지만, 그걸 매일 업데이트하는 시점을 주의해서 해주어야한다는 부분이라고 생각한다.

시간 제한이 막 빡세지는 않아서 그냥 반복문 같은 걸 두 번 돌려서 기초 대사량 변화 있을 때, 없을 때의 결과를 출력했고.

하다보니 많이 틀리고 오류냈던 부분은 Danger Diet를 두 케이스에서 어떤 시점에 어떻게 판별할지 부분이었던 것 같다.

=> 처음에 잘못시작해서 아예 지우고 다시 시작하는게 더 빨랐다.

---

BOJ 11478번: 서로 다른 부분 문자열의 개수

#include <iostream>
#include <set>
using namespace std;

int main() {
    string s;
    cin >> s;

    set<string> arr;
    for (int i=1; i<=s.length(); i++) {
        for (int j=0; j+i<=s.length(); j++) {
            string tmp = s.substr(j,i);
            arr.insert(tmp);
        }
    }

    cout << arr.size();
}

이전에 봤었는데 못 풀었던 문제라 이번에 다시 봤을 때 풀 수 있을까? 싶긴했다. 일단 문자열 사용하는 문제였고, 문자열 조작하는건 여전히 까다로운 것 같다.

부분 문자열을 만들고, 그 중 중복되지 않는 부분 문자열의 갯수가 몇 개인지 세는 문제였다. 보자마자 생각한 것은 substr() 써서 부분 문자열 만드는 것과, 그러려면 반복문 써야하는데 시간 제한 확인해봐야겠다? 정도였다.

일단은 substr() 써서 부분 문자열 만들어서 set에 저장해버리면 알아서 중복된 문자열들은 새로 저장되지 않을테니 후에 set의 크기만 출력해주면 될거라고 생각했다.

그러면 1차로 멈췄던것은 시간제한이 1초였는데 substr() 만들 때 이중 반복문을 써야해서 였다. 겉에서는 문자 길이 반복 돌리고, 그 안에서 문자열 처음~마지막 인덱스까지 돌면서 부분 문자열 만드는 방식을 생각해서 반복문을 무조건 2번 사용해야했다. 다행인건 입력제한인 문자열의 길이가 1000이라 n=1000인걸 고려하면 O(n^2)이어도 시간제한 1초는 넘기지 않을 거라 그냥 사용했다.

이후는 그래도 나름 쉽게쉽게 풀어나갔던 것 같다. substr() 사용법 까먹어서 찾아서 다시 정리했다.

substr(pos, count)

문자열.substr()으로 사용하게 되며 pos번째 문자부터 count 길이만큼의 문자열을 리턴해준다.

만약, 인자로 전달된 부분 문자열의 길이가 문자열보다 길면, 그 이상을 반환하지는 않고 문자열의 끝까지만 리턴해준다.

만약 count로 npos를 전달한다면, 자동으로 pos부터 원래 문자열의 끝까지 리턴.

막상 IDE에서 돌렸을 때 생각처럼 결과가 안나와서 어떻게 할까하다가 만든 substr()을 바로 셋에 저장하지 않고 tmp라는 변수에 저장하도록해서 디버깅을 해봤다. CLion IDE에서는 따로 조작하지 않아도 변수에 어떤 값 들어가는지는 잘 보여서 이렇게 하면 확인이 쉬웠다.

처음에 잘못했던 부분은 pos는 굳이 설정+업데이트 하지 않고 안쪽 반복문인 j를 사용해야한다는점. 이게 부분 문자열로 사용됐다고 그걸 넘어가는게 아니라 그냥 j의 업데이트를 따라가면 됐었다.

그리고 마지막에 틀린건, 이중 반복문 둘 다 조건식에서 s.length() 미만이 아니라 이하로 설정해줘야하는 부분이었다. 겉의 반복문인 i가 1에서부터 돌기 때문에 그것도 고려해줘야했다.

---

BOJ 1431번: 시리얼 번호

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int addNum(string s) {
    int sum = 0;

    for (char i : s) {
        if (isdigit(i)) sum+= i-'0';
    }

    return sum;
}
bool comp (string s1, string s2) {

    if (s1.length() == s2.length()) {
        if (addNum(s1) == addNum(s2)) {
            return s1 < s2;
        }
        return addNum(s1) < addNum(s2);
    }

    return s1.length() < s2.length();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<string> serial(n);
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;

        serial[i] = s;
    }

    sort(serial.begin(), serial.end(),comp);

    for (string s : serial) cout << s << "\n";
}

이거는 그래도 문제 보자마자 sort()에서 comp() 잘 정의해서 정렬해주면 되는거라고 생각해서 풀 수 있었다. 앞에서 한 번 써본거라 사용했는데 차이는 문자열에 들어있는 숫자의 경우 합을 비교해야하는거라 그 합을 리턴해주는 함수를 하나 추가해서 사용했다는 것 정도. comp() 정의하는 것을 배우고 다시 사용하면서 익힐 수 있는 문제여서 좋았다. false 값을 받을 때 스왑하게 되는 것을 주의.

---

BOJ 9375번: 패션왕 신해빈

#include <iostream>
#include <map>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        map<string,int> clothes;
        set<string> types;
        for (int i=0; i<n; i++) {
            string s, type;
            cin >> s >> type;

            types.insert(type);
            auto it = clothes.find(type);
            if (it != clothes.end()) {
                clothes[type] = clothes.find(type)->second +1;
            }
            else clothes[type] = 1;

        }
        int sum = 1;
        map<string, int>::iterator iter;
        for (iter=clothes.begin(); iter !=clothes.end(); ++iter) {
            sum *= iter->second +1;
        }

        cout << sum-1 << "\n";
    }
}

의외로 수학적인 능력? 확통 생각을 많이 했던 문제. 아니 애초에 그냥 확통 생각하고 풀면 더 쉬웠을텐데 처음에 바보같은 짓을 했다.

근데 제대로 푼 것 같은데 계속 25%에서 틀렸다고 뜨길래 왠지 한참 봤는데... 출력할 때 \n 엔터를 빼먹었다. 왜 이 생각을 못했을까.

풀이는 그냥... 옷 가짓수 다 곱하는 확통 문제인데, 이제 알몸이면 안되니까 각 옷 종류 곱한 것에서 하나를 빼는 그런 식이다.

이전에 맵 배웠으니까, 옷 종류(headgear)를 기준으로 해당 옷 종류에 가짓수가 몇 개 있는지를 맵으로 저장해두면 되는 식이었다.

반복자를 이번에 또 다시 사용해봤는데, 이게 처음에 낯설어서 어렵지 몇 번 써보면 새삼 편한 것 같다.

---

BOJ 1946번: 신입사원

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> score(n+1);

        for (int i=0; i<n; i++) {
            int s1, s2;
            cin >> s1 >> s2;

            score[s1] = s2;
        }

        int cnt = n;
        for (int i=n; i>1; i--) {
            for (int j=i-1; j>=1; j--) {
                if (score[i] > score[j]) {
                    cnt--;
                    break;
                }
            }
        }

        cout << cnt << "\n";
    }
}

전에 풀었던 추월 문제를 생각하면서 짜서 의외로 간단하게 풀었다고 생각했는데 시간 초과가 났다... 일단 점수 2개 중에 하나는 정렬할 필요없이 그냥 해당 인덱스에다가 넣어서 처리하고, 이제 뒤에서부터 비교해서 만약 자신보다 작은 인덱스의 값이 자신의 값보다 작으면 둘 다 점수가 떨어지는 지원자니까 cnt에서 하나씩 빼는 식으로 했는데....? (처음에는 문제 잘못 이해해서 cnt 하나씩 더하는 식으로 했는데 이러면 한 명이라도 자기보다 무엇하나 못 본 사람이 있으면 뽑히는 식이라 충족되지 않는 거였다.)

근데 이렇게 풀었다해도 일단 시간초과났다. 아마 for문 돌려서 비교하는 쪽?의 문제 같긴한데ㅔ....

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> score(n+1);

        for (int i=0; i<n; i++) {
            int s1, s2;
            cin >> s1 >> s2;

            score[s1] = s2;
        }

        int cnt = 1;
        int high = score[1];

        for (int i=2; i<=n; i++) {
            if (high > score[i]) {
                cnt++;
                high = score[i];
            }
        }

        cout << cnt << "\n";
    }
}

입력 값이 10^5인데 반복문을 두 번 돌리면 O(n^2)이니까 1초에 10^8번 연산을 하기에 일단 시간초과가 나는건 당연했다.

for문 2번 돌리는 것을 어떻게 한 번으로 줄여야할 지 사실 몰라서 예시코드 살짝 보고 아이디어를 얻었다. 일단 하나의 순서를 고정하고 다른 쪽으로 판별하는건 맞았는데...

어차피 한 점수가 1등인 사람은 뽑히는것이 확정이니 그 사람의 두 번째 등수를 highest_rank에 저장하고 밑의 사람들의 두 번째 종목 등수와 비교한다.

쉽게 생각하면 첫 번째 종목의 등수가 앞에 있는 사람들의 두 번째 종목 등수 중 가장 높은 것을 변수 하나에 기록해두고 그것과 n번째 사람의 두 번째 종목 등수를 비교해 n번째 사람의 등수가 더 낮으면 첫 번째 종목 등수가 앞인 모든 사람들보다 이 사람의 두 번째 종목 등수가 낮은 것이니 뽑히게 되는 것. 그리고 이 사람의 등수가 더 낮으니 highest_rank를 업데이트해주는 것이다.