알고리즘 문제 풀기

백준 2504: 괄호의 값, 1722번 순열의 순서, 13251번 조약돌 꺼내기.

studying develop 2020. 2. 7. 14:28

2504번 괄호의 값.

 

내 코드

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

using namespace std;
using li = long long int;

string str = "";
int idx = 0;
stack<char> st;
bool flag =true;

void pushStack(char x) {
	if (x == ')') {
		if (st.size() > 0) {
			if (st.top() == '(') {
				st.pop();
			}
			else {
				flag = false;
			}
		}
		else {
			flag = false;
		}
	}
	else if(x==']'){
		if (st.size() > 0) {
			if (st.top() == '[') {
				st.pop();
			}
			else {
				flag = false;
			}
		}
		else {
			flag = false;
		}
	}
	else if (x == '(') {
		st.push('(');
	}
	else if (x == '[') {
		st.push('[');
	}
}

li dfs() {
	li sum = 0;

	while (idx <= str.size())
	{
		if (idx == str.size()) {
			return sum;
		}

		if (str[idx] == '(' && idx + 1 < str.size() && str[idx + 1] == ')') {

			idx += 2;
			sum += 2;
		}
		else if (str[idx] == '['&& idx + 1 < str.size() && str[idx + 1] == ']') {
			idx += 2;
			sum += 3;
		}
		else if (str[idx] == '(') {
			pushStack(str[idx]);
			idx += 1;
			sum += 2 * dfs();		
		}
		else if (str[idx] == '[')
		{
			pushStack(str[idx]);
			idx += 1;
			sum += 3 * dfs();
		}
		else if (str[idx] == ')') 
		{
			pushStack(str[idx]);
			idx += 1;
			return sum;
		}
		else if (str[idx] == ']') 
		{
			pushStack(str[idx]);
			idx += 1;
			return sum;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> str;
	
	li ans=  dfs();

	if(st.size() ==0 && flag == true){
		cout << ans;
	}
	else
	{
		cout << 0;
	}


	return 0;
}

나는 계산은 재귀로 하고 , 괄호 입력 확인은 stack으로 해주었다.....

 

다른 분이 한걸 보니까. 종료 괄호를 기준으로 값을 곱해주면 에러 입력값도 다 0이 제대로 나오나 보다. 신기하다.... 어떻게 저렇게 설계 했을까.

 

다른 분

#include <cstdio>

using namespace std;



char str[40];
int idx=1;
int serch(){
    if(str[idx] != '(' && str[idx] != '[')
        return 0;

    char e_ch = str[idx] == '(' ? ')' : ']';
    int val = str[idx] == '(' ? 2 : 3;
    idx++;
    if(str[idx]==e_ch)
    {
        idx++;
        return val;
    }
    int return_=0;
    while(str[idx]!=e_ch){
        int res = serch();
        if(res == 0)
            return 0;
        return_+= res;
    }
    return_*=val;
    idx++;
    return return_;
}
int main()
{
    scanf("%s",str+1);
    int result=0;
    while(str[idx]!='\0'){
        int res = serch();
        if(res == 0)
        {
            result = 0;
            break;
        }
        result+=res;
    }
    printf("%d",result);
    return 0;
}

 

 

1722번 순열의 값.

 

3달전에는 못풀었던 문제이다. 순열 조합, 경우의 수가 즉 규칙이 있으면 N번째 관련된 값을 찾는데 도움이 많이 되는것 같다.

 

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

using namespace std;
using li = long long int;

int N, K;

li fac[21];
vector<int> arr;

bool vis[21] = { 0 };

int getRankAndPop(int x) {
	int rank = 0;
	for (int i = 1; i < 21; i++) {
		if (i == x && vis[i] == 0) {
			//arr.erase(arr.begin() + i);
			vis[i] = 1;
			return rank;
			break;
		}
		else if (vis[i] == 0) {
			rank++;
		}

	}
	
	return -1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> K;

	fac[0] = 1;
	for (int i = 1; i < 21; i++) {
		fac[i] = fac[i - 1] * i;
	}


	if (K == 1) {
		li M;
		cin >> M;

		for (int i = 1; i <= N; i++) {
			arr.push_back(i);
		}
		M -= 1;
		for (int i = 0; i < N; i++) {
	

			int nth = M / fac[arr.size()-1];
			cout << arr[nth]<< " ";
			arr.erase(arr.begin()+nth);

			M -= fac[N - i - 1] * nth;
		}

	}
	else if (K == 2) {
		li answer = 0;
		for (int i = 0; i < N; i++) {
			int tmp;
			cin >> tmp;
			arr.push_back(tmp);
			sort(arr.begin(), arr.end());
			answer +=(getRankAndPop(tmp)) * fac[N - i - 1];
		}
		cout << answer+1;

	}

	return 0;
}

M번째 수를 구하는게 아니라 M-1번째로 두고 구해야 답이 나왔다......

 

13251번 조약돌 꺼내기.

뭐하는 문제인지 모르겠다. 그냥 단순 계산이 음 그건 아니고 조합을 이용한 계산이구나.