[CODILITY] 코딜리티 문제풀이 파이썬 L3.TimeComplexity ~ L4.CountingElements

2주동안 오랜만에 백수된 걸 푹 누렸으니 이번주부터는 파이팅이다

이제 불합격 통보 제발 멈춰,,✋🏻

 

---

 

 

Lesson3. Time Complexity > FrogJmp(Easy)

FrogJmp coding task - Learn to Code - Codility

내가 싫어하는 개구리가 길을 건너 반대쪽으로 가려고 한다.

주어진 X는 시작 위치, Y는 가야하는 도로의 총 길이, Z는 한번에 뛸 수 있는 거리로 총 몇번만에 건너편에 도착하는지 구하는 쉬운 문제

 

첫 번째 시도 100%

from math import ceil

def solution(X, Y, D):
    return ceil(((Y-X)/D))

 

 

Lesson3. Time Complexity > PermMissingElem(Easy)

PermMissingElem coding task - Learn to Code - Codility

주어진 배열에서 빠진 원소를 구하는 문제로 아래 조건들 덕분에 쉬웠던 문제

- 배열의 길이가 N(len(A))일 때 배열의 원소는 [1:N+1]에 속하며(each element of array A is an integer within the range [1..(N+1)])

- 겹치는 원소가 없다(the elements of A are all distinct)

 

첫 번째 시도 50%

def solution(A):
    A = sorted(A)
    for i in range(len(A)-1):
        if (A[i+1]-A[i]) != 1:
            return A[i]+1
    return A[-1]+1

완벽한 코드라 생각했지만,, 빈 배열이 들어왔을 때 예외처리가 안되어있어서 실패 

 

두 번째 시도 60%

def solution(A):
    if not A:
        return 1
    A = sorted(A)
    for i in range(len(A)-1):
        if (A[i+1]-A[i]) != 1:
            return A[i]+1
    return A[-1]+1

빈 배열일 때 문제는 해결하였지만(빈 배열일 때는 1을 반환해야함)

첫 시작이 1이 아닌 다른 수로 시작할 때, 예를 들어 [2, 3, 4]가 주어질 때 1이 포함되지 않았음을 체크하는 조건이 없어서 5를 반환하여 실패..

 

세 번째 시도 100%

def solution(A):
    if not A:
        return 1
    A = sorted(A) 
    if A[0] != 1:
        return 1
    for i in range(len(A)-1):
        if (A[i+1]-A[i]) != 1:
            return A[i]+1
    return A[-1]+1

- 빈 배열일 때 예외 처리

- 입력받은 배열 일단 정렬

- 1~N+1 사이 수가 모두 있어야하는데 배열이 1로 시작하지 않은 경우 1 반환

- 정렬된 배열임으로 1씩 증가하지 않고 뛰어넘은 수가 생기면 해당 숫자 반환

- 마지막으로 모두 1씩 증가하여 배열을 다 돌았을 때 가장 마지막인 N+1이 포함되어있지 않은 상황임으로 (가장 마지막 원소 + 1) 반환

쉬운 문제였는데 자잘한 예외처리를 제대로 안해서 계속 다시 풀었다니 ㅠ 문제를 좀 더 꼼꼼히 푸는 연습을 계속 해야겠다.

 

 

Lesson3. Time Complexity > TapeEquilibrium(Easy)

TapeEquilibrium coding task - Learn to Code - Codility

주어진 배열을 두 그룹으로 나눠 각 그룹에 속한 원소들 합의 차 차를 구한다. 어떤 인덱스를 기준으로 그룹을 나눴을 때 그 차가 최소가 되는지 구하는 문제

 

첫 번째 풀이 46%

일단 아무 고민 없이 답이 나오도록 짠 코드인데.. sum 함수 때문에 시간초과가 나올 줄은 알았다..

def solution(A):
    min_sum = 100
    for i in range(1, len(A)):
        tmp = abs(sum(A[:i]) - sum(A[i:]))
        min_sum = min(min_sum, tmp)
    return min_sum

역시나 시간복잡도 O(N^2)로 실패

 

두 번째 풀이 15%

인덱스 기준 왼쪽 그룹과 오른쪽의 합을 미리 구해놓고 바뀌는 원소(인덱스에 해당하는)를 더하고 빼며 각 합을 계산, 그리고 최소값을 구하는 방법으로 변경

변경한 방법의 시간복잡도는 O(N*logN)으로 괜찮았지만 반복문의 범위를 잘못 설정함,,

 

세 번째 풀이 69%

그룹에는 꼭 하나의 원소라도 포함되어야 함, 따라서 그룹을 나누는 인덱스를 정하는 반복문은 마지막 원소까지 도달하면 안됨ㅠㅠ

이번에도 반복문의 범위를 잘못 설정하여 실패

그리고 계속하여 최소 차이를 저장하는 min_sum 변수를 좀 작은 수로 설정하여 min()함수에 걸리지 않는 경우가 발생,, 조건을 보고 수정함

 

네 번째 풀이 100%

def solution(A):
    min_sum = 100000
    left = 0
    right = sum(A)
    for p in range(len(A)-1):
        left += A[p]
        right -= A[p]
        min_sum = min(min_sum, abs(left-right))
    return min_sum

- min_sum의 경우 A의 원소 범위가  [−1,000..1,000] 이고, N(A의 길이)이 [2..100,000]임을 보고을보고 적당히 큰 값으로 설정

- 왼쪽 그룹은 그룹에 원소가 포함될 수록 더해야함으로 초기값 0으로 설정

- 오른쪽 그룹은 원소가 빠질수록 빼야함으로 전체 합으로 초기값 설정

- 여기서 p는 그룹을 나눌 인덱스로 p에 해당하는 원소를 왼쪽 그룹에 더하고 오른쪽 그룹에서 빼는 형태로 모든 경우의 그룹 탐색(탐욕법 문제인가..)

- 암튼 마지막 원소 하나만이 오른쪽 그룹인 경우가 있어야함으로 인덱스는 원소 마지막까지 돌면 안됨으로 반복문의 범위는 [0, len(A)-1]

 

 

Lesson4. Counting Elements > FrogRiverOne(Easy)

FrogRiverOne coding task - Learn to Code - Codility

처음에 문제가 무슨 문제인지 이해가 안되서 사실 구글링했다.. 코딜리티가 영어 문제라 이런게 좀 귀찮..

찾아본 결과, 또 내가 싫어하는 개구리가 X폭의 강을 건너야 하는데 1씩 움직일 수 있으며 나뭇잎이 있어야 강을 건널 수 있다.

대충 입력되는 리스트 A의 인덱스가 시간(초), 인덱스의 값이 나뭇잎이 생기는 위치라고 생각하면 쉬울 것 같다.

나와있는 예시대로 X=5, A=[1, 3, 1, 4, 2, 3, 5, 4]가 주어졌을 때 0초일때 거리 1에 나뭇잎이 생기고, 1초에 거리 3에 나뭇잎이 생기고..

뭐 이렇게 하다보면 인덱스가 6일 때(6초가 되었을 때) 1부터 5까지 모든 수가 등장하였음으로 5까지 모든 위치에 나뭇잎이 생겨 강을 건널 수 있다.

간단히 정리하면 1부터 X까지 모든 자연수가 등장했을 때의 인덱스를 구하라는 문제이다.

* A에 등장하는 모든 수는 [1, X]에 포함된다(each element of array A is an integer within the range [1..X])

 

첫 번째 시도 100%

def solution(X, A):
    
    nums = set()
    for i in range(len(A)):
        nums.add(A[i])
        if len(nums) == X:
            break
        
    if (i == len(A)-1) and (len(nums) != X):
        i = -1
        
    return i

- 1~X까지의 수가 중복으로 등장할 수 있음으로 나뭇잎 위치를 담을 nums는 집합으로 초기화

-리스트를 순회하며 나뭇잎 위치를 추가하는데

- 여기서 1~X까지의 수가 다 등장하였을 때, 즉 nums의 길이가 X가 되었을 때 반복문 순회를 멈춘다. 그때의 인덱스가 바로 강을 건널 수 있는 시간!

- 하지만 길이가 X가 되지 않는다던가 위의 종료조건을 통과하지 못했을 때는 강을 건너지 못한다는 의미임으로 반환할 값을 -1로 바꿔줌

 

 

Lesson4. Counting Elements > PermCheck(Easy)

PermCheck coding task - Learn to Code - Codility

permutation(순열) 문제로 순열 계산이 가능한지 체크하는 문제인 듯 하다.

N에 대한 순열N!을 구한다면 1부터 N까지의 자연수만 등장해야 함으로 N은 A의 길이이자 A의 최대값이라 해도 될듯!

 

첫 번째 시도 100%

def solution(A):
    A = sorted(A)
    if (A[0] != 1) or (A[-1] != len(A)):
        return 0
    for i in range(len(A)-1):
        if (A[i+1]-A[i]) != 1:
            return 0
    
    return 1

- 1~N까지 모든 자연수가 등장하는지 확인해야함으로 먼저 오름차순 정렬해준다.

- 일단 첫번째가 1이 아니거나 마지막이 N이 아니란 소리는 1~N 모든 자연수가 등장하지 않는다는 소리임으로 반복문 순회하기 전 정답 반환

- 만약 위의 조건을 만족한다면 리스트를 순회하며 1씩 증가하는지, 모든 자연수가 등장하는지 확인

 

 

Lesson4. Counting Elements > MaxCounters(Medium)

MaxCounters coding task - Learn to Code - Codility

문제 이해하는데 시간이 다소 많이 소요되었다.대충 정리해보자면 먼저 길이 N인 배열을 0으로 초기화하여 빈도수를 체크한다.

- A의 원소가 N+1이라면 A의 최대값으로 모든 원소 초기화(max counter)

- A의 원소가 N이하라면 해당 원소의 위치에 등장 빈도수를 증가시킨다(increase)

문제 해석도 그렇지만.. 결국 수행시간을 더 못줄이고 time out 문제로 실패했다 ㅠㅠ 유일하게 실패한 문제..

 

첫 번째 시도 66%

def solution(N, A):
    
    answer = [0 for i in range(N)]
    
    max_counter = 0
    for k in range(len(A)):
        if A[k] == N+1:
            for i in range(N):
                answer[i] = max_counter
        else:
            answer[A[k]-1] += 1
            max_counter = max(answer[A[k]-1], max_counter)
                
    return answer

max counter인 경우 최대 빈도수로 원소 초기화하는 부분을 그냥 직관적으로 반복문으로 돌렸더니 역시나 시간복잡도 O(N*M)

 

두 번째 시도 11%

def solution(N, A):
    
    answer = [0] * N
    
    max_counter = 0
    cnt = 0
    for k in range(len(A)):
        if A[k] == N+1:
            answer = [0] * N
            cnt += 1
        else:
            answer[A[k]-1] += 1
            max_counter = max(answer[A[k]-1], max_counter)
        
    for i in range(N):
        answer[i] = answer[i] + (max_counter * cnt)
                
    return answer

최대 빈도수로 초기화할 때, 모두 0으로 초기화하고 빈도수를 0부터 다시 증가시키는 방법으로 변경

A[k]가 N+1일때 최대 빈도수로 모두 초기화가 되어야하는데 나는 이때 카운트를 세고 최대 빈도수를 곱하여 더했다.

문제 이해가 조금 부족했던 풀이..

 

세 번째 풀이 22% ~ 네 번째 풀이 77%

마지막에 최대빈도수만큼 더하는 방법에서 뭐 어찌저찌 수정했지만 77%까지밖에 못끌어올림

 

마지막 다섯번째 풀이 88%

timeout으로 100%는 나오지 못했다. 마지막 테스트 케이스에서 0.006s차로 통과를 못했는데 도저히 난 못줄일거같다ㅠㅠ

아무래도 마지막에 for문 한번 더 도는게 실행속도에 조금 영향이 있지 않을까 싶은데 내가 생각한 풀이로는 이게 최선,,

def solution(N, A):
    answer = [0] * N
    max_counter = 0 
    tmp = 0 
    for k in A:
        if k == N+1:
            answer = [0] * N
            tmp = max_counter
        else:
            answer[k-1] = answer[k-1] + 1
            max_counter = max(answer[k-1] + tmp, max_counter)
            
    for i in range(N):
        answer[i] = tmp + answer[i]
                
    return answer

- 정답 먼저 배열 초기화, 등장한 빈도수들 중 최대값을 저장하는 max_counter, 이전의 max_counter을 저장하는 tmp

- 먼저 N+1일 때, 새로 빈도수를 시작하기 위해 배열을 모두 0으로 초기화해주고 이전의 max_counter을 tmp에 저장해준다.

- 아닐때는 빈도수 계산, 위에서 빈도수를 초기화했음으로 아까 저장한 tmp를 더한 빈도수와 max_counter중 큰값으로 max_counter 갱신

* N+1일때 최대 빈도수로 초기화를 해주어야하는데 다시 반복문을 돌 수 없으니 0으로 모두 초기화해주고 다시 빈도수를 증가시켜준다.

* 이후 max_counter 갱신할 때 빠진 최대 빈도수를 더해서 비교해줘야함으로 tmp에 과거 max_counter 저장

* max_counter를 갱신할 때 아까 최대 빈도수가 아닌 0으로 초기화시켜줬으니 tmp를 더한 상태에서 비교

 

다른 사람 풀이(100%)

def solution_(N, A):
    r = N * [0] 
    m1 = 0 	
    m2 = 0 	
    for i in A:
        if i <= N:
            r[i-1] = max(r[i-1] +1, m1 +1) 
            m2 = max(r[i-1], m2) 
        else :
            m1 = m2 	
            
    return [m1 if f < m1 else f for f in r]

나와 비슷한 풀이인데.. 왜 난 88%이고 이 답은 100%일려나...

 

 

Lesson4. Counting Elements > MissingInteger(Medium)

MissingInteger coding task - Learn to Code - Codility

포함되지 않은 가장 작은 자연수 출력하는 문제

 

첫 번째 시도 55%

def solution(A):
    A = sorted(A)
    if A[-1] < 0 : 
        return 1
    for i in range(len(A)-1):
        if (A[i] > 0) and ((A[i+1] - A[i]) > 1):
            return A[i]+1
    
    return A[-1]+1

음수만 있거나 1이 없는 경우 1을 출력해야하는데 후자의 예외처리를 못한 코드

마지막 원소(가장 큰 원소)가 음수가 아닌 양수여서 반복문을 들어갔을 때 그냥 1씩 증가하는지만 확인하는 로직이라 1을 확인하지 못함..

 

두 번째 시도 88%

def solution(A):
    A = sorted(A)
    if (A[-1] < 0) or (A[0] > 1):
        return 1
    for i in range(len(A)-1):
        if (A[i] > 0) and ((A[i+1] - A[i]) > 1):
            return A[i]+1
    
    return A[-1]+1

오름차순 정렬 후 1인 경우를 확인했지만.. 배열에 양수와 음수가 섞인 경우를 놓침.. 따라서 실패..

 

세 번째 시도 100%

def solution(A):
    new_A = []    
    for a in A:
        if a > 0:
            new_A.append(a)
    new_A = sorted(new_A)        
            
    if (len(new_A) == 0) or (new_A[0] > 1):
        return 1
    
    for i in range(len(new_A)-1):
        if (new_A[i+1] - new_A[i]) > 1:
            return new_A[i]+1
    
    return new_A[-1]+1

- 음수 양수 섞여서 입력을 받는데 어차피 자연수만을 체크하기 때문에 음수인 경우는 제외됨으로 양수인 값만 추가하여 새로 A배열 생성

- 새로 배열을 만들었는데 그 배열에 값이 없다던가(주어진 배열이 음수만 있었던 경우) 첫 시작이 1이 아니라면 1 반환

- 위의 경우가 아닌 경우 1씩 증가하는지 확인하여 빈 자연수 반환

 

새로운 배열을 굳이 안만들어도 될거같은데.. 하고 찾아본 다른 사람들의 풀이

 

다른 사람 풀이 1

def solution(N, A):
    A.sort()
    A = list(set(A))
    missingdata = 1
    for i in A:
        if i == missingdata :
            missingdata +=1
    return missingdata

(출처: https://sooho-kim.tistory.com/33)

 

다른 사람 풀이 2

def solution(A):
    temp_list = {*list(range(1, max(A) + 2))}
    for i in A:
        if i in temp_list:
            temp_list.remove(i)
    return min(temp_list) if temp_list and min(temp_list) > 0 else 1

(출처: https://this-programmer.tistory.com/342)