ehfkswl   2년 전

안녕하세요

코드를 너무 더럽게 짜서 잘 못보실거 같습니다ㅜㅜ

저는 먼저 "=="의 관계를 가진 단항식과 "!="의 관계를 가진 단항식들로 나누어 생각하여 각각의 arraylist집합을 만들었습니다

그리고 그 arraylist 안에 다시 arraylist를 넣어서 disjoint 한 집합의 형태로 각각의 식을 나누었습니다

즉 같은 arraylist안의 element들은 서로서로 동치가 될 수 있으므로 같이 묶어 놓은 것입니다

나중에 출력시 에는 각각의 arraylist 안에서 가장 짧은 길이의 element를 기준으로 하여 나머지 것들을 "==" 기호와 함께 출력을 하였습니다

"!="의 관계를 가진 단항식들은 서로 동치가 될 수 없으므로 arraylist안에 전부 다 넣었습니다

그리고 나중에 출력시 "=="로 만들었던 arraylist에서 같은 집합에 있는 element중 작은 길이의 다른 element값으로 동치가 될 수 있으므로 

길이가 작은 값으로 바꿔 주어 출력하도록 하였습니다

이정도로 구현하면 예제 있는 문제들은 맞습니다

그리고 모순이 되는 예제에는 ("1==2")이 출력되도록, 항상 참이되는 예제의 경우에는 ("1==1")이 출력되도록 하여 output 값이 최대한 작은 길이를 갖도록 하였습니다

제가 각각 모순이 된다고 생각한 예제는 다음과 같습니다

  1. 같은 equal로 묶인 array list안에 두개 이상의 정수가 들어간 경우
  2. "!="의 관계에 있는 두 element값이 똑같을 경우

그리고 항상 참이 된다고 생각한 예제는 다음입니다

  1. equal arraylist안에 하나의 element만 있는 경우(ex, a==a&&b==b) + "!="를 비교할 필요가 없거나 비교 연산이 없는 경우

수정사항) 여러가지 반례들을 스스로 찾아서 고쳤는데 아직도 에러가 납니다 못찾고 있는 부분을 알려주시면 감사하겠습니다

djm03178   2년 전

일단 반례는 다음과 같습니다.

11==11&&a==11

여기서 틀리는 이유는 둘이 완전히 같다면 절대로 equalList에 추가되지 말아야 하는데, 리스트가 완전히 비어있는 경우 161번째 줄에서 무작정 추가를 해버리기 때문입니다.

그래서 46번째 줄을 if (!str1[0].equals(str1[1])) 일 때만 실행해주면 이런 문제는 방지할 수 있습니다.

그러나, 지금의 코드는 O(N^2)에 동작하는 부분이 너무 많습니다. 데이터가 충분히 강력하다면 지금의 구조상으로는 시간 초과를 피할 수 없을 것으로 보입니다.

모든 탐색을 최대 logN 시간에 해낼 수 있는 방법을 강구해 보세요.

ehfkswl   2년 전

친절한 답변 감사드립니다!

말씀하신대로 반례에 대하여 수정을 하니 시간초과 문제가 발생하였습니다

처음부터 다시 짜려고 하는데 혹시 참고할 만한 탐색 알고리즘이 있을까요?

djm03178   2년 전

문제를 푸는 답이 딱 정해져 있는 건 아니겠지만, 저의 경우 disjoint set을 사용했습니다. 어떤 문자열이 어떤 집합에 속했는지는 HashSet 등으로 빠르게 찾을 수 있을 거고요. 각 집합의 모든 원소를 매번 뒤질 필요가 없다는 것이 핵심입니다.

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