💎 문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
💎 입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
💎 출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
💎 풀이 방법
문제가 쉽기도 하고 velog에 올리는 문제 말고도 푼 문제들이 좀 많은데 그 중에서 해시와 관련된 문제에 대한 리뷰를 해보지 않았던 것 같아서 쉽지만 짚고 넘어갈겸 정리해서 업로드 해본다!!
푼 문제는 해시를 바로 떠올릴 수 있게 하는 문제였는데, 해시 자료구조는 예를들어 string 형식의 key를 입력하였을 때 이에 대해 존재할 때 int형의 data를 받을 수 있는 경우를 보여준다. 다시 말해서 key를 통해서 key에 해당하는 값을 찾을 수 있도록 쉬운 접근방법을 제공하는 것을 해시(Hash) 라고 한다!! 그렇기 때문에 자료가 저장되는 공간인 해시 테이블에서 정렬되지 않은 값들을 key를 이용하여 검색하고 값을 찾아볼 수 있다.
이에 접근할 수 있는 방법으로 map이라는 STL클래스가 있는데, map을 활용하여 이번 문제를 풀었다!! map 또한 key와 value를 묶인 pair의 쌍으로 이루어진 트리이기 때문에 이 map에 듣도 못한 사람들을 먼저 저장해준 후 보도 못한 사람들을 입력받아 map에서 찾아 주는 방식으로 해결하였다!!
map<string, int> m;
.
.
.
for(int i = 0;i < N;i++){
string s;
cin >> s;
m.insert({s, i});
}
for(int i = 0;i < M;i++){
string s;
cin >> s;
if(m.find(s) != m.end())
v.push_back(s);
else
continue;
}map은 다만 해시가 정렬되지 않은 자료구조에서 찾아내는데에 반해 자료를 저장하게 되면 안에서 자동으로 오름차순 정렬된다. map의 기본 구조는 'map <key type, value type> 이름'으로 선언하며 map에 key와 value는 insert()를 이용하여 pair형태로 입력해서 넣어준다. 다음 M개의 보도 못한 값들을 입력 받았다면 find()를 이용하여 map의 string을 찾아준다. 만약 찾지 못했다면 map의 end()가 리턴되므로 이와 같지 않을 때는 듣도 보도 못한 값이 찾아진 것으로 이를 vector에 삽입하여 주었다!!
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(int i = 0;i < v.size();i++){
cout << v[i] << "\n";
}이렇게 map에서 찾아낸 정보를 vector에 담아진 것을 정렬하면 오름차 순으로 출력해주며 그의 갯수를 size()함수로 출력해주면 문제를 해결할 수 있었다!!
💎 전체 코드
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int N, M;
int main(int argc, const char * argv[]) {
map<string, int> m;
cin >> N >> M;
vector <string> v;
for(int i = 0;i < N;i++){
string s;
cin >> s;
m.insert({s, i});
}
for(int i = 0;i < M;i++){
string s;
cin >> s;
if(m.find(s) != m.end())
v.push_back(s);
else
continue;
}
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(int i = 0;i < v.size();i++){
cout << v[i] << "\n";
}
return 0;
}💎 고민
알고리즘을 공부하다 보니 전공 수업 때 들었었던 자료구조, 알고리즘과 관련된 강의들이 떠올랐다,,, 열심히 들을걸 ㅠㅠㅠ 수업에서 기초적인 알고리즘 및 자료구조의 개념들을 알려줬어서 이들을 잘 이용하였다면 조금 더 빨리 알고리즘 학습에 흥미를 느꼈을 것 같다,,, 그래도 어렴풋이 수업에서의 내용들이 기억이 나면서 구글링하였을 때 '아 맞아 이런거 알려줬었지', '아 이렇게 하면 해결이 된다고 했었지' 라는 생각들이 들어서 노력하면 충분히 학습할 수 있다고 생각이 들었다!!
map STL 클래스를 이용하여 특정 string을 찾는 방법을 코드로 작성해 보았는데, 일일히 탐색하는 방법과 탐색 정렬 알고리즘을 새롭게 작성하기보다 해시 구조에서의 map 함수를 이용하여 찾는 방법도 기억해 둬야겠다!!
화팅!!
