글 읽기 - 15956번 숏코딩 질문입니다. (카카오 페스티벌)

palatable7 4년 전 1

반례를 정상적으로 다 통과합니다.

어떤 반례가 있을 까요?

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>

#include <vector>
#include <cstdio>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define MAX 1000000
char b[MAX];

struct cmp {
	bool operator()(string s1, string s2) {
		int l1 = s1.length();
		int l2 = s2.length();

		if (l1 < l2)
			return true;
		else if (l1 > l2)
			return false;
		else {
			if (s1 > s2)
				return true;
			else if (s1 < s2)
				return false;
			else
				return true;
		}
	}
};

// 단어가 담길 배열
string sarr[MAX];
int sarr_ind;

// == 집합을 저장할 배열
set<string, cmp> eq_set[MAX];
int eq_ind = 1;
unordered_map<string, int> eq_info; // 각 문자열이 어느 집합에 속해있는지

// != 집합 저장할 배열
set<string, cmp> neq_set[MAX];
int neq_ind = 1;

//순서쌍 자료구조
typedef struct D {
	string a, b;

}D;

// == 순서쌍
vector<D> eq_pairs;

// != 순서쌍
vector<D> neq_pairs;

// union
void merge(string x, string y) {

	int l1 = x.length();
	int l2 = y.length();

	// x집합에 y삽입
	if (l1 >= l2) {
		int root_index = eq_info[x];
		int tmp = eq_info[y];
		eq_info[y] = root_index;  // y의 루트번호를 x의 루트번호로.

		// 삽입
		for (auto i = eq_set[tmp].begin(); i != eq_set[tmp].end(); i++) {
			eq_set[root_index].insert(*i);
		}
		eq_info;
		eq_set[tmp].clear(); // 기존 것 비우기
	}
	// y집합에 x삽입
	else {
		int eq_index = eq_info[y];
		int tmp = eq_info[x];
		eq_info[x] = eq_index;

		// 삽입
		for (auto i = eq_set[tmp].begin(); i != eq_set[tmp].end(); i++) {
			eq_set[eq_index].insert(*i);
		}

		eq_set[tmp].clear();
	}
}

bool isDigit(string str) {
	return (atoi(str.c_str()) != 0) || (str.compare("0") == 0);
}

unordered_map<string, string> stored_pair;

int main() {
	string sol = "";

	string s;
	cin >> s;
	int len = s.length();
	strcpy(b, s.c_str());

	char * p = strtok(b, "==!=&&");
	while (p != NULL) {
		sarr[sarr_ind++] = p;
		p = strtok(NULL, "==!=&&");
	}

	// 1. ==집합, != 집합
	int arr_index = 0;
	// 집합에 넣었던 것은 반복금지
	unordered_map<string, int> eq_check;
	unordered_map<string, int> neq_check;

	unordered_map<string, int> eq_check_recur;
	unordered_map<string, int> neq_check_recur;

	for (int i = 0; i < len; i++) {
		if (s[i] == '=') {
			string s1 = sarr[arr_index++];
			string s2 = sarr[arr_index++];

			// 이미 집합에 존재하는 쌍 이거나, 같은 값인 경우 pass
			string a = s1 + "==" + s2;
			string b = s2 + "==" + s1;
			if (eq_check_recur[a] == 1 || eq_check_recur[b] == 1 || s1 == s2) {
				i++;
				continue;
			}
			eq_check_recur[a] = 1;

			eq_pairs.push_back({ s1, s2 });

			if (eq_check[s1] == 0) {
				eq_check[s1] = 1;
				eq_set[eq_ind].insert(s1);
				eq_info[s1] = eq_ind++;
			}
			
			if (eq_check[s2] == 0) {
				eq_check[s2] = 1;
				eq_set[eq_ind].insert(s2);
				eq_info[s2] = eq_ind++;
			}
			

			i++;
		}
		else if(s[i] == '!'){
			string s1 = sarr[arr_index++];
			string s2 = sarr[arr_index++];

			// 정수이면서 서로 다른 값인 경우 pass
			if (isDigit(s1) && isDigit(s2)) {
				int i1 = atoi(s1.c_str());
				int i2 = atoi(s2.c_str());
				if (i1 != i2)
					continue;
			}

			// 모순
			if (s1 == s2) {
				cout << "1==0\n";
				return 0;
			}

			// 이미 집합에 존재하는 쌍 pass
			string a = s1 + "!=" + s2;
			string b = s2 + "!=" + s1;
			if (neq_check_recur[a] == 1 || neq_check_recur[b] == 1) {
				i++;
				continue;
			}
			neq_check_recur[a] = 1;

			neq_pairs.push_back({ s1, s2 });
			if (neq_check[s1] == 0) {
				neq_check[s1] = 1;
				neq_set[neq_ind].insert(s1);
			}

			if (neq_check[s2] == 0) {
				neq_check[s2] = 1;
				neq_set[neq_ind].insert(s2);
			}

			i++;
		}
	}

	// 2. merge('=='집합 대상)
	// eq_set[번호] : 집합 / eq_info[string] = int : 집합 번호 / eq_pqir[string] : 순서쌍 
	unordered_map<string, int> eq_check_r; // 중복 체크

	for (auto i = eq_pairs.begin(); i != eq_pairs.end(); i++) {
		string s1 = i->a;
		string s2 = i->b;

		int set1_ind = eq_info[s1];
		int set2_ind = eq_info[s2];

		string leader1 = s1;
		string leader2 = s2;

		if(!eq_set[set1_ind].empty())
			leader1 = *eq_set[set1_ind].begin();
		if(!eq_set[set2_ind].empty())
			leader2 = *eq_set[set2_ind].begin();

		// 이미 집합에 있는 값이거나 같은 값인 경우 pass
		string a = leader1 + "==" + leader2;
		string b = leader2 + "==" + leader1;
		if (eq_check_r[a] == 1 || eq_check_r[b] == 1 || leader1==leader2) {
			continue;
		}
		eq_check_r[a] = 1;

		merge(leader1, leader2);
		eq_set;
	}

	// 3. 그룹 순회
	for (int i = 1; i < eq_ind; i++) {
		// 비어 있으면 pass
		if (eq_set[i].empty())
			continue;

		// 나머지 check
		// 모순인 경우 			
		// 모순 : 한 그룹에 정수 2개 이상
		int digit_cnt = 0;
		int go = 0;
		string leader;
		for (auto iter = eq_set[i].begin(); iter != eq_set[i].end(); iter++) {
			string ss = *iter;
			if (go++ == 0)
				leader = ss;

			if (isDigit(ss))
				digit_cnt++;
			if (digit_cnt == 2) {
				cout << "1==0\n";
				return 0;
			}

			// 모순이 아닌 경우
			if (leader == ss)
				continue;
			sol += leader + "==" + ss + "&&";
		}
	}

	// 4. != 처리
	// a!=b&&c!=d&&1!=b&&1!=c
	unordered_map<string, int> ch;
	for (auto iter = neq_pairs.begin(); iter != neq_pairs.end(); iter++) {
		string s1 = iter->a;
		string s2 = iter->b;

		// 대표 부르기
		int i1 = eq_info[s1];
		int i2 = eq_info[s2];
		eq_set;

		string l1 = s1;
		string l2 = s2;

		// 대표가 있을 경우
		if(!eq_set[i1].empty())
			l1 = *eq_set[i1].begin();
		if(!eq_set[i2].empty())
			l2 = *eq_set[i2].begin();

		if (l1 == l2) {
			cout << "1==0\n";
			return 0;
		}

		// 이미 입력한 값은 pass
		string a = l1 + "!=" + l2;
		string b = l2 + "!=" + l1;
		if (ch[a] == 1 || ch[b] == 1)
			continue;
		ch[a] = 1;

		sol += l1 + "!=" + l2 + "&&";
	}

	if (sol == "") {
		cout << "1==1\n";
		return 0;
	}

	int len2 = sol.length();
	sol = sol.substr(0, len2- 2);

	cout << sol << '\n';
}

bupjae 4년 전 1

입력: a==111&&b==111&&c==111

오답: b==a&&b==111

정답 (예): b==a&&b==c&&b==111

palatable7 4년 전 0

한 시간 넘게 찾았는데 드디어.. 반례 감사합니다

palatable7 4년 전 0

a==111&&b==111&&c==111

이 반례도 제대로 나오게끔 수정 했습니다.

문제가 merge할 때 제대로 집합을 구분하지 못한 것에 있었습니다.

하지만 아직도 17%정도에서 틀렸습니다가 뜨는데, 어떤것이 반례가 또 있을까요?

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define MAX 1000
char b[MAX];

struct cmp {
	bool operator()(string s1, string s2) {
		int l1 = s1.length();
		int l2 = s2.length();

		if (l1 < l2)
			return true;
		else if (l1 > l2)
			return false;
		else {
			if (s1 > s2)
				return true;
			else if (s1 < s2)
				return false;
			else
				return true;
		}
	}
};

// 단어가 담길 배열
string sarr[MAX];
int sarr_ind;

// == 집합을 저장할 배열
set<string, cmp> eq_set[MAX];
int eq_ind = 1;
unordered_map<string, int> eq_info; // 각 문자열이 어느 집합에 속해있는지

// != 집합 저장할 배열
set<string, cmp> neq_set[MAX];
int neq_ind = 1;

//순서쌍 자료구조
typedef struct D {
	string a, b;

}D;

// == 순서쌍
vector<D> eq_pairs;

// != 순서쌍
vector<D> neq_pairs;

// union
void merge(string x, string y) {

	int l1 = x.length();
	int l2 = y.length();

	// x집합에 y삽입
	if (l1 <= l2) {
		int root_index = eq_info[x];
		int tmp = eq_info[y];
		eq_info[y] = root_index;  // y의 루트번호를 x의 루트번호로.

		// 삽입
		for (auto i = eq_set[tmp].begin(); i != eq_set[tmp].end(); i++) {
			eq_set[root_index].insert(*i);
			eq_info[*i] = root_index;
		}
		eq_info;
		eq_set[tmp].clear(); // 기존 것 비우기
	}
	// y집합에 x삽입
	else {
		int eq_index = eq_info[y];
		int tmp = eq_info[x];
		eq_info[x] = eq_index;

		// 삽입
		for (auto i = eq_set[tmp].begin(); i != eq_set[tmp].end(); i++) {
			eq_set[eq_index].insert(*i);
			eq_info[*i] = eq_index;
		}

		eq_set[tmp].clear();
	}
}

bool isDigit(string str) {
	return (atoi(str.c_str()) != 0) || (str.compare("0") == 0);
}

unordered_map<string, string> stored_pair;

int main() {
	string sol = "";

	string s;
	cin >> s;
	int len = s.length();
	strcpy(b, s.c_str());

	char * p = strtok(b, "==!=&&");
	while (p != NULL) {
		sarr[sarr_ind++] = p;
		p = strtok(NULL, "==!=&&");
	}

	// 1. ==집합, != 집합
	int arr_index = 0;
	// 집합에 넣었던 것은 반복금지
	unordered_map<string, int> eq_check;
	unordered_map<string, int> neq_check;

	unordered_map<string, int> eq_check_recur;
	unordered_map<string, int> neq_check_recur;

	for (int i = 0; i < len; i++) {
		if (s[i] == '=') {
			string s1 = sarr[arr_index++];
			string s2 = sarr[arr_index++];

			// 이미 집합에 존재하는 쌍 이거나, 같은 값인 경우 pass
			string a = s1 + "==" + s2;
			string b = s2 + "==" + s1;
			if (eq_check_recur[a] == 1 || eq_check_recur[b] == 1 || s1 == s2) {
				i++;
				continue;
			}
			eq_check_recur[a] = 1;

			eq_pairs.push_back({ s1, s2 });

			if (eq_check[s1] == 0) {
				eq_check[s1] = 1;
				eq_set[eq_ind].insert(s1);
				eq_info[s1] = eq_ind++;
			}
			
			if (eq_check[s2] == 0) {
				eq_check[s2] = 1;
				eq_set[eq_ind].insert(s2);
				eq_info[s2] = eq_ind++;
			}
			

			i++;
		}
		else if(s[i] == '!'){
			string s1 = sarr[arr_index++];
			string s2 = sarr[arr_index++];

			// 정수이면서 서로 다른 값인 경우 pass
			if (isDigit(s1) && isDigit(s2)) {
				int i1 = atoi(s1.c_str());
				int i2 = atoi(s2.c_str());
				if (i1 != i2)
					continue;
			}

			// 모순
			if (s1 == s2) {
				cout << "1==0" << '\n';
				return 0;
			}

			// 이미 집합에 존재하는 쌍 pass
			string a = s1 + "!=" + s2;
			string b = s2 + "!=" + s1;
			if (neq_check_recur[a] == 1 || neq_check_recur[b] == 1) {
				i++;
				continue;
			}
			neq_check_recur[a] = 1;

			neq_pairs.push_back({ s1, s2 });
			if (neq_check[s1] == 0) {
				neq_check[s1] = 1;
				neq_set[neq_ind].insert(s1);
			}

			if (neq_check[s2] == 0) {
				neq_check[s2] = 1;
				neq_set[neq_ind].insert(s2);
			}

			i++;
		}
	}

	// 2. merge('=='집합 대상)
	// eq_set[번호] : 집합 / eq_info[string] = int : 집합 번호 / eq_pqir[string] : 순서쌍 
	unordered_map<string, int> eq_check_r; // 중복 체크

	for (auto i = eq_pairs.begin(); i != eq_pairs.end(); i++) {
		string s1 = i->a;
		string s2 = i->b;

		int set1_ind = eq_info[s1];
		int set2_ind = eq_info[s2];

		string leader1 = s1;
		string leader2 = s2;

		if(!eq_set[set1_ind].empty())
			leader1 = *eq_set[set1_ind].begin();
		if(!eq_set[set2_ind].empty())
			leader2 = *eq_set[set2_ind].begin();

		// 이미 집합에 있는 값이거나 같은 값인 경우 pass
		string a = leader1 + "==" + leader2;
		string b = leader2 + "==" + leader1;
		if (eq_check_r[a] == 1 || eq_check_r[b] == 1 || leader1==leader2) {
			continue;
		}
		eq_check_r[a] = 1;

		merge(leader1, leader2);
		eq_set;
	}

	// 3. 그룹 순회
	for (int i = 1; i < eq_ind; i++) {
		// 비어 있으면 pass
		if (eq_set[i].empty())
			continue;

		// 나머지 check
		// 모순인 경우 			
		// 모순 : 한 그룹에 정수 2개 이상
		int digit_cnt = 0;
		int go = 0;
		string leader;
		for (auto iter = eq_set[i].begin(); iter != eq_set[i].end(); iter++) {
			string ss = *iter;
			if (go++ == 0)
				leader = ss;

			if (isDigit(ss))
				digit_cnt++;
			if (digit_cnt == 2) {
				cout << "1==0" << '\n';
				return 0;
			}

			// 모순이 아닌 경우
			if (leader == ss)
				continue;
			sol += leader + "==" + ss + "&&";
		}
	}

	// 4. != 처리
	// a!=b&&c!=d&&1!=b&&1!=c
	unordered_map<string, int> ch;
	for (auto iter = neq_pairs.begin(); iter != neq_pairs.end(); iter++) {
		string s1 = iter->a;
		string s2 = iter->b;

		// 대표 부르기
		int i1 = eq_info[s1];
		int i2 = eq_info[s2];

		string l1 = s1;
		string l2 = s2;

		// 대표가 있을 경우
		if(!eq_set[i1].empty())
			l1 = *eq_set[i1].begin();
		if(!eq_set[i2].empty())
			l2 = *eq_set[i2].begin();

		if (l1 == l2) {
			cout << "1==0" << '\n';
			return 0;
		}

		// 이미 입력한 값은 pass
		string a = l1 + "!=" + l2;
		string b = l2 + "!=" + l1;
		if (ch[a] == 1 || ch[b] == 1)
			continue;
		ch[a] = 1;

		sol += l1 + "!=" + l2 + "&&";
	}

	if (sol == "") {
		cout << "1==1" << '\n';
		return 0;
	}

	int len2 = sol.length();
	sol = sol.substr(0, len2- 2);

	cout << sol << '\n';
}

bupjae 4년 전 1

MAX 값이 갑자기 줄어들었습니다.

이 문제는 최대 입력 크기가 1000000 글자인데, 108번째 줄에서 크기 1000 인 배열로 문자열을 복사하고 있습니다.

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

문제

문제

출처

ICPC

15956번 숏코딩 질문입니다. (카카오 페스티벌)

palatable7 4년 전 1

bupjae 4년 전 1

palatable7 4년 전 0

palatable7 4년 전 0

bupjae 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말