[백준 BOJ] 9612번 Maximum Word Frequency (C++/cpp)

문제 설명

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

 

 

접근 방법 - 맵과 벡터를 활용한 기초 연산 문제

백준의 9612번 문제는 맵의 원리를 잘 알고 있다면 맵과 벡터를 활용하여 비교적 쉽게 해결할 수 있는 문제이다.

해당 문제는, 입력으로 주어지는 단어 중 잦은 빈도로 나타난 단어와 그 횟수를 구하여 출력하면 되는 문제이다.

이때, 최대 빈도수가 같은 경우에는 사전적으로 나중에 나오는 단어를 정답으로 구할 것이 문제에 명시되어 있다.

(영어 지문 해석본을 따로 업로드할까 싶었지만, 진짜 문제 설명이 이게 끝이다.(?))

 

필자는 맵과 벡터를 아래처럼 활용하여 문제를 해결할 수 있었다.

• 맵 <string, int> :: 각 단어를 key로 가지며, 해당 단어의 출현 빈도를 value로 갖게끔 하였다.
• 벡터 <string> :: 맵의 key값들을 저장할 인덱스 저장소로 활용하였다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력으로 주어지는 단어의 개수(n)를 입력받는다.

 

2) 위 설명에 있는 대로, 맵(word)과 벡터(index)를 구성하여 미리 선언해 둔다.

 

3) n의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- 단어(st)를 하나씩 입력받는다.

- 만일 현재 입력값인 st가 index에 존재하지 않는다면, 각 맵 원소의 원활한 접근을 위하여 index에 st를 추가해 둔다.

- word에 있어 st를 key값으로 가지는 공간에 1을 더하여, 해당 단어의 출현 빈도를 갱신해 준다.

 

4) 최대 빈도수를 저장할 max를 0으로 초기화하고, 잦게 나타난 단어를 저장할 max_st를 빈 값("")으로 초기화해 둔다.

 

5) index의 크기만큼, 반복문을 실행하여 word의 값들을 하나씩 탐색한다.

- 만일 현재 탐색하고 있는 word의 value값이 max값보다 크다면 정답을 바꾸어줘야 하기 때문에, max값을 word의 해당 value값으로 갱신하고 max_st에도 현재 word의 key값을 넣도록 한다.

- 현재 탐색하고 있는 word의 value값이 max값과 같은 경우에는, word의 key값과 max_st의 값을 서로 비교해주어야 한다.

이때 word의 key값이 현재의 max_st보다 크다면 정답을 바꾸어줘야 하기 때문에, 위에서 동작한 것과 동일하게 수행하도록 한다.

 

6) 5)의 연산이 모두 종료되었다면, 최종적으로 저장된 max_st와 max의 값을 순차적으로 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 9612번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n;
    cin >> n;
    cin.ignore();

    map<string, int> word;
    vector<string> index;
    for (int i = 0; i < n; i++) {
        string st;
        cin >> st;

        if (find(index.begin(), index.end(), st) == index.end()) {
            index.push_back(st);
        }
        word[st]++;
    }

    int max = 0;
    string max_st = "";
    for (int i = 0; i < index.size(); i++) {
        if (word[index[i]] > max || word[index[i]] == max && max_st < index[i]) {
            max = word[index[i]];
            max_st = index[i];
        }
    }
    cout << max_st << " " << max << endl;
}

 

제출 결과

(2024.02.17 백준 9612번 문제 제출 결과)