HackerRank - Between Two Sets

인수분해 관련 문제.

www.hackerrank.com/challenges/between-two-sets/problem?h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen

 

첫번째 문제 봉착.

우선, 문제를 이해하는데 40분이 넘게 걸렸다.;;;;

문제를 요약하면 이렇다.

 

a, b 정수 리스트가 주어질 것이다.

b 리스트의 요소들의 공통 약수를 먼저 찾는다. 그리고 그 약수들을 a 리스트의 항목들로 나누었을 때 모든 a리스트의 요소들에 대한 나머지가 0인 약수의 갯수를 리턴하는 문제이다.

 

와....이거를 진짜..예문봐도 이해도 안가고. 설명을 왜 저렇게 해놔서...;;;;; ㅜㅠㅜㅠ

약수 그려놓고 추측해가면서 답을 맞춰가다보니 문제가 이해가 됐다. 와...이런걸 코테로 주면 진짜 난감할거 같네..;;;

아마도 a -> b 형식의 관계를 설명하려다 보니 저런거 같다.

 

두번째 문제 봉착.

약수를 구하는 함수..???

어...이거를 생각해본적이 없던터라 한참 고민을 한것 같다.

스마트 한 방법이 생각나지 않아 짱구를 굴린게 음....우선 b 리스트가 오름차순으로 정렬되어 들어온다.

즉...첫번째 요소의 약수만 구해놓으면 두번째부터는 그 약수만 가지고 다음 요소의 약수가 되는지 아닌지만 판단하며 삭제해나가면 된다.

삭제요소가 많아 질수록, 큰수에서는 오히려 반복횟수가 줄어든다.

 

그렇게 모든 b리스트 요소의 공통 약수를 뽑아두고(c), 다시 a리스트과 비교한다.

c 반복을 바깥에 두고, a 반복을 안에 둔다. 그리고 a 요소 중 하나라도 c 의 약수가 아니면 c에서 해당 값을 제외하고 break문으로 a 반복문을 빠져나가버리고 다시 c반복문으로 돌아간다.

 

그렇게 남은 c 리스트의 갯수를 리턴. 끝...

최적화는...글쎄 다음에 고민을...문제 이해하는데 시간을 너무 잡아먹어서...ㅜㅠ