[Week 1] STRJOIN self review - Queue-ri

STRJOIN self review

파일명: STU/STRJOIN/Queue-ri.cpp
수행시간: 0ms

1. 고민 과정

쉬운 그리디라서 크게 고민하진 않았습니다. 문자열 합칠때의 비용만 따로 변수에 모아주면 됩니다.

2. 풀이 아이디어

가장 짧은 문자열부터 합쳐야 최적해가 나오기 때문에, 이러한 케이스에 유용한 최소 힙을 사용했습니다.

3. 작성한 코드와 설명

Advanced-Algorithm-Study/STU/STRJOIN/Queue-ri.cpp

Lines 15 to 19 in 4946fa6

    
           priority_queue<int, vector<int>, greater<int>> pq; 
        
           while (N--) { 
        
           	int _; cin >> _; 
        
           	pq.push(_); 
        
           }

입력 데이터를 그대로 최소 힙에 넣습니다. 힙 삽입 조작은 O(logN) 이며 이것이 N번 이루어지므로 시간복잡도는 O(NlogN) 입니다.

Advanced-Algorithm-Study/STU/STRJOIN/Queue-ri.cpp

Lines 21 to 30 in 4946fa6

    
           int ans = 0; 
        
           while(pq.size() > 1) { 
        
           	int a = pq.top(); 
        
           	pq.pop(); 
        
           	int b = pq.top(); 
        
           	pq.pop(); 
        
           	ans += a + b; 
        
           	pq.push(a + b); 
        
           }

최소 힙에서 루트 노드 값을 2개 꺼낸 뒤 합치고, 합친 값을 ans에 누적시킨 뒤 다시 최소 힙에 넣습니다. 이 과정은 최소 힙에 원소가 1개 남을 때 까지 반복합니다.

힙 삭제 조작은 O(logN) 이며 삽입 N-1번, 삭제는 2(N-1)번 일어나므로 이 과정도 시간복잡도는 O(NlogN) 이어서 전체 시간복잡도는 O(NlogN) 이 됩니다.

루프가 끝나면 정답 값인 ans를 출력합니다.

추신으로, 알고스팟 g++ 컴파일러 플래그가 c++0x 인 것 같은데 이 경우 C++14의 transparent comparator를 사용하지 못하기 때문에 아쉬웠습니다.

	priority_queue<int, vector<int>, greater<int>> pq;
	while (N--) {
	int _; cin >> _;
	pq.push(_);
	}

	int ans = 0;
	while(pq.size() > 1) {
	int a = pq.top();
	pq.pop();
	int b = pq.top();
	pq.pop();

	ans += a + b;
	pq.push(a + b);
	}