C++ 자료구조 1 - 백준 1874번, 1406번

스택 관련 문제들 계속 풀어보고 있다!!

백준 1874번 www.acmicpc.net/problem/1874

1874번: 스택 수열

문제 : 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

그러니까 1부터 n까지를 스택에 먼저 넣고 이 스택에서 수를 빼서 수열을 만들어라는 문제이다.

예를 들면

8 4 3 6 8 7 5 2 1 을 입력으로 넣으면 (맨 앞의 8은 n이다)

처음에 4를 수열에 만들어야 하니까 1 2 3 4를 순서대로 스택에 넣고 (++++ 가 출력) 이 스택에서 다시 4를 빼서 (-) 4를 수열에 넣는다. 그러면 이제 스택에는 1 2 3 이 남아있다. 그다음에 3을 수열에 넣어야 하니까 이 스택에서 3을 뺀다 (-)

그러면 스택에는 1 2 가 남아있고 6을 수열에 넣어야하니까 5 6을 스택에 넣고(++) 6을 뺀다 (-). 그러면 스택에는 1 2 5가 남아있다!! 이제 수열에 8을 넣어야 하니까 7 8을 스택에 넣고(++) 8을 뺀다(-). 그리고 그다음엔 7을 넣어야 하니까 그냥 7을 바로 빼면 되고(-) 스택에 남은 수는 1 2 5 니까 5 2 1을 수열에 넣으려면 차례대로 빼면 된다(---) 

따라서 출력은 ++++--++-++-----

#include<iostream>
#include<stack>
#include<string>

using namespace std;
int main() {
	stack<int> s;
	int n;
	string ans;

	cin >> n; //처음에 들어온 입력값
	int m = 0; //스택에 들어간 마지막 값
	while (n--) {
		int x;
		cin >> x; //수열에 들어가는 입력값
		if (x > m) { 
			while(x > m) {
				s.push(++m);
				ans += '+'; //push해준 횟수만큼 pop
			}
			s.pop();
			ans += '-'; //pop
		}
		else { //x가 m보다 크지않으면
			bool found = false;
			if (!s.empty()) {
				if (x == s.top()) { //x가 m과 같아야 스택에서 올바르게 pop될 수 있음(오름차순을 지켜야 하기 때문에)
					found = true; //x과 m(s.top())과 같으면 true
				}
				s.pop();
				ans += '-';
			}
			if (!found) {
				cout << "NO" << '\n';
				return 0; 
			}
		}
	}
	for (auto x : ans) { //ans에서 하나씩 꺼내오자
		cout << x << '\n';
	}
	return 0;
}

 

백준 1406번 www.acmicpc.net/problem/1406

1406번: 에디터

이 문제는 주어진 문자열을 편집할 수 있는 간단한 편집기를 구현하는 것이다! 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다

이 편집기가 수행할 수 있는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

|을 커서로 표현해서 예를 들어보면

L 연산 : abc|xyz -> ab|cxyz

D 연산 : ab|cxyz -> abc|xyz

B 연산 : abc|xyz -> ab|xyz (커서 왼쪽의 문자 삭제)

P d 연산 : ab|xyz -> abd|xyz

 

우리는 이 커서를 기준으로 왼쪽/오른쪽 문자열을 각각 스택에 넣어 저장할 수 있다. (명령어가 아무것도 실행되지 않았을때는 커서가 문장의 맨 뒤에 있다고 가정 abcxyz|)

스택에 넣으면 훨씬 더 효율적인 시간으로 이 명령어들을 수행 할 수 있다. 그림을 그려보면 쉽게 이해할 수 있다!!

 

위의 그림은 L연산을 했을 때의 그림이다. 커서의 왼쪽 스택은 맨 앞에 문자가 밑에 깔리도록 스택을 구현하고, 커서의 오른쪽 스택은 맨뒤의 문자가 맨 밑에 깔리도록 스택을 구현하면 L연산뿐만 아니라 D연산, B연산, P연산 모두 쉽게 구현할 수 있다.

 

D연산은 커서를 오른쪽으로 옮기는 것인데 이것은 오른쪽 stack의 맨 위를 pop 하고 이 문자를 왼쪽 스택에 push 해주면 된다.

B연산은 왼쪽 stack의 맨 위를 pop 해주기만 하면 되고

P d연산은 왼쪽 스택에 d를 push 해주기만 하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
char a[600000];
int main() {
	scanf("%s", &a);
	stack<char> left, right;
	for (int i = 0; i < strlen(a); i++) {
		left.push(a[i]); //커서가 처음에는 맨 뒤에 위치해 있으므로!
	}
	int n;
	scanf("%d", &n);
	while (n--) {
		char what;
		scanf(" %c", &what);
		if (what == 'L') {
			if (!left.empty()) {//왼쪽 스택이 비었으면 (커서가 맨 앞에 위치해있으면) 커서 옮길수 없음
				char c = left.top();
				left.pop();
				right.push(c);
			}
		}
		if (what == 'D') {
			if (!right.empty()) {//오른쪽 스택이 비었으면 (커서가 맨 뒤에 위치해있으면) 커서 옮길수 없음
				char c = right.top();
				right.pop();
				left.push(c);
			}
		}
		if (what == 'B') {
			if (!left.empty()) {//왼쪽 스택이 비었으면 (커서가 맨 앞에 위치해있으면) 삭제할 친구 없음
				left.pop();
			}
		}
		if (what == 'P') {
			char c;
			scanf(" %c", &c);
			left.push(c);
		}
	}
	while (!left.empty()) { //left스택을 right스택 위에 쌓아서 두 스택을 합쳐서 출력한다
		right.push(left.top());
		left.pop();
	}
	while (!right.empty()) {
		printf("%c", right.top());
		right.pop();
	}
	return 0;
}

처음에 이렇게 코드를 짜니까 시간 초과라고 떴다..

첫 번째 for문에 들어가기 전에 int m = strlen(a); 이렇게 선언해주고 그냥 백준 선생님 코드 참고해서 char c = right.top() 이렇게 선언된 건 지우고 그냥 바로 left.push(right.pop())이런 식으로 다 바꿔적으니까 통과됐다!!

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
char a[600000];
int main() {
	scanf("%s", &a);
	stack<char> left, right;
	int m = strlen(a);
	for (int i = 0; i < m; i++) {
		left.push(a[i]); //커서가 처음에는 맨 뒤에 위치해 있으므로!
	}
	int n;
	scanf("%d", &n);
	while (n--) {
		char what;
		scanf(" %c", &what);
		if (what == 'L') {
			if (!left.empty()) {//왼쪽 스택이 비었으면 (커서가 맨 앞에 위치해있으면) 커서 옮길수 없음
				right.push(left.top());
				left.pop();
			}
		}
		else if (what == 'D') {
			if (!right.empty()) {//오른쪽 스택이 비었으면 (커서가 맨 뒤에 위치해있으면) 커서 옮길수 없음
				left.push(right.top());
				right.pop();
			}
		}
		else if (what == 'B') {
			if (!left.empty()) {//왼쪽 스택이 비었으면 (커서가 맨 앞에 위치해있으면) 삭제할 친구 없음
				left.pop();
			}
		}
		else if (what == 'P') {
			char c;
			scanf(" %c", &c);
			left.push(c);
		}
	}
	while (!left.empty()) { //left스택을 right스택 위에 쌓아서 두 스택을 합쳐서 출력한다
		right.push(left.top());
		left.pop();
	}
	while (!right.empty()) {
		printf("%c", right.top());
		right.pop();
	}
	return 0;
}

이게 통과된 코드!!

최대한 풀이에서 봤던 코드랑은 다르게 하고 싶은데 하다 보면 결국 풀이랑 비슷해지는 거 같다ㅠㅠㅠㅠ 더 생각해봐야지