ljjk159   4년 전

우선 질문 게시판에 있던 테스트 케이스들은 모두 통과했습니다.

==으로 연결되어 있는 변수와 상수는 disjoint set으로 묶어주고 다음과 같은 방식으로 문제에 접근했습니다.

0. 자료구조 : 

 vector<string> str; index에 따른 string을 저장합니다.

vector<int> root; 각 집합의 root index를 저장합니다. root index인 경우, 그 집합에서 문자열의 길이가 가장 짧은 string의 index를 i라 하면, -i를 저장합니다. 

 unordered_map <string, int> eeq; string에 따른 유일한 index를 저장합니다.

 set<pair<int, int>> neq; 처음 input을 받을 때 !=로 연결된 pair들을 저장합니다.

 vector<bool> isThereDigit;  각 집합의 root index에 그 집합에 숫자가 포함되었는지 여부를 저장합니다.

 set<pair<int, int>> visit; input을 모두 받은 후 neq 집합에서 중복되는 pair를 제외하고 저장합니다

  1. ==인 경우 양 변이 다른 경우 union 함수로 합집합을 만들어줍니다. 만약 양변의 두 set에 모두 숫자가 포함되어 있는 경우 1!=1을 출력하고 exit(0)으로 프로그램을 바로 종료합니다. (뒤의 인풋 무시) (set_union의 로직입니다.)
  2. !=인 경우 우선 양 변이 같은 집합에 속해있는지 검사하여 같은 집합인 경우 1!=1을 출력하고 종료합니다. 두 set에 숫자가 포함된 경우, 1!=2와 같이 항상 true이므로 무시해줍니다. 이외의 경우에는 neq에 두 집합의 root pair(r1, r2)를 저장합니다. (set_add_neq의 로직입니다.)
  3. input을 모두 받은 이후, neq에 있는 pair들을 모두 검사하여 중복을 제거하고 visit에 저장합니다. (set_process_neq) 같은 집합에 있는 두 원소가 !=로 연결되어 있는 경우, 1!=1을 출력하고 종료합니다. 그리고 두 집합에 모두 숫자가 포함된 경우는 visit에 저장하지 않습니다. root index가 작은 것을 왼쪽에 저장하여 중복이 생기지 않게 했습니다.
  4. 이후 union 연산이 없었거나, visit에 저장된 pair가 없는 경우는 모든 식이 true라는 의미이므로 1==1을 출력하고 종료합니다.
  5. 이외의 경우는 우선 visit에 저장된 pair들을 모두 출력한 후, union으로 묶인 집합들을 모두 출력합니다.

우선 난잡한 논리 흐름과 설명 읽어주셔서 감사드리고, 이외에도 많은 test case를 만들어서 해봤는데도 반례를 찾지 못했습니다.. 이 문제만 5일째 붙잡고 매달리고 있는데 도움 주시면 정말정말정말 감사하겠습니다..

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