[99클럽 코테 스터디 10일차 TIL] #해시6

10일 차가 되었습니다. 꾸준한 게 중요한 것 같아요. 끝까지 파이팅 해보겠습니다.

 

문제 설명

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

 

생각 흐름

---

먼저 문제를 보았을 때, 포켓몬이라는 단어가 등장했다는 점에서 되게 친숙하게 접근할 수 있었던 것 같다.

 

 문제를 차분하게 읽어보았을 때, 결국 중복된 요소를 잘 골라낼 수 있냐를 물어보는 것 같아서..

 

어떤 자료구조를 사용할까 하다가 중복을 허용하지 않는 자료구조인 map과 set이 생각이 났는데.?

key값만 중요할 뿐 value값을 필요로 하는 문제는 아닌 거 같아 set을 선택하게 되었다.

 

map과 set은 결국 비슷한 자료구조이지만 key와 value의 유무(?) 정도로 구분되기 때문에 비교적 더 간단한 set을 사용하였고

 

문제에서 제공하는 1차원 배열의 사이즈의 절반인 n과 자료구조가 set인 a 배열의 사이즈를 비교해서 출력하며 마무리하였다.

 

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

int solution (vector <int> nums) {
	int answer = 0;
	int n = num.size()/2;

	set <int> a;

	for (int i = 0; i < nums.size(); i++) {
		a.insert(nums[i]);
	}

	if (a.size() <= n) {
		answer = a.size();
	}
	else {
		answer = n;
	}

	return answer;
}

 

 

 

공부한 내용 정리

---

1. set, map의 차이점?

STL array, vector, list가 연속 컨테이너 (Sequential Container) 였다면 map과 set은 연관 컨테이너 (Associative Container)이다. 

연관이라는 말은 저장하려고 하는 자료의 key 값이 서로 관련이 있다는 의미이다.

 

map은 pair <key, value>를 원소로 저장하는데, key를 기준으로 데이터를 정렬한다.

set은 key를 기준으로 원소를 정렬 상태로 저장하지만, value 값이 따로 있지 않다.

 

즉, set은 key와 value가 같은 데이터를 원소로 저장한다.

 

<map>

STL map은 이진 탐색 트리의 일종인 red-black 트리로 구성되어 있다.

map의 key는 유일 (unique) 해야 한다. 즉, 중복된 key값을 사용할 수 없다.

 

같은 key 값을 갖는 원소를 저장하고 싶다면 multimap을 사용하면 된다.

map은 key를 이용해 다른 자료형인 value를 빠르게 검색할 수 있는 연관 컨테이너이다.

 

 map의 원소는 pair <key, value> 이므로

항상 pair 객체를 만들어서 원소를 추가한다는 것을 주의하면 된다.

원소를 추가하거나 삭제할 때는 key값을 기준으로 한다.

 

map <int, string> testmap;

testmap.insert(pair<int,string>  (1, "첫 번째 방법"));
testmap.insert(make_pair(2, "두 번째 방법"));

auto pairdata = make_pair(3, "세 번째 방법");
test.insert(pairdata);

testmap.emplace(4, "네 번째 방법");
testmap.insert_or_assign(5, "다섯 번째 방법");

for (auto & mypair: testmap) {
	cout << mypair.first << " " << my.pair.second << "\n";
}

 

 

 map에 원소를 삽입하는 방법은 5가지가 있다.

 

1. pair <key, value> 임시 객체 생성을 통한 원소 삽입 방법

2. pair<key, value>를 만들어주는 make_pair 함수 사용방법

3. make_pair로 pair<key, value>를 만들어서 이를 직접 삽입하는 방법

4. emplace 내부에서 pair <key, value>를 직접 생성하여 삽입하는 방법

5. insert_or_assign을 통한 key 없는 경우에만 삽입하는 방법

 

map의 원소를 참조할 때 first는 key 값, second는 value값을 나타낸다.

 

testmap.erase(3);

 

map의 멤버 함수 erase()를 통해 원소를 삭제할 수 있다.

 

key 값을 통해 삭제가 가능하다.

 

cout << testmap[1] << "\n";
cout << testmap[2] << "\n";

 

map은 [] 연산자를 통해 value 값을 참조할 수 있어서 연관 배열이라고도 부른다.

배열과 같이 map은 key 값을 index로 사용하여 value에 액세스 할 수 있다.

 

다른 점은 메모리가 연속되어 있지 않다는 것이다.

 

그리고 map에서는 어떤 자료형이라도 key 값으로 사용할 수 있다는 점이다.

 

 

<set>

map과 set은 기능적인 부분은 크게 다른 것이 없다.

 

set은 key를 정렬 기준으로 사용하며 이것을 그대로 저장한다.

key와 value가 같은 map이라고 생각하면 문제가 없다.

멤버 함수도 map과 거의 동일하다.

 

set은 원소를 항상 정렬 상태로 저장하는 컨테이너로 이해하면 된다.

 

출처: https://ssinyoung.tistory.com/47