[백준 BOJ] 14425번 문자열 집합 (C++/cpp)

문제 설명

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

14425번: 문자열 집합

 

접근 방법 - 맵을 활용한 문자열 탐색 문제

백준의 14425번 문제는 맵 자료구조를 활용하여 해결할 수 있는 문자열 탐색 문제이다.

해당 문제는, 검사하고자 하는 문자열을 하나씩 입력받을 때 특정 집합 속에 존재하는 문자열의 개수가 총 몇 개인지를 연산하여 출력해야 하는 문제이다.

맵이라는 자료 구조를 모른다면, 2개의 배열을 통하여 무작위로 비교하는 식으로 정답을 구하려 했을 수도 있다.

하지만 이렇게 연산을 하게 된다면 입력값의 개수가 최대일 때에 시간 초과가 발생할 수도 있다. 일단 필자가 그랬다...

맵은 key와 value의 타입을 원하는 타입으로 지정할 수 있기 때문에, 이러한 경우에 훨씬 효율적으로 탐색을 수행할 수 있다.

그렇기 때문에 만약 맵이라는 구조를 몰랐다면 이번 기회에라도 익혀두는 것이 문제 해결에 도움이 될 것이다.

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

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

 

코드의 실행 순서

1) 집합에 존재하는 문자열을 key 값으로 저장할 맵 ma를 전역 변수로 미리 선언해 둔다.

(문자열(string)을 key로, 해당 문자열의 존재 여부(bool)를 value로 저장하게끔 설정하였다.)

 

2) 집합의 크기(n)와 검사하고자 하는 문자열의 개수(m)를 입력받는다.

 

3) n의 크기만큼, 반복문을 실행하여 문자열(st)을 하나씩 입력받는다.

그리고 입력받은 문자열(st)은 그 즉시 ma의 요소로 삽입되게끔 한다.

"해당 문자열이 집합에 존재한다."를 뜻하게끔, {st, true} 형태로 삽입을 수행한다.

 

4) 검사하고자 하는 문자열들 중 집합에 존재하는 문자열의 총합을 저장할 변수 count를 0으로 초기화하여 선언한다.

 

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

- 검사할 문자열(test)을 하나씩 입력받는다.

- ma[test]의 값이 true라면, 이는 집합에 해당 문자열이 존재한다는 것을 의미한다. 따라서 이 경우엔, count에 1을 더해주도록 한다.

 

6) 위 연산을 완료하였다면, 최종적으로 저장된 count의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

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

// 백준 14425번 코드
map<string, bool> ma;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string st;
		cin >> st;
		ma.insert({st, true});
	}

	int count = 0;
	for (int i = 0; i < m; i++) {
		string test;
		cin >> test;
		if (ma[test] == true) { count++; }
	}
	cout << count << endl;
}

 

제출 결과

(2022.12.19 백준 14425번 문제 제출 결과)

어마무시한 시간 초과의 흔적들...