이것 저것 &

문제링크: https://www.acmicpc.net/problem/1715

문제 접근에 대해서 이해하면 쉽게 구현한 문제이다.

우선, 그리디한 방식으로 문제를 도출할 수 있다는 것을 이해해야 한다!

접근방식

1. 생각해보면, 항상 작은수를 먼저 처리해주면 최소값이 도출이 된다는 것을 알수 있다.

2. 그렇다면 새로 추가되는 수는 어떻게 관리해주어야 할까? 

새로 수를 넣어줄때 마다 정렬을 해야하나? 

아니다!

그냥 편하게 우선순위 큐를 사용하면 될 일이다. 

자동으로 lgn번의 탐색으로 수를 정렬된 상태로 보관해주기 때문에

해당 문제에 가장 적합한 자료구조이다.

문제풀이 

1.  구현 자체는 너무나도 단순하다.

priority_queue를 사용하여 문제를 해결하자.

정답코드입니다.

#include <iostream>
#include <queue>
using namespace std;

int n = 0;
priority_queue <int> que;
long long result = 0;

int main() {
	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		que.push(temp * -1);
	}

	while (que.size() != 1) {

		int a = que.top() * -1;
		que.pop();
		int b = que.top() * -1;
		que.pop();

		result += (a + b);

		que.push( (a + b) * -1);


	}

	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1918

접근방식

1. 후위 표기식으로 변환하는 문제

2. 자료구조중 에서 스택을 사용하면 쉽게 구할 수 있다.

3. 연산자를 스택에 넣어놓으며 진행 

문제풀이 

1. 연산자는 스택에 있는 값과 값을 비교하며 진행

2. *,/ 이 나온 경우

스택에서 *,/ 가 나오면 스택에서 POP하고 결과에 추가

3. +,-가 나온 경우

스택에서 *,/,+,- 가 나오면 스택에서 POP하고 결과에 추가

4. )가 나온 경우

(가 나올때 까지 POP하고 결과에 추가

즉 연산자들의 우선 순위는 *,/ > +,- > ( 순 입니다.

아래는 정답 코드입니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string input;
string result;
stack <char> stk;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] >= 'A' && input[i] <= 'Z')
			result += input[i];
		else {
			if (stk.empty())
				stk.push(input[i]);
			else {
				if (input[i] == '(')
					stk.push(input[i]);
				else if (input[i] == ')') {
					while (1) {
						char temp = stk.top();
						stk.pop();
						if (temp == '(')
							break;
						result += temp;
					}
				}
				else if (input[i] == '+' || input[i] == '-') {
					while (!stk.empty() && stk.top() != '(') {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
								
				}
				else if (input[i] == '*' || input[i] == '/') {
					while (!stk.empty() && (stk.top() == '*' || stk.top() == '/')) {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
					
				}


			}

		}

	}

	while (!stk.empty()) {
		result += stk.top();
		stk.pop();
	}

	cout << result << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/2493

자료구조중에서 스택을 사용해야 하는 문제였습니다.

접근방식

1. 일반적인 방식을 생각한다면 최악의 경우에는 O(n^2)이 될수 있기 때문에 시간초과가 일어나는 것을 인지 

2. 항상 자신의 왼쪽에서 가까운 값들 부터 확인해야 한다는 아이디어를 통해서 스택을 사용하면 검색을 줄일 수있다는 것을 인지 

문제풀이 

1. 스택이 비어있다면 0을 출력

2. 스택에 값이 있다면, 스택의 top값이 현재 값보다 클때까지 pop!

3. 다시 1번을 수행한다.

아래는 정답코드입니다.

#include <iostream>
#include <stack>
using namespace std;
int n;
int arr[500000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;

	stack <pair<int, int>> stk;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		if (stk.empty()) {
			stk.push(make_pair(i, arr[i]));
			cout << 0 << ' ';
		}
		else {
			
			while (!stk.empty()) {
				if (stk.top().second > arr[i]) {
					cout << stk.top().first << ' ';
					break;
				}
				else
					stk.pop();
				
			}

			if (stk.empty())
				cout << 0 << ' ';
			stk.push(make_pair(i, arr[i]));
		}

		
	}
	cout << "\n";


	return 0;
}