코딜리티를 이용한 코딩테스트 준비 (lesson 1~4)

며칠 전, 연구실 선배로부터 네이버 인턴할 때 코딜리티를 이용해서 코테를 봤다는 팁을 얻고

바로 코딜리티에 로그인하여 코딩 테스트를 준비하고 있다. 

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

Developer Training | Test Coding Skills Online - Codility

 

 내가 사용하는 언어는 python으로, 문제를 풀면서 활용하기 좋았던 여러 내장 functions들을 정리해본다.

 

lesson 1~4 핵심

• list: pop(), insert(index, element)
• set: add(element), remove(element)
• 문제의 전제 조건들 잘 확인하여 에러가 나지 않도록 주의할 것.
• 미리 예외가 날 상황들을 주석으로 정리해보고 하나씩 코드로 구현할 것.
• time complexity 
  • O(N^2)가 되는 코딩을 주의할 것. (ex. for문 내 리스트 sum, 비교 등)
  • O(N)으로 만드는 방법
    • 리스트 요소 하나하나 조건을 충족하는 지 체크 & count. 
  • O(N+M)으로 만드는 방법
    • for문 하나에 조건 하나씩 충족하도록 설계.

 

CyclicRotation

#list pop, insert를 이용하여 해결

def solution(A, K):
    # Implement your solution here
    for i in range(K):
        pop_num = A.pop()
        A.insert(0, pop_num)
    return A

OddOccurrencesInArray

#리스트 내에 쌍으로 등장하는 수를 제외한 숫자 하나를 출력하는 문제

#hash set을 활용하여, 짝수로 등장하면 set 내에서 제거되고, 하나만 존재하면 set 내에 남아 있도록 함.
#time out -> 66%

def solution(A):
  output = set()
  for i in A:
    if i not in list(output):
      output.add(i)
    else:
      output.remove(i)
  return list(output)[0]
  
  
# 다른 솔루션  
from functools import reduce

def solution(A):
    return reduce(lambda x,y: x^y, A)

 

PermMissingElem

# 길이 N의 배열 내에서 1부터 N+1까지 숫자 중 누락된 숫자를 찾기 
# total score 100%

def solution(A):
    # Implement your solution here
    answer = sum(list(range(1, len(A)+2)))
    summ = sum(A)
    return answer  - summ

 

TapeEquilibrium

#한 인덱스를 기준으로 배열을 두개로 나누었을 때 각각의 합의 차이가 가장 작은 것을 반환.

#분할된 리스트를 각각 sum하면 O(N^2)이 되어 timeout error가 뜸. 
#정답률 38%

def solution(A):
    for index in range(len(A)):
        if index == 0 :
            best_min = abs(sum(A))
        else:
            a = sum(A[:index])
            b = sum(A[index:])    
            diff = abs(a-b)
            if diff < best_min: best_min = diff
    return best_min
    
    
 #분할 list에 대한 sum을 없애서 시간 복잡도를 O(N)으로 만들어주는 것이 핵심. 
 # 정답률 100%
 
 def solution(A):
    l = 0
    r = sum(A)
    best_min = None
    for index in range(1, len(A)):
        l = l+A[index-1]
        r = r-A[index-1]
        diff = abs(l-r)
        if best_min is None: best_min = diff
        else: best_min = min(diff, best_min)  
    return best_min

FrogRiverOne

# set 내에 1~X까지의 숫자가 존재해야 하며, 그 조건을 충족하는 가장 작은 배열 인덱스를 구하는 문제.
# 두번째 if문 비교 조건에서 시간복잡도가 올라간 것으로 보임. 
# 시간 복잡도 O(N^2), 정답률 54%

def solution(X, A):
    leaves = set()
    for index, i in enumerate(A):
      if i not in leaves:
          leaves.add(i)
      if leaves == set(range(1, X+1)): return index
    return -1
    
    
# 위 풀이에서 한꺼번에 조건을 만족하는지 판단하지 말고, 조건을 쪼개어 하나씩 충족시키는 지를 확인하는 방향으로 풀이.
# 시간 복잡도 O(N), 정답률 100%

def solution(X, A):
    check_list = [0]*(X+1)
    cnt  = 0 
    for index, i in enumerate(A):
        if check_list[i] == 0:
            check_list[i] = 1
            cnt += 1
        if cnt == X : return index  
    return -1

 

PermCheck

#제시된 N 길이의 배열 A가 1~N의 요소가 하나씩 들어있는 지 확인하는 문제.
#antiSum의 예외처리 고려하지 않아서 오답. 즉, 꼭 하나씩 요소가 들어있지 않아도 sum(A)와 같은 예외를 처리해줘야 함.  
#정답률 75%

def solution(A):
    # Implement your solution here
    num = len(A)
    if sum(A) == sum(range(1, num+1)): return 1
    else: return 0
    
 #이 또한 앞선 문제의 풀이 방식과 동일하게 해결 가능함. 
 #정답률 100%
 
 def solution(A):
    check_list = [0]*(len(A)+1)
    count = 0 
    for i in A:
        try:
            if check_list[i] == 0:
                check_list[i] = 1
                count +=1
        except:
            continue
    if count == len(A): return 1
    else : return 0

 

MaxCounters

# 조건에 따라 길이 N의 counter 배열 내의 요소를 계산하고 결과를 출력하는 문제.
# for문과 첫번째 if문 조건 & max 연산으로 인해 시간복잡도가 N*M이 됨.
# 시간 복잡도 O(N*M), 정답률 66%

def solution(N, A):
    counters = [0]*(N+1)
    for i in A:
        if i in range(1, N+1):
            counters[i] += 1 
        elif i == N+1:
            counters = [max(counters)]*(N+1)
    return counters[1:]

# 연산을 어떻게 하느냐가 관건이 됨. 두 개의 필요 연산을 각각 for문을 돌면서 해주는 것으로 해결.
# 시간 복잡도 O(N+M), 정답률 100%

def solution(N, A):
    counters = [0]*(N+1)
    maxnum = 0
    maxsub = 0
    for i in A:
        if i >= 1 and i <= N: #이 조건에 해당하는 counter는 계산 끝남. 
            if counters[i] < maxnum : 
                counters[i] = maxnum
            counters[i] += 1 
            maxsub = max(counters[i], maxsub) #이 부분 주의! 
        elif i == N+1 : #이 조건에 해당하는 counter는 계산 안 끝남. 
            maxnum = maxsub
    #계산이 안 끝난 부분 해결 
    for index, j in enumerate(counters):
        if j < maxnum:
            counters[index] = maxnum
    
    return counters[1:]

 

MissingInteger

# chat GPT를 이용하여 풀이해 준 그대로 실행.
# 시간 복잡도 O(N log N), 정답률 100%

def solution(A):
    # Filter out negative and zero values, and sort the array
    A = sorted(filter(lambda x: x > 0, A))
    # If the filtered array is empty or its first element is not 1, return 1
    if not A or A[0] != 1:
        return 1
    # Iterate over the filtered array and compare adjacent elements
    for i in range(1, len(A)):
        if A[i] - A[i-1] > 1:
            # If the difference between adjacent elements is greater than 1, return the missing value
            return A[i-1] + 1
    # If all elements are consecutive, return the next integer after the last one
    return A[-1] + 1