(7/29) 4일차 - STL 문제

어제와 같이 문제를 풀었습니다. 총 8문제였습니다.

https://bas.ioikorea.cc/problems/list

2022 여름학교 처음반

 

1. 순열    O

vector 두 개를 만들어 현재 순열의 값들을 넣은 후 각각에 대해 prev_permutation() 과 next_permutation() 을 사용한 후 출력해주면 됩니다.

 

2. 바구니     O

set을 사용하면 시간초과가 발생합니다. (multiset과 unordered_set, unordered_multiset을 써도 동일)

따라서 set이 아닌 map을 활용해야 하는 문제입니다. map<int, int>를 만들어주고 정수 a를 key값으로 정하고 정수 a의 개수를 value값으로 설정해줍니다. 이후 각각의 명령에 대해 올바른 수행을 해주면 됩니다.

     1. 정수 a를 추가한다 --> 이미 a라는 key값이 존재한다면 iter->second += 1, 존재하지 않는다면 insert(a, 1)

     2. 정수 a를 한개 삭제한다 --> iter -> second -= 1, if(iter->second == 0) erase (value가 0이면 삭제해주어도 된다)

     3. 정수 a의 개수를 출력한다 --> print(iter->second)

 

3. 유니크    O

문제 제목처럼 vector에 unique라는 명령을 써주면 됩니다. unique를 사용하게 되면 중복한 원소들이 제거되며 vector의 크기가 감소하지만 capacity는 남아있기 때문에 원소가 빠진 자리들을 erase해주는 명령까지 수행해주고 vector를 출력해주면 됩니다. 

 

4. 사과나무    O

나이가 L보다 크거나 같고 R보다 작거나 같은 사과나무의 수 & 사과의 수를 계산해야 하는 문제입니다. 입력받은 사과를 vector에 넣어 오름차순 정렬해주고 누적합 배열을 만듭니다. 이후 lower_bound(L)과 upper_bound(R)을 해줘서 조건을 만족하는 구간의 길이(사과나무의 수)를 구하고 그 구간에 있는 사과의 수를 누적합 배열에서 hap[R] - hap[L]로 O(1)에 구해주면 문제를 해결할 수 있습니다.

 

5. 실습 문제 준비     O

set 자료형에 1~n까지의 수를 넣어놓습니다. 그리고 1번 코치부터 완전탐색 해주면서 1 ~ Zi 까지 중 가장 높은 번호의 문제를 set에서 삭제해줍니다. 만약 삭제할 수 없다(1 ~ Zi까지의 문제가 전부 삭제되었다) 라고 한다면 이전까지의 코치의 수를 출력해줍니다.

 

6. 볼륨을 높여라!    X

작성중. 아직 해결하지 못함.

 

7. 슈퍼컴퓨터    X

작성중. 아직 해결하지 못함.

 

8. 두 절친    X

작성중. 아직 해결하지 못함.