대엉코딩

www.acmicpc.net/problem/1406

1. 풀이방법

- 커서가 여러칸씩 뛰는 명령어는 없으므로 상대적으로 간단하였습니다.

- 저는 커서의 앞쪽은 VECTOR 커서의 뒤쪽은 STACK 을 이용하였습니다.

- 방법은 여러가지가 있을 것 같습니다 편하신대로...

- 커서를 왼쪽으로 옮길 때 커서의 뒤쪽이 되는 한 문자는 STACK에 푸쉬하고

- 커서를 오른쪽으로 옮길 때는 STACK에서 POP해 와서 다시 VECTOR에 넣는 식으로 하였습니다.

- 아마 시작할 떄의 커서의 위치가 맨 뒤쪽이라서 이러한 생각을 자연스럽게 하게된 것 같습니다.

2. 주의사항

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	vector<char> tmpc;
	stack<char> tmps;
	int cursor;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		tmpc.emplace_back(s[i]);
	}
	cursor = s.length();
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c;
		if (c == 'L') {
			if (cursor == 0) continue;
			else { //커서 뒤쪽은 스택으로 옮겨 놓음
				tmps.push(tmpc[cursor - 1]); tmpc.pop_back(); cursor--;
			}
		}
		else if (c == 'D') {
			if (tmps.empty()) continue;
			else {
				tmpc.emplace_back(tmps.top()); tmps.pop();
				cursor++;
			}
		}
		else if (c == 'B') {
			if (cursor == 0) continue;
			else {
				tmpc.pop_back();
				cursor--;
			}
		}
		else {
			char c;
			cin >> c;
			tmpc.emplace_back(c);
			cursor++;
		}
	}

	//출력부
	for (int i = 0; i < tmpc.size(); i++) {
		cout << tmpc[i];
	}
	while (!tmps.empty()) {
		cout << tmps.top();
		tmps.pop();
	}


	return 0;
}

www.acmicpc.net/problem/10799

1. 풀이방법

- 문제가 요구하는 사항을 구현하는 문제인데, 스택을 이용해서 현재 몇개의 막대가 쌓여있는지를 확인하였습니다.

- 사실 굳이 STACK.SIZE()를 그냥 임의의 변수 하나를 만들어 관리하면 그냥 반복문만으로도 구현 가능합니다.

2. 주의사항

- 조각의 개수가 증가하는 경우는 두가지 경우입니다. 

- (1) 레이저가 자르는 경우 (2) 막대가 끝나는 경우

3. 나의코드

<stack이용>

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	stack<char> sarr;
	int resultnum = 0;
	for (int i = 0; i < s.length(); i++) {
		if (sarr.empty()) { //비어있을 경우
			sarr.push(s[i]); continue;
		}
		if (s[i] == ')'&&s[i-1]== '(') { //레이저
			sarr.pop();
			resultnum += sarr.size();
			continue;
		}
		if (s[i] == '(') { //막대의 시작
			sarr.push(s[i]);
		}
		else if (s[i] == ')') { //막대의 끝
			sarr.pop();
			resultnum++;
		}
	}
	cout << resultnum << "\n";
	return 0;
}

<변수로 관리>

#include<iostream>
#include<string>

	using namespace std;

	int main() {
		int cnt = 0, result = 0;
		string t;
		cin >> t;
		for (int i = 0; i < t.length(); i++) {
			if (t[i] == '(') {
				if (t[i + 1] == ')') {
					i++;
					result += cnt;
					continue;
				}
				cnt++;
			}
			else {
				cnt--;
				result++;
			}
		}
		cout << result;
		return 0;
	}

www.acmicpc.net/problem/1874

1. 풀이방법

- 문제 설명이 약간 부족한 감이 있는데, 예시를 보면서 아 이렇게 하라는 거구나 라고 알게 되었습니다.

- 1~n까지의 숫자를 보는데 입력으로 들어오는 만들어야되는 것들은 큐에 담아 놓고 앞에서 부터 비교를 했습니다.

- 말로 설명이 어려워 아마 코드를 보시면 이해가 쉽게되실듯 합니다.

2. 주의사항

- 이런류의 문제가 사실 꽤 어렵게 느껴집니다. 개인적으로...

- 여러번 풀어봐야 할 것 같습니다.

3. 나의코드

#include<iostream>
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, tmp;
	cin >> n;
	queue<int> qar; //만들어야하는 결과
	vector<bool> oper; //결과 출력을 위한 +,- 저장벡터
	stack<int> sar; // 만들기 위해 사용할 스택
	for(int i=0;i<n;i++) {
		cin >> tmp;
		qar.push(tmp);
	}
	for (int i = 1; i <= n; i++) {
		if (i == qar.front()) {
			sar.push(i);
			oper.push_back(1);
			sar.pop();
			oper.push_back(0);
			qar.pop();
			while (1) {
				if (sar.empty() == false) {
					if (sar.top() == qar.front()) {
						sar.pop();
							oper.push_back(0);
							qar.pop();
					}
					else { break; }
				}
				else { break; }
			}
		}
		else {
			sar.push(i);
			oper.push_back(1);
		}
	}
	if(sar.empty()==true){
		for (int i = 0; i < oper.size(); i++) {
			if (oper[i] == 1) {
				cout << '+' << '\n';
			}
			else {
				cout << '-' << '\n';
			}
	    }
	}
	else { cout << "NO" << '\n'; }
	return 0;
}

https://www.acmicpc.net/problem/3986

- 조건1. 같은 문자끼리 연결한 선이 교차 하지 않아야 한다.

- 조건2. 각 글자를 정확히 한개의 다른위치에 있는 다른글자와 짝지을 수 있다.

- 문제를 읽고 조건을 생각해보다가 스택을 이용하면 편하게 풀수 있다고 생각한 것이

- 스택에 넣어놓고 같은 단어가 들어와서 그 단어와 함께 pop이 되면 그것이 선이 교차하지 않는다는 것으로 생각

- 1. 스택이 비어있으면 삽입

- 2. 스택의 top()과 현재 문자가 같으면 스택을 pop()

- 3. 스택의 top()과 현재 문자가 다르면 그대로 스택에 push()

- 단어 전체를 순회 하는동안 위 과정을 거쳐는데 만약 1번 조건이 만족하지 않는다면 스택에서 빠져나가지

- 못한채로 남아있는 문자들이 있을 것이고 1번은 만족해도 2번이 만족되지 않는다면 홀수개의 문자가 스택에 남아있을

- 것입니다.

- 즉 반복문을 모두 돌았을 떄 스택이 비어있어야 그 단어는 좋은 단어 인것입니다.

<필기>

<코드>

https://www.acmicpc.net/problem/2493

처음에는 시간초과가 3번 정도 났나...

문제 파악은  별게 없는 것 같습니다.

그리고 레이저는 입력방향의 반대 방향으로 쏘기 때문에 입력을 받으면서

지금 들어와있는 입력 값들만 보면 됩니다.

처음에는 그 건물로 부터 이전에 들어온 값들을 보면서 크기를 비교 했는데 시간초과

최악의 경우 시간을 훨씬 뛰어 넘기 떄문이겠죠

그래서 비교의 수를 줄이기 위해 어떻게 할까 하다가

만약 1번 건물의 높이가 4이고 2번에 들어온 건물의 높이가 8이면 그 이후 건물들은 1번 건물은 볼필요도 없습니다.

즉 약간 높은건물에 가려서 보이지 않는 다는 느낌을 떠올린다면 스택을 이용하여 풀수 있습니다.

새로운 높은 건물이 들어 온다면 그 이전의 건물들은 모두 스택에서 빼버리는 거죠

숫자가 작을때는 별로 차이가 안나겠지만 숫자가 엄청 커질경우 시간차이가 상당 할 것으로 보입니다.

-첫번째 시간초과 났던 소스 입니다.-

-스택을 이용하여 시간초과를 해결한 코드 입니다.-