언제나 처음처럼

[문제 링크]

스택을 사용하면 쉽게 풀 수 있는 문제였다.

배열 기준으로 move[i] - 1 위치에서 인형을 뽑게 되고, 인형을 찾을 때 까지(배열 원소가 0이 아닌 지점) depth = 0 부터 (board.size()-1) 까지 탐색한다.

인형을 찾으면 탐색을 종료하고 인형을 바구니에 담는다. 이때 바구니의 가장 위에 있는 인형과 동일한 인형이라면 가장 위에 있는 인형을 제거하고 answer 값을 2 증가시킨다.

만약 depth == board.size() 라면 인형을 못찾은 것이므로 건너뛰도록 구현하였다.

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;
	stack<int> basket;

	for (int i = 0; i < moves.size(); i++)
	{
		int depth = 0;

		while (depth < board.size() && board[depth][moves[i] - 1] == 0)
			depth++;

		if (depth == board.size())
			continue;

		int pick = board[depth][moves[i] - 1];
		
		board[depth][moves[i] - 1] = 0;

		if (!basket.empty() && basket.top() == pick)
		{
			basket.pop();
			answer += 2;
		}
		else
			basket.push(pick);

	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

스택의 대표적인 문제라고 볼 수 있는 괄호 체크와 분할정복이 섞인 문제였던거 같다.

입력으로 주어지는 문자열 p는 곧 문자열 u = p와 빈 문자열 v가 주어진 형태라고 볼 수 있다.

따라서 문제에서 요구하는 알고리즘대로 구현하면 된다.

먼저 문자열 p가 올바른 괄호 문자열인지 확인해야 한다.

만약 올바른 괄호 문자열이라면 그대로 출력해주면 되고, 올바른 괄호 문자열이 아닐 경우 p를 u와 v로 나눠야 하는데

문제에서 u는 더이상 쪼개질 수 없는 균형잡힌 문자열로 나눠야 한다고 나와있기 때문에 '(' 와 ')' 의 개수가 같아지는 지점을 기준으로 u와 v로 나누면 된다.

마지막으로 나눠진 u에 대해서 올바른 괄호 문자열인지 확인하고, 문제에서 시키는데로 문자열을 완성해주면 된다.

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

bool match(const string& p)
{
	stack<char> temp;

	for (int i = 0; i < p.length(); i++)
	{
		if (p[i] == ')')
		{
			if (temp.empty())
				return false;
			
			temp.pop();
		}
		else
			temp.push(p[i]);
	}
	if (!temp.empty())
		return false;

	return true;
}

string solution(string p) {
	string answer = "";
	
	bool check = match(p);

	if (check)
		return p;
	else
	{
		int uLen;
		stack<char> temp;

		for (uLen = 0; uLen < p.length(); uLen++)
		{
			if (!temp.empty() && temp.top() != p[uLen])
				temp.pop();
			else
				temp.push(p[uLen]);

			if (temp.empty())
				break;
		}
		uLen++;

		string u = p.substr(0, uLen);
		string v = p.substr(uLen);

		check = match(u);

		if (check)
			answer = u + solution(v);
		else
		{
			answer = '(' + solution(v) + ')';
			for (int i = 1; i < uLen - 1; i++)
			{
				if (u[i] == '(')
					answer.push_back(')');
				else
					answer.push_back('(');
			}
		}
	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

스택을 이용하여 풀 수 있는 간단한 문제였다.

여는 괄호는 바로 스택에 쌓고, 닫는 괄호의 경우 스택의 top()에 해당 괄호를 여는 괄호가 있는지 확인하여 있다면 여는 괄호를 스택에서 pop() 해주고, 없다면 잘못된 괄호이므로 "NO"를 반환해준다.

마지막으로 입력받은 괄호 문자열의 끝까지 탐색했다면 스택이 비어있는지 확인 후 비었을 경우 "YES", 비어있지 않을 경우 "NO"를 반환하도록 구현하였다.

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

string Solution(string str)
{
	stack<char> stk;
	for (int i = 0; i < str.size(); i++)
	{
		switch (str[i])
		{
		case ')':
			if (stk.empty() || stk.top() != '(')
				return "NO";
			stk.pop();
			break;

		case '}':
			if (stk.empty() || stk.top() != '{')
				return "NO";
			stk.pop();
			break;

		case ']':
			if (stk.empty() || stk.top() != '[')
				return "NO";
			stk.pop();
			break;

		default:
			stk.push(str[i]);
		}
	}

	return stk.empty() ? "YES" : "NO";
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		string str;
		cin >> str;

		cout << Solution(str) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 136 day