gkfkagkfka12   2년 전

어떻게 접근해야 할지 모르겠습니다.

카카오 홈페이지에서 주는 공식 풀이도 이해를 못하겠는데... dfs로 푸는 문제인가요?

접근방법이라도 주시면 감사하겠습니다.

djm03178   2년 전

맞은 사람 수에도 나오듯이, 어려운 문제였습니다. 맞은 사람들의 코드 길이를 봐도, 3000바이트 아래의 정답 코드가 거의 없을 정도로 구현도 복잡합니다.

기본적으로는 이런 자료구조를 만들어 내면 됩니다.

  1. "==" 관계인 것들끼리 집합을 만듭니다. 예를 들면 저는 disjoint set을 구현했습니다.
  2. 각 집합에는 그 집합을 대표하는 "대장"이 있습니다. "대장"이란 그 집합에서 가장 길이가 짧은 단항식을 말합니다.
  3. 하나의 집합에는 둘 이상의 서로 다른 정수가 있으면 안 됩니다. 어떤 집합에 어떤 정수 값이 이미 들어가 있다면, 그 집합에 새로운 정수를 추가하려는 건 무조건 거짓이 됩니다.
  4. "!=" 관계는 두 집합을 연결합니다. 서로 다른 두 집합 사이에는 둘 이상의 "!=" 관계가 있을 수 없습니다. "!=" 관계를 출력할 때는 각 집합의 "대장"들만 출력하면 됩니다.
  5. 같은 집합에 속한 단항식끼리 "!=" 관계가 있다면 전체 문장은 거짓입니다.

djm03178   2년 전

특별히 어떤 방법으로 풀어야 한다고 정해져있기보다는, 문제에서 정하는 여러 조건들을 잘 정리해서 그에 맞는 자료구조와, 필요한 연산들을 구현해내는 게 중요한 것 같습니다. 

gkfkagkfka12   2년 전

항상 친절한 답변 너무 감사드립니다. Disjoint set은 상당히 좋은 아이디어네요! 

지금 당장 짜볼 수는 없지만 내일 짜보고 어려운 점이 있으면 다시 댓글 남기겠습니다.

감사합니다.

gkfkagkfka12   2년 전

@djm03178님 각 문자열을 파싱해서 disjoint set을 만들어보려고 했는데 인덱스 값이 숫자인데 어떤식으로 구현해야 되나요? 아예 string 배열로 빼서 따로 따로 해야되나요 아니면 map을 써야 할까요? 

djm03178   2년 전

저는 map을 썼습니다.

gkfkagkfka12   2년 전

저도 map을 써서 구현했습니다. 근데 예제에서 int==float가 float==int가 되도 상관없는거 맞나요?

djm03178   2년 전

둘이 같은 식이고 길이도 같으니 상관 없죠.

gkfkagkfka12   2년 전

제 허졉한 코드에서 뭐가 문젠지 알려주실수있나요 ㅠㅠ 노력은 해봤는데 계속 틀리네여...

djm03178   2년 전

1==2&&a==a

는 무조건 거짓이므로 1==0 등을 출력해야 합니다.

gkfkagkfka12   2년 전

수정했는데 그래도 틀리네요 ...ㅠ 게시글 수정했습니다.

ehfkswl   2년 전

djm03178님 가능하시면 위에 제코드도 봐주시면 감사하겠습니다

djm03178   2년 전

위가 어디인가요

ehfkswl   2년 전

15956번 문제에 대하여 따로 모아놓은 질문 글 중 이글 다음에 있는 것입니다!!

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