문제 접근
값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이 들어오면 그 값보다 큰 값을 가진 인덱스들에 대해 라면의 값을 확인하려고 했다. set안에 라면과 문제 중 한 가지 종류의 int값만 넣는다고 가정하면, 두 개의 set이 필요하고 이 때문에 두 set의 index를 확인하기 위한 또 다른 자료 구조가 필요해지면서 풀이가 복잡해졌다. 또 새로 들어온 사람에 대한 참석 여부를 확인하는 것은 비교적 간단한데, 그 사람이 들어옴으로서 참석이 불가능해지는 사람에 대해 계산하는 것은 더 복잡하게 느껴졌다.
문제 풀이
map, set
c++의 표준 라이브러리 이진 검색 트리 자료형이다. 따로 포스팅 해야겠다.
이차원 그래프
주어진 두 개의 int값을 이차원 좌표로 생각하면 참여가 가능한 사람과 참여가 불가능한 사람을 구분하는 것이 훨씬 더 명확해진다. 참석이 불가능한 사람의 경우 그 사람의 좌표 오른쪽 위에 다른 사람의 좌표가 있다. 오른쪽 위에 있다는 의미가 x값과 y값이 모두 더 크다는 의미이기 때문이다.
값의 수용 여부
따라서 새로운 값이 들어왔을 때 그 값을 받아들일지 안받아들일지를 이차원 그래프로 생각하면 그 값의 x좌표를 기준으로 오른쪽을 살펴봤을 때 더 큰 y값을 가진 좌표가 존재하면 안된다. 만약 더 큰 y값을 발견하면 거기서 탐색을 멈추고 그 값을 받아들이지 않는 것으로 종료한다. 탐색이 컨테이너의 마지막 iterator까지 도달하면 큰 값이 하나도 없었다는 의미이므로 그 값을 받아들인다
기존 값 제거
새로운 값이 들어온 경우 그 값에 의해 더 이상 받아들여지면 안되는 값을 제거해야 한다. 그 원리는 값을 받아들이는 경우와 매우 비슷하다. 이차원 그래프 상에서 새로운 좌표의 x값보다 더 작은 좌표들을 확인하다. 이 좌표들은 x값은 반드시 더 작기 때문에 제거될 가능성이 있는 좌표들이다.
이제 y값을 확인하는데, 만약 y값이 새로운 좌표보다 작다면 그 좌표는 새로운 좌표의 왼쪽 아래에 있으므로 제거해야한다. 만약 왼쪽으로 탐색 중 y값이 더 큰 값을 발견하게 되면 이후의 값은 어차피 그 y값보다 반드시 더 크기 때문에 탐색을 종료한다.Iterator
컨테이너 안에서 탐색을 할 때 항상 처음부터 끝까지 하는 것이 아니라 특정 기준점에서 아직 확실하게 정해지지 않은 어떤 지점까지만 이동하므로 Iterator를 활용하는 것이 좋다.
느낀점
두 값이 들어온 경우 이차원 그래프로 생각하면 좋은 풀이가 될 수 있다. C++의 표준 라이브러리 set, map을 활용하면 이진 검색 트리를 이용할 수 있게 되어 값들의 정렬, 검색, 비교에 있어서 매우 효율적이다.
