- 1. Problem
- 2. My Approach
- 3. Implementation
- 4. Textbook Approach
- 5. Implementation
- 6. Analysis
- 7. Feedback
1. Problem
2. My Approach
- 문제를 이해하면 간단한 연산으로 답을 구할 수 있음을 알 수 있다.
- 주어진 문자열들의 길이를 오름차순으로 정렬하고 맨 앞의 가장 작은 두 값을 더한 값을 ret에 더해주고 그 값을 다시 정렬된 배열의 적합한 위치에 넣어준다.
3. Implementation
int main(){
...
priority_queue<int,vector<int>,greater<int>> q;
...
int ret = 0;
while(q.size() != 1){
int t1 = q.top(); q.pop();
int t2 = q.top(); q.pop();
ret += t1 + t2;
q.push(t1+t2);
}
...
}
- 우선순위 큐를 만들어주어 자동으로 정렬된 상태가 지속되게 구현해 주었다.
4. Textbook Approach
- 놀랍게도 본인의 코드와 거의 동일하다.
- 다만 main함수 내에서가 아니라 별도로 함수를 만들었다.
5. Implementation
int concat(const vector<int> lengths){
priority_queue<int, vector<int>, greater<int> > pq;
for(int i = 0; i < lengths.size(); i++)
pq.push(lengths[i]);
int answer = 0;
while(pq.size() > 1) {
int min1 = pq.top(); pq.pop();
int min2 = pq.top(); pq.pop();
pq.push(min1 + min2);
answer += min1 + min2;
}
return answer;
}
6. Analysis
- 본인의 코드와 책의 코드의 while문은 둘 다 n-1번 실행되고, 그 안에서 수행하는 q.top( )과 q.pop( )함수 호출에는
O(lgn)의 시간이 걸리기 때문에 알고리즘의 전체 수행시간은O(nlgn)이다.
7. Feedback
오프라인으로 치뤄지는 코딩 대회에선 지금처럼 마음대로 인터넷을 이용할 수 없다. 때문에 미리 STL에서 제공하는 여러 함수들을 미리 익혀둘 필요가 있다.