SWExpert Acamedy 가능한 시험 점수 D4
- Set에 대한 간단한 고찰 & 공부
시간 : 40개 테스트케이스를 합쳐서 C의 경우 1초 / C++의 경우 1초 / Java의 경우 2초 / Python의 경우 4초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
문제)
영준이는 학생들의 시험을 위해 N개의 문제를 만들었다.
각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다.
학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까?
예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다
가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다.
두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 1점이다.
가능한 시험점수의 경우의 수를 살펴보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 모두 11가지이다.처음에는 그냥 간단하게 Set으로 풀면 되겠거니 라고 생각했다.
하지만 내가 생각하는 바로는 Implementation이 생각보다 어려웠다.
우선 전략 자체는 Brute Force로 풀어보자고 생각했다.
딱히 유의미한 알고리즘도 없을 것 같았고, 결국에는 그 값이 있는지 없는지 Check해야해 Set이 가장 빠를 것 같았다.
그래서 그냥 아래와 같이 생각했다. (이번에는 main code만 쓰도록 하겠다)
input element를 순차적으로 set 내부의 element와 더해 모조리 insert 해버리는 것이다.
set<int> ans;
ans.insert(0);
for (int i = 0; i < qnum; i++)
for (auto iter = ans.begin(); iter != ans.end(); iter++)
ans.insert(array[i] + *iter);
``
당연히 동작하지 않았는데, 그 이유는 ans.end()가 계속해서 늘어났기 때문이다.
실제로 출력해보니 0, 2, 4, 6, 8, ... 으로 첫 원소 2가 무한히 더해지는 것을 확인할 수 있었다.
그래서 (초심자라면 모두가 예상했듯) ans.end()를 미리 받아서 쓰면 되겠군 이라고 생각했는데 ?! for (int i = 0; i < qnum; i++)
{
set<int>::iterator end_mark = ans.end();
for (auto iter = ans.begin(); iter != end_mark; iter++)
ans.insert(array[i] + *iter);
}안됐다... 계속 안됐다... 왜지?? iterator 출력은 당연히 안되고... 값이라도 볼 겸 *end_mark를 출력해보니까 에잉? 왠지는 모르겠는데 ans.size()와 똑같이 나왔다.
이건 왜지... 일단 넘어가기로 하고
왠지 이런 방법으로는 안될 것 같다는 느낌이 쎄하게 들었지만 일단 마무리는 해보아야하니.. size 비교로 해보기로 했다.
for (int i = 0; i < qnum; i++)
{
int size = ans.size();
int temp = 1;
for (auto iter = ans.begin(); temp <= size; iter++)
{
temp++;
pair<set<int>::iterator, bool> pp = ans.insert(array[i] + *iter);
}
}정답은 잘 나오지만, 1초 라는 시간 내에 풀기가 불가능, 40개 test case를 모조리 틀렸다는 것을 확인할 수 있었다.
어차피 값들을 모조리 비교해야하고, 원소 하나하나에 대해서 다 비교해야하는데 가장 빠른게 set이 아닌가? 라는 생각이 들었다.
그렇다면 hash로 풀어보아야하는가...
여담으로 vector로도 만들어보았지만 당연히 안됐다.
그래서 이제 hash로 풀어볼 예정이지만, 그래도 set 공부를 해서 꽤나 유의미했던 것 같다.
iterator가 무엇인지도 다시 확인하고, red black tree의 특성과 iterating 중 inorder(평생 안 쓸줄 알았는데 결국 쓰긴 쓰는걸 보니 학부 교과과정은 역시 킹갓인가 라는 생각이 들었다)
임을 확인해서 나름 유의미했다.
다시 한번 풀어봐야지
글이 두서가 없는데 문제를 완전히 풀고 나면 다시 한 번 정리하겠다
not only but also