글 읽기 - [java]반례를 못찾겠습니다.

tnwls0529 4년 전 0

먼저 질문 게시판에 올라온 반례는 다 테스트 해보았습니다.

테스트 해본 것들은 아래와 같습니다.

1. a!=b&&b!=a 와 같이 겹치는 것이 있는 경우

=> a!=b

2. a!=b&&b==c&&c!=a 와 같이 ==의 조건에 의해 != 조건이 지워질 수 있는 경우

=> b==c&&a!=b

3. 11!=1 와 같이 숫자!=숫자인 경우

=> 1==1

4. a==1&&a==2 와 같이 한 그룹에 숫자가 2개 이상 있는 경우

=> 1!=1

5. festival==2018&&festival!=a 와 같이 != 조건의 단항식이 더 짧은 식으로 바뀌는 경우

=> 2018==festival&&2018!=a

6. festival==2018&&festival==kakao&&2018!=kakao 와 같이 수식이 참이 되지 않는 경우

=> 1!=1

어떤 것 때문에 틀렸는지 전혀 감이오지 않아서, 어떤 조건을 더 테스트해야하는지 모르겠습니다...

도와주세요!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;

public class Main {
	// 숏코딩 문제임

	static class Length_sort implements Comparator {
		// 비교 기준 객체 만들기 위해서

		@Override
		public int compare(Object o1, Object o2) {
			// TODO Auto-generated method stub
			String s1 = (String) o1;
			String s2 = (String) o2;
			if (s1.length() > s2.length()) {
				return 1;
			} else if (s1.length() < s2.length()) {
				return -1;
			} else {
				return 0;
			}

		}

	}

	static boolean isDigit(String s) {
		// 정수인지 확인하는 함수
		boolean result = true;
		for (int j = 0; j < s.length(); j++) {
			char _temp = s.charAt(j);
			if (j == 0 && _temp == '-') {
				// 음수의 경우도 고려할 수 있도록 하기 위해서 아무 동작은 하지 않지만 경우를 나누어 놓음.
			} else if ('0' > _temp || _temp > '9') {
				result = false;
			}

		}
		return result;
	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String input = br.readLine();
			// Set<String> management_2 = new HashSet<String>();
			String _value[] = input.split("&&"); // &&으로 쪼개기
			String value[][] = new String[_value.length][2]; // == != 으로 쪼갰을 때 저장할 배열
			Set<String> management[] = new HashSet[_value.length * 2]; // 관리용 배열
			ArrayList<String> management2[] = new ArrayList[_value.length * 2]; // 정렬하고나서는 여기로 넘길 것임.

			Set<String> same = null; // 같은 애들 모아서 넣을 것
			LinkedList<Integer> digit = null; // 숫자인 애들 모아서 넣을 것

			br.close();

			int manage_index = -1;
			for (int i = 0; i < _value.length; i++) {
				if (_value[i].contains("==")) {
					value[i] = _value[i].split("==");
					if (manage_index == -1) {
						// 우선 만들어지지도 않은 것.
						manage_index++;
						same = new HashSet<String>();
						same.add(value[i][0]);
						same.add(value[i][1]);
						management[manage_index] = same;
					} else {
						int check = 0; // 1이면 추가하고 나온 거
						for (int k = 0; k <= manage_index; k++) {
							Iterator<String> iter = management[k].iterator();
							while (iter.hasNext()) {
								String temp = (String) iter.next();
								if (value[i][0].equals(temp) || value[i][1].equals(temp)) {
									management[k].add(value[i][0]);
									management[k].add(value[i][1]);
									check = 1;
									break;
								}
							}

						}
						if (check == 0) {
							manage_index++;
							same = new HashSet<String>();
							same.add(value[i][0]);
							same.add(value[i][1]);
							management[manage_index] = same;
						}
					}
				}
			}

			for (int i = 0; i <= manage_index; i++) {
				// 길이에 대해서 모든 same set 정렬
				ArrayList<String> temp = new ArrayList(management[i]);
				Collections.sort(temp, new Length_sort());
				management2[i] = temp;
			}

			for (int i = 0; i <= manage_index; i++) {
				Iterator<String> iter = management2[i].iterator();
				digit = new LinkedList<Integer>();
				while (iter.hasNext()) {
					String temp = iter.next();
					if (isDigit(temp)) {
						digit.add(Integer.parseInt(temp));
					}
				}
				if (digit.size() > 0) {
					LinkedList<Integer> compare_digit = new LinkedList<Integer>();
					for (int _digit = 0; _digit < digit.size(); _digit++) {
						compare_digit.add(digit.get(0));
					}
					if (!digit.equals(compare_digit)) {
						// 둘이 모두 같지 않다면 같지않은 정수가 있다는 의미이므로 그냥 false
						System.out.println("1!=1");
						System.exit(0); // 종료
					}
				}
			}
			// 같은 것에 대해서 정수 확인까지 끝

			for (int i = 0; i < _value.length; i++) {
				if (_value[i].contains("==")) {

				} else {
					// != 인 것임.
					value[i] = _value[i].split("!=");
					for (int k = 0; k <= manage_index; k++) {
						Iterator<String> iter = management2[k].iterator();
						while (iter.hasNext()) {
							String temp = (String) iter.next();
							if (value[i][0].equals(temp)) {
								value[i][0] = management2[k].get(0); // 가장 짧은 것으로 바꾸어줌
							}
							if (value[i][1].equals(temp)) {
								value[i][1] = management2[k].get(0);
							}
						}
					}
					_value[i] = value[i][0] + "!=" + value[i][1];
				}
			}
			// 짧은 애들로 수정

			int restore = manage_index;
			for (int i = 0; i < manage_index; i++) {
				for (int j = i + 1; j <= manage_index; j++) {
					// 교집합인 경우에 합치는 과정 필요!!!!
					Iterator<String> iter = management[i].iterator();
					Set<String> temp = new HashSet<String>();
					while (iter.hasNext()) {
						temp.add(iter.next());
					}
					if (!temp.isEmpty()) {
						if (management[j] == null) {
							break;
						}
						temp.retainAll(management[j]);
						if (!temp.isEmpty()) {
							// 교집합이 있으면
							iter = management[j].iterator();
							while (iter.hasNext()) {
								management[i].add(iter.next());
							}
							if (j + 1 <= manage_index && management[j + 1] != null) {
								management[j] = management[j + 1];
								management[j + 1] = null;
							} else {
								management[j] = null;
							}
							restore--;
						}
					}
				}
			}
			manage_index = restore;

			for (int i = 0; i <= manage_index; i++) {
				// 길이에 대해서 모든 same set 정렬
				ArrayList<String> temp = new ArrayList(management[i]);
				Collections.sort(temp, new Length_sort());
				management2[i] = temp;
			}

			for (int i = 0; i < _value.length; i++) {
				// 같지 않다인데 같은 애들이면 그냥 false
				if (_value[i].contains("!=")) {
					String temp[] = _value[i].split("!=");
					if (temp[0].equals(temp[1])) {
						System.out.println("1!=1");
						System.exit(0);
					} else {
						if (isDigit(temp[0]) && isDigit(temp[1])) {
							_value[i] = "1==1";
						}
					}
				}

			}

			for (int i = 0; i < _value.length - 1; i++) {
				for (int j = i + 1; j < _value.length; j++) {
					if (_value[i].equals(_value[j]) && _value[i] != "") { // 예를 들면 b!=c 가 있는데 b!=c가 또 있는 형태
						_value[j] = "";
					} else if (_value[i].contains("!=")) {
						String temp[] = _value[i].split("!=");
						String reuse = temp[1] + "!=" + temp[0]; // 예를 들면 b!=c 가 있는데 c!=b인 형태
						if (reuse.equals(_value[j])) {
							_value[j] = "";
						}
					}

				}
			}
			String result = "";

			for (int i = 0; i <= manage_index; i++) {
				Iterator<String> iter = management2[i].iterator();
				String mid = iter.next();
				if (result != "") {
					result += "&&";
				}
				while (iter.hasNext()) {
					result += mid + "==" + iter.next();
					if (iter.hasNext()) {
						result += "&&";
					}
				}

			}
			for (int i = 0; i < _value.length; i++) {
				if (_value[i].contains("!=")) {
					if (result != "") {
						result += "&&";
						result += _value[i];
					} else {
						result += _value[i];
					}
				}
			}
			if (result == "") {
				result = "1==1";
			}
			System.out.println(result);

		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

}

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

문제

문제

출처

ICPC

[java]반례를 못찾겠습니다.

tnwls0529 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말