Google Foo Bar Challenge Level 3 #3

Find the Access Codes
=====================

In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need access to it. But the only door leading to the LAMBCHOP chamber is secured with a unique lock system whose number of passcodes changes daily. Commander Lambda gets a report every day that includes the locks' access codes, but only the Commander knows how to figure out which of several lists contains the access codes. You need to find a way to determine which list contains the access codes once you're ready to go in. 

Fortunately, now that you're Commander Lambda's personal assistant, Lambda has confided to you that all the access codes are "lucky triples" in order to make it easier to find them in the lists. A "lucky triple" is a tuple (x, y, z) where x divides y and y divides z, such as (1, 2, 4). With that information, you can figure out which list contains the number of access codes that matches the number of locks on the door when you're ready to go in (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky triple" access codes).

Write a function solution(l) that takes a list of positive integers l and counts the number of "lucky triples" of (li, lj, lk) where the list indices meet the requirement i < j < k.  The length of l is between 2 and 2000 inclusive.  The elements of l are between 1 and 999999 inclusive.  The solution fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0. 

For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the solution 3 total.

Languages
=========

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Java cases --
Input:
Solution.solution([1, 1, 1])
Output:
    1

Input:
Solution.solution([1, 2, 3, 4, 5, 6])
Output:
    3

-- Python cases --
Input:
solution.solution([1, 2, 3, 4, 5, 6])
Output:
    3

Input:
solution.solution([1, 1, 1])
Output:
    1

 

풀이

어째서인지 Level 3가 레벨 2보다 쉬운 것 같다.

 

처음 떠오른 건 리스트 L의 원소들을 나눌 수 있는 관계로 서로 표시하면, 그래프가 된다는 것.

그런데 그렇게까지 가지 않더라도, 

[1, 2, 3, 4, 5, 6, 7, 8]을 시뮬레이션 해 보면 ->

1 2 3 4 5 6 7 8

x 1 1 1 1 1 1 1

x x x 2 x 2 x 2

x x x x x 3 x x 

x x x x x x x 4

로 나누어 떨어지므로,

이 정보를 이용하면 될 듯하다.

 

처음엔 "j<i이고 L[i] % L[j] == 0인 j의 수"를 구하고 해당 수로 만들 수 있는 가능한 2-tuple의 조합 수가 답일 거라 생각했었는데, 이건 L[j1]이 L[j2]를 못 나누는 경우를 고려하지 않았었다.

 

사고를 더 정리해보면, 어떤 수 L[i]로 만들 수 있는 lucky triple은 lucky double에서 만들어진다.

즉 lucky double을 미리 구해 놓으면 lucky triple을 구하는 것은 자연스럽게 도출된다. (lucky double을 이루는 수가 L[i]로 나누어 떨어지는지 보면 됨) 풀이를 단계적으로 생각해 보니 간단하다.