문제
우선 저번 시간에 반복자(iterator)라는 조금 딱딱한 개념을 익히느라 고생 많았다.
이번 내용은 훨씬 부드러우니깐 걱정하지 말도록 하자.
지난 시간에 Set에 원소를 삽입하는 법과 삭제하는 법만을 배웠다.
그러나 결국 집합 내에 원소가 있나 없나 검사하는 작업을 할 줄 모른다면 자료구조를 배우는 의미가 없을 것이다. 오늘은 이에 대해 배우도록 하자.
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert({1,4,6,7,9}); /// insert를 5번 쓰는 것 말고 이런 방법도 있다.
int x;
printf("찾고자 하는 원소를 입력해봐요: ");
scanf("%d",&x);
if(s.find(x) != s.end() ) printf("존재!\n");
else printf("존재하지 않음!\n");
return 0;
}
입력 1)
찾고자 하는 원소를 입력해봐요: 4
|
출력 1)
존재!
|
입력 2)
찾고자 하는 원소를 입력해봐요: 3
|
출력 2)
존재하지 않음!
|
핵심은 아래 한 줄이 원소 유무를 검사하는 표현이라는 것이다.
if(s.find(x) != s.end() )
직관적으로 와 닿기 힘든 표현이지만, 가만히 생각하면 일리가 있다.
***** 이 아래로는 이해를 돕기 위한 설명이며, 실제 set 작동 방식과는 차이가 있다는걸 미리 밝힌다 *****
[1 4 6 7 9]가 들어있는 자료에서 4를 검색을 한다고 생각해 보자.
![](https://u.jungol.co.kr/problem/4639/c2e4c31f-8e33-4b91-aeb8-db06eb592416.png)
반복을 하다가…
![](https://u.jungol.co.kr/problem/4639/e3bf6197-1cde-41c0-9296-829198f71338.png)
찾으면! 현재 화살표(반복자:iterator)를 리턴하고 끝난다.
그런데 3(없는 원소)을 검색한다고 생각한다면?
![](https://u.jungol.co.kr/problem/4639/1acb65ce-a510-4209-81f8-edb5aa7b95ff.png)
로 탐색을 하다가...
![](https://u.jungol.co.kr/problem/4639/a52b87c2-a158-4bf2-a273-704a73110aa6.png)
3은 못찾았어요! 하면서 s.end()를 리턴하고 끝나게 된다고 생각하면 된다.
***** 이 위로는 이해를 돕기 위한 설명이지, 실제 작동 방식이 아니다. (Set의 실제 작동 방식은 이것보다 훨씬 빠르다.
Set이 이렇게 순차적으로 탐색하는 방식을 채택한다면, 굳이 set을 쓸 이유가 없을 것이다. 배열에서 for문 돌리는게 훨씬 편하지…) *****
눈치챘겠지만, s.find(x)의 반환값은 반복자, 즉 그림에 보이는 붉은 화살표이기 떄문에, 당연히 prev()나 next()등을 이용하여 화살표 위치를 좌우로 움직이는 것이 가능하다.
이제 연습문제를 풀어보자. 연습문제는 지난 시간 내용인 반복자(iterator)도 들어있기 때문에, 여태까지의 거저먹기식 연습문제보다는 조금 난이도가 있다. (그치만 여전히 쉽다.)
연습문제
정수형 자료를 저장할 수 있는 집합(set)을 선언한 후, 다음 3가지 작업을 순서대로 처리하는 프로그램을 작성하라.
- i val : val가 없다면 집합에 추가한다.
- r val : 집합 내에 val가 있다면 삭제한다. 없다면 아무 것도 하지 않는다.
- f val : 집합 내에서 val를 찾는다.
* 존재하지 않는다면 “NOPE”를 출력한다.
* 존재하지만 집합내에 유일한 원소라면 UNIQUE”를 출력한다.
* 그 이외의 경우에는, 집합 내에서 val를 제외하고 val와의 차이가 가장 적게 나는 원소를 찾아 출력한다.
(양쪽이 같은 시에는 더 작은 수를 출력한다. 반드시 find() 기능을 사용한다.
입력
첫 줄에 작업의 개수인
다음
출력
각 쿼리마다 필요한 경우 문제에서 요구하는대로 출력한다.
예제1
12
i 1
i 2
i 3
f 0
f 1
f 2
i 4
i 5
i 6
f 4
i 7
f 10
NOPE
2
1
3
NOPE