[CODILITY] 코딜리티 문제풀이 파이썬 L6.Sorting

Lesson6.Sorting > Distinct(Easy)

Distinct coding task - Learn to Code - Codility

입력받은 리스트에서 중복을 제거하고 등장하는 숫자의 개수를 구한다.

 

첫 번째 풀이) 100%

def solution(A):
    return len(set(A))

파이썬의 set 자료형 덕분에 쉽게 풀었던 문제

파이썬으로 코테를 풀면 이런 점들이 좋은데 반대로 이런 점들이 어려운거 같기도 하다. 코드가 짧고 간결한 반면 다른 언어로의 적용이 조금 힘들다는거..

물론 내가 다른 언어의 기초가 완벽하지 않아서 그런 문제도 있다만은.. 앞으로 문제 풀때는 자바로 푸는 연습을 해봐야하지 않을까 싶다.

 

 

Lesson6.Sorting > MaxProductOfThree(Easy)

MaxProductOfThree coding task - Learn to Code - Codility

탐욕법 문제를 이런 문제라 할 수 있으려나? 암튼 자주 봐오던 유형의 문제이다.

리스트에서 3개의 수를 곱해 최대인 수를 구하는 문제인데 자칫해서는 모든 반복문을 다 돌다가 시간복잡도를 해결하지 못하는 경우가 생기기도 한다.

이런 문제의 경우 반복문을 피하고 시간복잡도를 줄이는게 관건인 듯 하다.

문제에서 중요한 점은 음수와 양수가 포함되어있다는 것인데, 아래 두 기본지식 + L6의 제목처럼 정렬을 이용하여 접근하면 쉽게 풀렸던 문제

* 최대값을 구하기 위해서는 답은 무조건 양수야아함

* 음수의 경우 절댓값이 작을수록 더 작은 수임

 

첫 번째 시도) 100%

def solution(A):
    A = sorted(A, reverse=True) # 내림차순 정렬

    if (A[2] > 0) or (A[0] < 0): # + + +, - - -
        answer = (A[0] * A[1] * A[2])
        # - - * 가 더 큰 경우
        answer = max(answer, A[-1] * A[-2] * A[0])
    elif (A[2] < 0) and (A[1] > 0): # + + - -> + - -
        answer = (A[0] * A[-1] * A[-2])
    elif (A[1] < 0): # + - -
        answer = (A[0] * A[-1] * A[-2])
            
    return answer

먼저 정렬을 한다. 나는 인덱스를 앞에서부터 가는걸 좋아해서 내림차순으로 정렬해주었다. 양수와 음수가 섞여있어 여러 경우로 나뉘는데

(1) 상위 3개가 모든 경우가 양수일때 혹은 모두 음수일때 -> 그대로 3개의 곱이 최대값

(2) 음수가 1개 섞여있는 경우 -> 상위 양수 1개 * 하위 음수 2개를 곱해 최대 양수로 만들어준다.(음수는 작을수록 절대값이 큰 점을 이용)

(3) 음수가 2개 섞여있는 경우 -> 위와 동일하게 상위 양수 1개와 하위 음수 2개를 곱하여 최대값을 반환한다.

 

복잡하게 조건문으로 나눠져있지만 간단히 정리하면

def solution(A):
    A = sorted(A, reverse=True) 
    return max((A[0]*A[1]*A[2]), (A[0]* A[-1]* A[-2]))

 

 

Lesson6.Sorting > Triangle(Easy)

Triangle coding task - Learn to Code - Codility

입력된 배열에서 삼각형을 만들 수 있는 세 변이 주어지는지 확인하는 문제

삼각형을 이루기 위해서는 세 변의 길이(A[R] > A[Q], A[P])가 주어졌을 때 A[P] + A[Q] > A[R] 을 만족해야한다.

 

첫 번째 풀이) 100%

def solution(A):
    A.sort(reverse=True)
    for i in range(len(A)):
        try:
            if A[i] < A[i+1] + A[i+2]:
                return 1
        except:
            break
    return 0

항상 for문에서 마지막 인덱스를 어떻게 지정할지 고민을 좀 했었는데 그냥 try/except 구문으로 해결하는게 더 간편한거 같다.

- 내림차순으로 정렬

- 정렬한 리스트를 순회하며 삼각형을 이루는 조건을 만족할 때 1을 반환한다.

- 조건문에 걸리지 않아(삼각형을 이루는 조건을 모든 변이 만족하지 않아) 반복문이 종료되면 0을 반환한다.

 

 

Lesson6.Sorting> NumberOfDiscIntersections(Medium)

NumberOfDiscIntersections coding task - Learn to Code - Codility

주어진 리스트에 따라 x좌표상에 원들을 그렸을 때 겹치는 원의 쌍을 구한다.

그림을 그리면서 문제를 이해해보면 쉬운데 처음에는 여러 조건 생각하여무작정 셀려고 했더니 코드도 안짜지고 감이 안와 단순하게 방법을 바꿨다.

먼저 A=[1, 5, 2, 1, 4, 0]가 주어졌을 때 인덱스는 원의 중심 x좌표, 인덱스에 해당하는 값은 반지름의 크기이다. 그대로 그림을 그려보면

 

 

내가 생각했던 풀이 방법도 함께 그려져있는데 살펴보자면

먼저 x축에 찍히는 원의 가장 왼쪽 좌표와 오른쪽 좌표를 구하여 하나의 배열에 담고 정렬한다. 

* 여기서 신경써야할 점은 왼쪽 좌표(원의 시작)인지 오른쪽 좌표(원의 끝)인지 구분하여 담아야한다.

x좌표들의 배열을 순회하며 원의 끝 좌표를 만나면 이 좌표 전까지 원의 시작 좌표들의 수를 센다. 이는 곧 현재 끝난 원과 겹쳐지는 원들의 수이다.

그러고 원이 끝났음으로 아까 카운트하고있던 원의 시작좌표 수에서 1을 빼준다.

def solution(A):
    answer = 0
    points = []
    for i in range(len(A)):
        points.append((i-A[i], -1)) # left
        points.append((i+A[i], 1)) # right
    points.sort() 
    
    # (이전까지 -1의 개수) - 1(자기 자신)
    cnt_left = 0 # -1
    for i in range(len(points)):
        if points[i][1] == -1:
            cnt_left += 1
        if points[i][1] == 1:
            answer += (cnt_left-1)
            cnt_left -= 1
    
    return -1 if answer > 10000000 else answer

첫 번째 반복문은 원의 시작 좌표(left, -1)와 끝나는 좌표(right, 1)를 구해서 points 리스트에 담는 부분이며 -1/1과 함께 튜플 형태로 구분을 두었다.

그 이후 시작 좌표(-1)를 만날때마다 시작하는 원의 수를 세면서(cnt_left) 끝 좌표(1)을 만날때마다 이전까지 시작되었던 원의 수(cnt_left)를 답에 더한다.

더하기 전에 1을 빼준 이유는 cnt_left에 현재 끝난 원의 시작좌표도 포함되어있기 때문에 1을 빼준다. 원이 끝났기 때문에 시작한 원의 개수에서 제하는 것이다.

 

다른 사람 코드) 

def solution(A):
    answer = 0
    points = []
    for i in range(len(A)):
        points.append((i-A[i], -1)) # left
        points.append((i+A[i], 1)) # right
    points.sort() 
    
    cnt_left = 0 # -1
    for i in range(len(points)):
        if points[i][1] == -1:
            answer += cnt_left
            cnt_left += 1
        if points[i][1] == 1:
            cnt_left -= 1
    
    return -1 if answer > 10000000 else answer

나와 비슷한데 사람들은 대부분 원의 끝 좌표가 아니라 시작 좌표를 기준으로 생각한 것 같다.