[MWT@SSHS] 모의고사 #5 풀이

안녕하세요 탐렢입니다!

5번째 모의고사에는 std::set, std::map 등의 자료구조를 익히기 좋은 문제들을 모아놓았습니다.

맞은 뒤에도 적극적으로 저나 다른 멘토들의 코드를 보면서 STL 활용법을 얻어가세요!

A. 숫자 카드 2

map을 이용해서 해결할 수 있는 간단한 문제입니다. 좌표압축을 해도 되지만 map이 훨씬 간단하죠!

map<int,int> M;

X가 적힌 숫자 카드 저장 : ++M[x];

X가 적힌 숫자 카드의 개수 출력 : cout << M[x] << '\n';

이 때 들어가는 원소들이 정렬되어 있을 필요가 없으므로, unordered_map을 이용하면 수행 시간을 줄일 수 있습니다.

B. 회사에 있는 사람

set에는 string도 넣을 수 있답니다! 자세한 설명은 유사 코드를 참조합시다.

set<string,greater<string>> X; string을 사전 역순으로 정렬해서 저장하는 set

string S;

cin >> S;

사원 넣기

//마지막 글자가 'r'인지만 체크하면 된다.

if(X.back() == 'r') S.insert( X.substr(0, X.size() - 6) ); // " enter"를 제외한 사원명을 X에 삽입

else S.erase( X.substr(0, X.size() - 6) ); //" leave"를 제외한 사원명을 찾아 제거

for(string k : S) //S의 원소들을 작은 것부터 순회함

cout << k << '\n';

C. 숫자놀이

map에도 string을 넣을 수 있답니다!

jason9319님의 구현이 깔끔합니다.

참고 :

string s = "abcd ";

s += "efgh";

이 경우 s는 "abcd efgh"가 됩니다. 참 편리한 std::string!

D. 직사각형의 개수

이진 탐색을 이용해서 풀 수도 있지만, set을 이용한 풀이법은 아래와 같습니다.

1. x좌표를 압축하고, x좌표 개수만큼의 set에 y좌표들을 모두 때려박습니다.

2. x좌표 순서대로 정렬된 점의 배열을 탐색하면서, \(i\)번째 점 \((x_i, y_i)\)와 \(j\)번째 점 \((x_j, y_j)\)에 대해서 \(x_i < x_j, y_i < y_j\)인 경우만 고려합니다. 이렇게 탐색하면 한 직사각형을 여러 번 세는 것을 피할 수 있습니다.

3. 점 \((x_i, y_j)\)와 \((x_j,y_i)\)가 모두 존재한다면 직사각형이 존재하는 것입니다.

이는 Set[x_i]에서 y_j를 찾고, Set[x_j]에서 y_i를 탐색해서 해결할 수 있습니다.

복잡도는 \(O(N^2 \lg N)\) 또는 \(O(N^2)\) (with unordered_set)이 됩니다.

E. 개구리 공주

문제 추천해주신 portableangel님께 감사드립니다!

D번과 비슷한 방법이지만, 이번에는 각 점\((x,y)\)를 \((u = x-y, v = x+y)\)로 바꿔서 이 두 좌표를 압축합니다. 이렇게 보면 개구리의 이동은 \(u-v\) 축에서 \(u\)축, \(v\)축에 평행한 이동으로 단순화됩니다.

각각의 x-y좌표마다 set을 만들어서 x+y 좌표를 때려박고,

각각의 x+y좌표마다 set을 만들어서 x-y 좌표를 때려박습니다.

그리고 set의 lower_bound, upper_bound를 이용하여 개구리가 다음 번에 갈 식물의 좌표를 알 수 있습니다.

S.lower_bound(t) : S의 원소 중 t보다 "작지 않은" 최소 원소의 포인터를 반환합니다. 없으면 S.end().

S.upper_bound(t) : S의 원소 중 t보다 "큰" 최소 원소의 포인터를 반환합니다. 역시 없으면 S.end().

자세한 구현은 예제로 맡기겠습니다. 이해가 되지 않는다면 저나 멘토들에게 질문해주세요!

마지막으로, 개구리가 이동에 성공할 경우 원래 있던 식물을 set에서 지워주어야 합니다.

F. 레벨 배치하기

문제 출제 & 추천해주신 jwvg0425님께 감사드립니다!

문제가 어려워 보이지만 description을 해독하면 모든 레벨에 대해 자신 직전에 클리어할 "부모 레벨"을 찾아주는 문제입니다. 부모 레벨에 대한 조건을 써 보면.

레벨 \(i\)가 시작 레벨인 경우,

1. \(K_i = S_i\)를 만족한다.

2. \(S_i\)는 모든 \(S_x\)들 중 가장 작다. 심지어 \(S_i\)와 같은 \(S\)값을 가지는 다른 원소가 존재해서도 안된다.

1, 2가 만족되지 않을 경우 답은 0입니다.

레벨 \(i\)가 시작 레벨이 아닌 경우, 부모 레벨 \(p\)는

1. \(S_p < S_i\)를 만족한다.

2. \(K_p + S_i = K_i\)를 만족한다.

따라서 레벨들을 \(S\) 순서대로 정렬한 뒤 시작 레벨을 결정하고, 나머지 레벨에 대해서는 다음 유사 코드와 같이 진행해주면 됩니다.

map<int,int> M;

Answer = 1;

1. \(S_i = a\)인 모든 \(i\)에 대해서, Answer *= M[K_i - a];

2. \(S_i = a\)인 모든 \(i\)에 대해서 M[K_i]++;

G. 보석 도둑

무조건 보석을 비싼 순서대로 greedy하게 가져가는 것이 최선임을 알 수 있습니다.

따라서 보석을 가격이 비싼 순서대로 정렬하고, set에는 가방의 용량을 모두 넣어둡니다.

같은 무게의 가방이 여러 개 주어질 수 있으므로 multiset을 이용해야 합니다!

각각의 보석을 돌면서 이 보석을 넣을 수 있는 가장 작은 가방이 있다면, 그 가방에 보석을 집어넣고 set에서 빼면 됩니다.