[Week 1] STRJOIN self review - Choi-mina

[Choi-mina]

STRJOIN self review

• 파일명: STU/STRJOIN/Choi-mina.cpp
• 수행시간: <4ms>

1. 고민 과정

최소 비용을 찾기 위해서 어떻게 해야할지 고민을 했던 것 같습니다.

2. 풀이 아이디어

최소 비용을 찾아야 하기 때문에 우선순위 큐를 사용해 top쪽으로 작은 값을 위치시켰습니다.

3. 작성한 코드와 설명

int c, n;
int cost;

int con(const vector<int> len) {
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < len.size(); i++) {
		q.push(len[i]);
	}
	cost = 0;
	while (q.size() > 1) {
		int min1 = q.top();
		q.pop();
		int min2 = q.top();
		q.pop();
		q.push(min1 + min2);
		cost += (min1 + min2);
	}

	return cost;
}

con()함수는 결과값을 반환하는 함수입니다.
작은 값을 top쪽에 위치하도록 q라는 우선순위 큐를 선언해주었습니다.
원소가 1개가 남을때까지 반복하는 while문을 적어주었습니다.
제일 위에 있는 원소를 min1변수에 넣어주고 pop을 이용해 다음 원소를 가져올 수 있도록 해주었습니다. min2에 그 다음으로 작은 원소를 넣어주었습니다. 이 둘을 더해 q에 다시 넣어주어 최소 비용을 찾을 수 있게 구현하였습니다.

int main() {
	cin >> c;
	for (int i = 0; i < c; i++) {
		cin >> n;
		vector<int> len(n);
		for (int j = 0; j < n; j++) {
			cin >> len[j];
		}
		cout << con(len) << endl;
	}
	return 0;
}

main에서는 입력을 받고 결과값을 반환하는 함수를 출력하는 코드를 적어주었습니다.