프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격

프린터

 

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

 

 

1번은 수행이 매우 단순하다. 2번 부분에서 뒤에 중요도가 높은 문서가  한 개라도 존재하는지가 문제 해결의 부분인거 같다. 

 

내 생각에는 맨 처음에 대기 목록에서 맨 앞에 것을 제외하고 가장 높은 우선 순위를 max_priority에 저장한다. max_priority > J 이면 J를 대기 목록 맨 뒤에 넣는다.  max_priority < J이면 출력하고 order를 1 증가한다 . J가 location이면 order를 출력한다.

 

근데 max_priority는 뒤에 가장 큰 우선 순위가 무엇인지 알려준다. 하지만 그 우선순위가 출력되면 그 다음 것은 모른다. 즉 이것은 배열로 저장해야 한다. vector<int> priorities에 저장하자. 그리고 내림 차순으로 정렬한다.

 

그러면 priorities.front() > J 이면 J를 대기 목록 맨 뒤로, priorities.front() < J 이면 출력하고 order 1 증가. J가 location이면 order를 출력한다.

 

근데 구현하다 보니 문제가 있다. 내가 자료구조를 정하지 않아서 벡터로 J를 앞에서 확인하고 뒤로 밀어 넣어 주려니까 이상하게 된다. 즉 priorities는 deque를 사용하는 편이 좋을거 같다. 그리고 ordered_priorities도 앞에 것을 확인하고 빼려니까 deque는 되는데 ,deque는 정렬이 안된다. vector에서 정렬하고 front를 의미하는 인덱스 fr을 선언해 주자.

 

하다 보니 또 문제가 priorities를 ordered_priorities로 정렬하려니 인덱스를 놓친다. pair로 선언해야 할듯 하다.

 

음 나름 쉬운 문제 같은데 설계도 실패해 햇갈려서 짜는데도 오래걸렸다....

 

다른 사람들은 최고 우선순위를 찾을때 이중 반복문으로 앞에서 부터 계속 확인했는데 이 부분은 내가 더 잘 생각한거 같다.

 

#include <string>
#include <vector>
#include<functional>
#include<algorithm>
#include<deque>
#include<queue>
#include<cstdio>

using namespace std;
deque<pair<int, int>> dq;
vector<int> ordered_priorities;
int fr = 0;
int order = 0;



int solution(vector<int> priorities, int location) {
	int answer = 0;
	int N = priorities.size();

	for (int i = 0; i <N; i++) {
		ordered_priorities.push_back(priorities[i]);
		dq.push_back(make_pair(priorities[i], i));
	}

	sort(ordered_priorities.begin(), ordered_priorities.end(),greater<int>());


	while(!dq.empty()) {
		int J = dq.front().first;


		if (J < ordered_priorities[fr] ) {
			pair<int,int> front = dq.front();
			dq.pop_front();
			dq.push_back(front);
		}
		else if (J == ordered_priorities[fr]) {
			order += 1;

			if (location == dq.front().second)
				break;

			dq.pop_front();
			fr++;
		}
	}

	answer = order;
	return answer;
}

 

 

쇠막대기

 

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.

- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.

- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.

- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

 

 

음 문제를 해석했다. (~~~) 이렇게 괄호 안에 () 이렇게 붙은게 몇개인지만 알면 된다. 각 (~~~) 괄호 안에 '() 갯수' 개로 막대기가 증가한다.

 

그리고 어떻게 괄호 안에 것들의 갯수를 셀까 고민했는데, ( 와 )이 한쌍이니까 앞에 ()가 나오면 그 앞에 ( 의 갯수만 알면 된다. 

 

그리고 이것에 대한 방법은 스택이란걸 알아서 알게 된거 같은데..... 스택에 (은 넣고 )이 오면 (을 한개 빼면 되고 ()이 오면 (의 갯수를 세주면 된다.

 

맞았다. 이런 문제는 음 스택인게 뻔히 보이는데 이전의 4개는 큐라고 생각하지 못한거 같다. 하면서 문제 유형을 좀 더 파악해봐야 될거 같다. 큐는 음 앞에서 뺄 수 있는 성격을 갖는 문제 유형?ㅋㅋ

 

다른 사람 풀이를 보니, ) 다음에야 반드시 () 가 나오니까 if문을 네스티드 해서 풀기도 했다.

 

 

 

주식 가격

 

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices                                                                     return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

오른쪽으로 가면서 관찰하다가 뒤에꺼 보다? 가격이 떨어지면 뒤로 가면서 몇일뒤에 떨어졌는지 카운트 해주어야 한다.

 

보니까 지나온 애들중 가격이 가장 큰애를 맥스라 하면 맥스보다 가격이 떨어지면 , 떨어진 가격을 low라 했을때 왼쪽으로 low보다 큰 애들만 빼주면서 카운트 하면 된다 생각했는데 

 

그러면 1,4,2,3,2 은 안 맞는거 같다. 아 아니구나 4,2 에서 4를 빼주고 2를 넣으면 되네.

 

근데 하다보니 문제가 빼주면서 다음 max를 찾아야 하는데 찾기가 어렵다. 그냥 큐에 넣고 우선순위 큐로 처리하는게 날듯?

 

그리고 return answer를 인덱스 순으로 리턴하려면 st에 i도 더해야지, 뺄때 몇번째 원소인지 알 수 있을듯?

 

언제 빼야 되는지는 st의 top 보다 작을때 계속 빼면 된다. 근데 문제가 인덱스를 기준으로 답이 구해진다는 거였다. 그래서 그 부분은 pair로 인덱스도 저장했다.

 

근데 언제 빼야 되는 지에서 st의 top 보다 작을때인지, 이전 st에서 max 보다 새로 만난 cur이 작을때 인지 햇갈렸는데 그게 그거 같다.

 

#include <string>
#include <vector>
#include<stack>
#include<iostream>
#include<queue>

using namespace std;

priority_queue<int> q;
stack<pair<int,int>> st;
int ans[100001];

vector<int> solution(vector<int> prices) {
	vector<int> answer;

	for (int i = 0; i < prices.size(); i++) {
		int cur= prices[i];

		if (i == prices.size()-1) {
			st.push(make_pair(cur, i));
			cur = 0;
		}

		if (st.empty() || (!st.empty()  && st.top().first <= cur)) {
			st.push(make_pair(cur,i));
		}
		else if ((!st.empty() && st.top().first > cur) || i == prices.size()-1) {
			int cnt = 0;

			while (!st.empty() && st.top().first > cur) {
				cnt = i - st.top().second;
				ans[st.top().second] = cnt;
			//	cout << st.top().second << " " << cnt << "\n";
				
				st.pop();
			}

			if ( prices.size()-1 > i) {
				st.push(make_pair(cur, i));
			}

		}

	}

	for (int i = 0; i < prices.size(); i++) {
		answer.push_back(ans[i]);
	}


	return answer;
}

 

다른 분의 풀이는 prices에 가격은 저장되어 있으니까, index만 스택에 저장해서 풀었다. 이게 변수 설정에서는 훨씬 당연하고 효율적이다...

 

스택/큐 영역 6문제를 풀다 보니 이 문제가 스택인지 큐인지 판단하는게 생각보다 어려운거 같다. 

 

뭔가 스택을 사용하니까 st.front() 랑 다음 원소 관계를 정의하면 , pop 연산을 하고도 스택 내부에서는 앞에서 처리가 되니까 정의한 관계가 지속되는거 같다... 뭔 소린지 나도 잘 모르겠다...