HackerRank - Beautiful Pairs

www.hackerrank.com/challenges/beautiful-pairs/problem

Beautiful Pairs | HackerRank

이것도 문제이해가 어려웠다. 아....진짜 문제이해가 쉽게 안되는 문제가 진짜 짜증난다. 영어공부를 해야하는건지..;;;;

틀리고 틀린 입력값과 결과값을 가지고 유추한 뒤 다시 풀고 나서 지문을 보면 이해가 되니..;;;;

문제를 탓할 순 없겠지. 영어를 제대로 해석해내고 이해하지 못하는 나의 문제인거지...ㅜㅜ

 

문제. 두가지 int형의 값이 담긴 같은 길이의 배열 a, b가 주어진다. 두 배열 간 중복되는 값을 가진 각각의 위치 index를 (i, j) 한 쌍으로 보고 모든 중복되는 경우를 구하여 나열한다. 그렇게 위치index 한 쌍의 목록이 생성되게 되는데....

목록 내부의 값 중 i값이 중복되거나 j값이 중복되는 경우를 제외시킨다. (예를 들어 (1, 2), (1, 3) 은 함께 존재할 수 없고 별도로 존재해야 한다.)

결과 목록이 (A, B, C, D)라고 할 때 C와 D가 i 또는 j가 중복될 경우 결과 목록은 (A, B, C) or (A, B, D)로 존재해야 한다. 이때 꼭 b의 항목 중 1개를 수정해서 가장 큰 목록 길이가 생기도록 해야한다.

 

자. 엄청 복잡해 보인 이 문제가 왜 난이도가 쉬움일까...

포인트 1. 중복건을 분리하여 별도의 결과목록으로 나열해야 한다는건 결국, a배열을 기준으로 b에도 같은 값이 존재하는 건수가 현재 상태의 가장 긴 결과목록의 길이가 된다. 왜??

1, 2, 3, 4

1, 2, 3, 3

이 두가지의 배열을 보면 (0, 0), (1, 1), (2, 2), (2, 3) 이런 결과목록이 나오고 배열 요소 내 인덱스가 중복이 있으니 아래와 같은 경우로 나와야 한다.

1 - (0, 0), (1, 1), (2, 2)

2 - (0, 0), (1, 1), (2, 3)

 

더 극단적으로..

1, 2, 3, 4

1, 1, 2, 2

=> (0, 0), (0, 1), (1, 2), (1, 3)

-> (0, 0), (1, 2) / (0, 0), (1, 3) / (0, 1), (1, 2) / (0, 1), (1, 3) 이렇게 네가지 경우로 나오는데 모두 길이가 2이다.

즉, a와 b의 교집합 안에 들어오는 건수만 체크를 하면 현 상태에서 최고의 사이즈가 나오게 된다.

그리고 중요한 포인트. 무조건 b의 값 하나를 수정해야 한다.

두가지 경우가 생길 수 있다. 

1. 두 배열의 차집합이 존재하는 경우 : 최고의 결과목록 길이는 배열의 길이보다 짧다. b의 차집합의 항목 중 하나를 나머지 a의 차집합 항목 중 하나와 같게 만들면 배열의 길이가 +1이 된다.

2. 두 배열의 차집합이 존재하지 않는 경우.(모든 원소가 완전히 동일한 경우) : 최고의 결과목록 길이는 배열의 길이와 같다. 이미 매치된 항목 중 하나를 변경해야 함으로 결과목록의 길이가 무조건 -1이 된다.

 

내가 간과했던 부분.

1. 교집합의 건수로 봐야한다는 부분을 지문을 보고서 이해하지 못했다.;;;;;;(이게 너무 크다...아이구...ㅜㅜ)

2. 1번의 문제를 이해하고 봤다면 좀 더 경우의 수를 확인하기 쉬웠을텐데, 적절한 테스트 케이스를 생각하지 못했다.(바로 위의 2번 같은 경우...a와 b가 서로 동일한 집합임을 고려하지 못했다.)

 

다시한번, [Input Format]을 잘 읽어보자. 주어진 문제의 조건을 좀 더 디테일하게 규정할 힌트가 숨어있다.(이번 문제에서는 두 배열의 길이가 같다는 부분...), 그리고 [Note]도 잘 읽어보자. 중요하니까 노트겠지....(b는 꼭 1개를 수정해야 한다는....)