백준 스터디 10주차 (2022-05-17 TUE ~ 2022-05-23 MON)

🥈 1302번 - 베스트셀러

❔ 문제 바로가기

⭐ 풀이의 핵심

• {책의 제목: 판매 횟수} 형태의 map을 활용 하여 판매 횟수를 관리
• map을 순회하며 가장 많이 팔린 책의 제목을 출력

✅ 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력 이라는 조건이 있으므로 unordered_map이 아닌 key 기준으로 자동 정렬이 되는 map을 활용

🔽 코드 (C++)

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

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

    int N;
    cin >> N;

    string book;
    map<string, int> bookList;
    for (int i=0; i<N; i++) {
        cin >> book;
        bookList[book]++;
    }

    int maxNum = 0;
    string maxBook;
    for (auto iter=bookList.begin(); iter!=bookList.end(); iter++) {
        if (iter->second > maxNum) {
            maxNum = iter->second;
            maxBook = iter->first;
        }
    }

    cout << maxBook;

    return 0;
}

🥇 9935번 - 문자열 폭발

❔ 문제 바로가기

⭐ 풀이의 핵심

🚨 #include <string> 라이브러리의 find 함수를 활용할 경우 시간초과

• 스택 의 개념을 활용하여 push & pop
• 아래 코드에서는
  • 실제 스택 자료구조를 활용하지는 않음
  • string answer = ""; 이라는 빈 문자열을 하나 정의하고 이를 스택처럼 활용
    • 주어진 문자열을 순회하며 한 문자씩 스택 문자열에 push
    • 주어진 폭발 문자열의 마지막 문자와 같은 문자가 push된 경우 (스택의 top에 위치하게 된 경우) 폭발 문자열의 길이만큼 최근 push된 문자들을 체크하고 폭발 문자열과 같을 경우 pop
    • 모두 순회 후 스택 문자열의 크기가 0일 경우 "FRULA" 출력 vs 그 외 경우 스택 문자열 출력

🔽 코드 (C++)

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

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

    string str, bomb;
    cin >> str >> bomb;

    string answer = "";
    int bombLen = bomb.size();
    for (int i=0; i<str.size(); i++) {
        answer.push_back(str[i]);

        int answerLen = answer.size();
        if (answer[answerLen-1] == bomb[bombLen-1] && answerLen >= bombLen) {
            bool flag = true;
            for (int j=0; j<bombLen; j++) {
                if (bomb[j] != answer[answerLen-bombLen+j]) {
                    flag = false;
                    break;
                }
            }
            
            if (flag) {
                for (int j=0; j<bombLen; j++) {
                    answer.pop_back();
                }
            }
        }
    }

    if (answer.size() == 0) {
        answer = "FRULA";
    }

    cout << answer;
    return 0;
}