[Codility Challenge] Jurassic Code Python 풀이

오늘은 Codility Challenge를 풀어봤다.

 

현재는 Jurassic Code 챌린지가 진행 중이다.

 

아래 링크에서 챌린지를 진행할 수 있다.

 

https://app.codility.com/programmers/challenges/

Jurassic Code challenge

시간제한은 120분이고 거의 아래의 언어들을 사용할 수 있다.

(C, C++, C#, Go, Java 11, Java 8, JavaScript, Kotlin, Lua, Objective-C, Pascal, Perl, PHP, Python, Ruby, Scala, Swift 4 or Visual Basic.)

 

---

문제 설명

 

 

좌표 위에 점이 N개가 있다. 각 포인트는 빨강이나 초록('R'이나 'G') 색으로 색칠되어있다.

K번째 점은 (X[K], Y[K])로 이루어져 있고 그 색은 colors[K]다.

(0,0)에 있는 점은 없다.

 

여기서 원을 그릴 건데 그 원안에 빨간색과 초록색 점의 개수가 같게 하고 최대한 많은 점을 넣으려고 한다.

(여기서 원안에 아무 점도 없을 수 있다.)

 

문제 설명은 이해하기 쉬울 거라고 생각한다.

예시가 필요하면 글 초반의 링크에서 해보면 좋을 것 같다.

---

맨 처음에는 시간 복잡도를 생각하지 않고 풀어봤다. 그렇게 시간 복잡도가 O(N^2)이 나와서

데이터가 많을 때 테스트 케이스를 실패해서 아래와 같이 실버가 나왔다.

 

보통 코딩 테스트 사이트에서는 테스트 케이스 맞춘 것만 알려주던데

Codility 챌린지는 시간 복잡도까지 알려줘서 좋았다.

---

다음에 반복문을 하나 줄여서 풀어봤다.

 

그 결과 챌린지에서 Golden Award를 받을 수 있었다.

 

시간 복잡도는 O(N logN)이 나왔다.

 

결과는 아래 캡처와 같이 자세하게 하나하나 다 알려준다.

 

---

이제 구현 방식을 보겠다.

 

우선 원점부터 좌표까지의 거리와 색을 하나로 묶어서 sorting을 하고 싶어서

리스트로 정의를 하고 [ 거리, 색 ]의 리스트를 만들고 거리로 sort를 했다.

계산 편의상 거리에 루트를 취하지는 않았다.

linelen = [ [X[i]**2 + Y[i]**2, colors[i]] for i in range(len(X))]
linelen.sort(key=lambda x : x[0])

 

그 후 초기 길이를 0으로 정하고 

그 길이와 비교해서 같으면 해당 점의 색 개수를 추가한다.

해당 길이의 점을 모두 담아야 하므로 continue를 통해 아래의 로직을 패스한다.

if prevlen == l[0]:
    if l[1] == 'R':
        R+=1
    else:
        G+=1
    continue

그리고 달라진다면 우선 R과 G가 같은지 똑같은 지 확인하고

똑같다면 정답에 이전까지 계산했던 R과 G의 합을 추가한다.

 

여기서 이전 길이의 길이가 같을 때의 모든 점의 개수가 담긴다.

 

그리고 길이가 달라졌으니 다시 해당 점의 색 개수를 추가한다.

 

그리고 거리가 모두 같은 점이 있을 때를 대비해서

모든 점을 다 본 후 R과 G가 같은지 확인하고 정답에 R과 G의 개수를 더해서 추가한다.

 

이렇게 반복문 한 번으로 끝낼 수 있게 된다.

 

---

이제 코드를 보겠다.

 

def solution(X, Y, colors):
    # write your code in Python 3.6
    R=0
    G=0
    answer = 0
    colors = list(colors)
    linelen = [ [X[i]**2 + Y[i]**2, colors[i]] for i in range(len(X))]
    linelen.sort(key=lambda x : x[0])

    prevlen = 0

    for l in linelen:
        if prevlen == l[0]:
            if l[1] == 'R':
                R+=1
            else:
                G+=1
            continue
            
        else:
            if R==G:
                answer = R+G  
            prevlen=l[0]
            if l[1] == 'R':
                R+=1
            else:
                G+=1
        
    if R==G:
        answer = R+G       

    return answer

 

잘 작동되는 것을 확인할 수 있다.