[백준 BOJ] 1302번 베스트셀러 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 맵을 활용한 기초 연산 문제

백준의 1302번 문제는 맵 자료구조를 활용하여 비교적 쉽게 해결할 수 있는 문제이다.

해당 문제는, 판매된 책의 이름들이 입력으로 주어질 때 가장 많이 팔린 책의 이름을 구하여 출력하면 되는 문제이다.

(많이 팔린 책이 여러 종류인 경우엔, 사전 순으로 앞서는 책의 이름을 구하여 출력하라고 문제에 명시되어 있다.)

 

필자는 <책의 이름(string), 팔린 권수(int)> 형식으로 맵을 구성 하여 각 데이터를 저장하였다.

책의 이름만 따로 저장해 둘 string형 벡터도 따로 선언하였으며, 이 둘로 적절히 문제를 해결할 수 있었다.

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

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

 

코드의 실행 순서

1) 팔린 책의 권수(n)를 입력받는다.

 

2) 책의 이름을 key값으로 갖고 해당 책이 팔린 권수를 value값으로 갖는 맵(m)을 미리 선언해 둔다.

m의 각 value값에 원활히 접근할 수 있도록, 책의 이름을 저장할 벡터(v)도 따로 선언해 둔다.

 

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

- 팔린 책의 이름(st)을 순차적으로 입력받는다.

- m에 있어 st를 key값으로 갖는 value에 대해 1을 더하여, 해당 책이 팔린 권수의 값을 추가한다. 

- v에 st 값이 존재하는지를 확인해 보고, 만약 존재하지 않는다면 v에 대해 st 값을 추가하도록 한다.

 

4) 가장 많이 팔린 책의 권수 값을 저장할 max를 0으로 초기화하여 선언해 둔다.

(0에서부터 최댓값을 만날 때마다 값을 변동시키면서 갱신할 예정이다.)

이에 따라 가장 많이 팔린 책의 이름을 저장할 result도 미리 선언해 둔다.

 

5) v의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 현재 탐색하고 있는 특정 책의 팔린 권수(m[v[i]])가 max값보다 크다면, max를 해당 값으로 갱신하도록 한다.

result의 값 또한 해당 책의 이름(v[i])으로 값을 바꾸도록 한다.

- 만약 현재 탐색하고 있는 특정 책의 팔린 권수(m[v[i]])가 max값과 같으나 해당 책의 이름(v[i])이 result보다 사전적으로 앞서있다면, result 값만 v[i]로 값을 바꾸도록 한다.

 

6) 위처럼 연산이 완료되었다면, 최종적으로 저장된 result의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

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

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

	int n;
	cin >> n;

	map<string, int> m;
	vector<string> v;
	for (int i = 0; i < n; i++) {
		string st;
		cin >> st;
		m[st]++;
		
		if (find(v.begin(), v.end(), st) == v.end()) {
			v.push_back(st);
		}
	}

	int max = 0;
	string result;
	for (int i = 0; i < v.size(); i++) {
		if (max < m[v[i]]) {
			max = m[v[i]];
			result = v[i];
		}
		else if (max == m[v[i]] && result > v[i]) {
			result = v[i];
		}
	}
	cout << result << endl;
}

 

제출 결과

(2023.06.29 백준 1302번 문제 제출 결과)