글 읽기 - 풀이 방법이 맞는지 봐주십시오.

Viento 5년 전 0

Set ::= "{" Elementlist "}"
Elementlist ::= <empty> | List
List ::= Element | Element "," List
Element ::= Atom | Set
Atom ::= "{" | "}" | ","

조건을 따져서 입력된 문자열이 Set이 될 수 있는지 없는지 확인하는 문제입니다.

Set의 "{" 를 Open, "}" 를 Close, List 사이의 "," 를 Next 라고 본다면

다음 문제는 모든 문자를 Open, Close, Next, Atom 중 하나로 파싱하여 올바르게 파싱되는 지 확인하는 문제인 것 같습니다.

확인 방법은 불필요한 탐색을 피하기 위해 DFS를 이용했구요.

i: i 번째 문자열

depth: 현재 열린 집합의 개수 (Open 만 검출되고 Close는 아직 검출되지 않음)

두 인자를 이용해서

i번째 문자가 상태 x라면, i+1 번째 문자가 상태 y가 될 수 있는지 탐색하였습니다.

x -> y)

Open -> Open, Close, Atom

Close -> Close, Next

Next -> Open, Atom

Atom -> Next, Close

그리고 최후의 문자의 상태가 Close, depth가 0이라면 true를 반환하고

재귀호출에서 true가 반환되면 연이어 true를 반환,

false가 반환되면 다른 상태로 탐색을 시도, 더 이상 탐색할 상태가 없다면 false 반환

을 반복하여 최종적으로 한 케이스라도 문자열의 끝에서 true가 반환되면

집합이 있다고 판단하였습니다.

틀렸다고 나오는데 무엇을 잘못한것인지 찾을수가 없습니다.

#include <iostream>
#include <cstring>
using namespace std;

const int OPEN = 0;
const int CLOSE = 1;
const int NEXT = 2;
const int ATOM = 3;
char str[210] = {0};
int len = 0;

bool next_open(int i, int depth);
bool next_close(int i, int depth);
bool next_atom(int i, int depth);
bool next_next(int i, int depth);

bool next_open(int i, int depth)
{
	int nind = i+1;
	if(i == len-1)
		return false;
	else if(str[nind] == '{' && next_open(nind,depth+1))
		return true;
	else if(depth >0 && str[nind] == '}' && next_close(nind, depth-1))
		return true;
	else if(next_atom(nind, depth))
		return true;
	else
		return false;
}

bool next_close(int i, int depth)
{
	int nind = i+1;
	if(i == len-1 && depth == 0)
		return true;
	else if(str[nind] == ',' && next_next(nind, depth))
		return true;
	else if(depth >0 && next_close(nind, depth-1))
		return true;
	else
		return false;
}
bool next_atom(int i, int depth)
{
	int nind = i+1;
	if(i == len-1)
		return false;
	else if(str[nind] == ',' && next_next(nind, depth))
		return true;
	else if(depth >0 && str[nind] == '}' && next_close(nind, depth-1))
		return true;
	else
		return false;
}
bool next_next(int i, int depth)
{
	int nind = i+1;
	if(i == len-1)
		return false;
	else if(str[nind] == '{' && next_open(nind, depth+1))
		return true;
	else if(next_atom(nind, depth))
		return true;
	else
		return false;
}


void solve(int i)
{
	//str.clear();
	cin >> str;
	len = strlen(str);
	bool ans = str[0] == '{' && next_open(0, 1);
	
	cout <<"Word #" << i << ": ";
	if(!ans)
		cout <<"No ";
	cout<<"Set\n";
}

int main()
{
	int T;
	cin >> T;
	for(int i=0;i<T;i++)
		solve(i);
}

Viento 5년 전 0

이렇게 풀면 시간초과가 날 것 같네요 좀 더 고민해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.