[CODILITY] 코딜리티 문제풀이 파이썬 L1.Iterations ~ L2.Arrays

오랜만에 쓰는 코테 문제풀이 포스팅

간간히 프로그래머스 풀다가 넘 어렵기도하고,, 기본적인 문제풀이가 안되는거 같아서 백준도 함께 시작했다(사실 회사에서 준수님따라 시작함)

어쩌다 보니 준비하고있는 곳 코딩테스트가 코딜리티로 이뤄진다길래 익숙해질겸 오늘 코딜리티 가입해서 몇 문제를 풀어보았다.

프로그래머스랑 별 다르지 않은듯?! 문제 답안 제출하고 바로 다시 제출하지 못하고 나갔다 들어와 초기화된 상태로 다시 해야되는건 아쉽지만

가장 맘에 드는건 내가 틀린 테스트케이스와 틀린 이유, 시간복잡도를 볼 수 있다는 점!!!!!

내 힘으로 풀지 않고 내가 틀린 테스트케이스 참고해가며 코드를 고쳐나가는 건 매우 위험하고 안좋은거 알지만 ㅠ 넘 답답한걸,,

프로그래머스 카카오 문제들 풀다가 넘 질려있었는데

코딜리티보니 비슷한 유형인데 접근하기 더 쉽게 구성된 문제들이 있어서 당분간 프로그래머스는 접고 코딜리티랑 백준으로 달려볼까 한다.

첨에 코딜리티 Exercise별로 풀었는데 문제마다 참고할 코드가 많지 않아 Lesson을 따라가기로 했다.

내가 푸는 것도 중요하지만 다른 사람들은 어떻게 풀었나 보면서 배우는게 참 많은 것 같다. 다들 어쩜그리 똑똑하신건지.. 흥.. 나도 알려조..

---

 

[MY GITHUB] https://github.com/ijo0r98/codility

GitHub - ijo0r98/codility: 코딩테스트 내가 접수한다(3) 코딜리티

 

 

Lesson1. Iterations > BinaryGap

BinaryGap coding task - Learn to Code - Codility

첫번째 시도 44%

처음에 문제를 잘못 이해했다. 1과 0 상관없이 양쪽에 하나의 비트가 있고 그 비트와 다른 연속된 비트의 수를 구하는 문제인 줄 알았다.

예를 들어 10001도 3이고 01110도 3이라고 생각했다.

입력받은 배열을 순회하며 비트가 달라지면 while문을 돌며 같은 비트일 때 개수를 세고 또 다시 다른 비트가 나타나면 멈추고 최대 개수를 비교하는 그런 로직으로 짰다.

코드는 없지만 지금 생각해보면 살짝 엉망진창..

 

두번째 시도 0~6%

도저히 이상하다 싶어 구글링하다가 찾은 정보는 0의 개수만 세는 거라는거..

생각해보니 2진수는 무조건 1로 시작할테고 0이 등장하면 0의 개수를 세는 것이 맞긴 하다. 문제가 영어인 점의 폐해ㅠ 영어공부도 덤^_^

def solution(N):
    binary = bin(N)[2:]
    i = 0
    max_cnt = 0
    for i in range(1, len(binary)-2):
        if binary[i] == '0':
            next_i = i + 1
            cnt = 1
            while True:
                cnt += 1
                next_i += 1
                if next_i == len(binary)-1:
                    break
                if binary[next_i] == '1':
                    max_cnt = max(cnt, max_cnt)
                    break
                
    return max_cnt

- 어차피 2진수의 시작은 1이니 0을 지나 인덱스 1부터 다음 인덱스(next_i)를 고려한 전체길이-2까지 순회

- 0을 만나면 while문을 돌며 1이 다시 나올때 까지 cnt 증가, 1이 나오는지 확인하기 위해 next_i도 함께 증가

- 1을 만나거나 1을 만나지 못해 리스트의 끝에 도달하면(인덱스 범위를 벗어나면) 반복문 종료

- 이때 1을 만난 경우 BinaryGap을 구할 수 있는 상황임으로 최대개수를 갱신해줌

예외처리가 잘 안된건지 이것저것 바꿔보았지만 6%가 최대로 끝남..

 

세번째 시도 100%

허허 위의 두 풀이 생각하게된게 프로그래머스에서 비슷한 유형을 저렇게 풀다 포기했기 때문..

답답해서 구글링하다 겁나 간단한 풀이를 알아냈다.... Lesson1부터 문제 못풀고 구글링 한 내 자신이 부끄럽고 속상..

1 사이에 존재하는 0들의 길이를 구한다는 것에 초점을 맞춰 1의 인덱스들 차로 그 사이 길이를 구하는 방법이다.

def solution(N):
    binary = bin(N)[2:]
    idxs = []
    for i in range(len(binary)):
        if binary[i] == '1':
            idxs.append(i)
    if len(idxs) == 1:
        return 0
    
    max_cnt = 0
    for i in range(len(idxs)-1):
        max_cnt = max(max_cnt, idxs[i+1]-idxs[i]-1)
    return max_cnt

- 리스트에서 1이 등장하는 인덱스값을 모두 idxs 리스트에 저장

- 인덱스끼리 빼면 그 차이 즉 1 사이 0이 존재하는 구간의 길이를 알 수 있다.

 

 

Lesson2. Arrays > CyclicRotation

CyclicRotation coding task - Learn to Code - Codility

첫번째 시도 100%

주어진 배열을 주어진 수 만큼 회전하는 문제로 직접 회전하는게 아니라 인덱스를 중심으로 생각하여 풀었던 문제.. 다행히도 한방에 품!

* 참고로 회전 방향은 -> 왼쪽에서 오른쪽, 배열 뒤로 이동하는 모양임

def solution(A, K):
    length = len(A)
    answer = [0 for i in range(length)]
    for i in range(len(A)):
        new_i = (i + K) % length
        answer[new_i] = A[i]
    
    return answer

- K만큼 회전하게되면 기존의 자리보다 K만큼 뒤로 물러나는 것임으로 새로 자리잡을 인덱스값을 구하고 그 인덱스에 값을 넣어줌

 

다른 사람 풀이

리스트 슬라이싱을 이용한 방법으로 색다른 접근이였다.

def solution(A, K):
    N = len(A)
    if N < 2:
        return A
    if K >= N:
        K = K%N       
    return A[N-K:] + A[:N-K]

(출처: https://kimyaesol.tistory.com/149)

 

 

Lesson2. Arrays > OddOccurrencesInArray

OddOccurrencesInArray coding task - Learn to Code - Codility

첫번째 시도 100%

이 문제도 처음에 방향을 잡을 땐 조금 해맸는데 그렇게 어려운 문제는 아니였삼

프로그래머스에서 괄호 쌍 맞추던게 생각나서 스택으로 어찌저찌 하려했는데 생각대로 잘 안됐다.

특히나 리스트를 이용한 풀이를 할 때 시간복잡도도 잘 따져서 해야겠다고 생각이 들어 수행시간 생각해서 하느라 더 답답..

뭘 해도 O(n^2)밖에 생각 안나길래 그냥 풀까 하다가 떠오른 사전! 이곳저곳 활용하기도 좋고 쉬워서 파이썬에서 가장 좋아하는(ㅋㅋ) 자료형이 사전임

* 짝이 맞지 않는 수는 하나밖에 없다는 거 알아둘 것! 첨에 배열로 반환했다가 0점 나옴

import collections

def solution(A):
    a_dict = collections.defaultdict(list)
    
    for i in range(len(A)):
        a_dict[A[i]].append(i)
    
    for key, value in a_dict.items():
        if len(value)%2 != 0:
            return key

- collections 또한 내가 좋아하는 파이썬 라이브러리,, 코테할때 짱짱,, defaultdict 이용하여 초기값을 리스트로 지정

  (collections.defaultdict 활용법 👉🏻 2021.10.30 - [python/hello world] - [PYTHON] 파이썬 collections 모듈(1) defaultdict )

- 각 알파벳을 키로, 값에는 해당 알파벳이 등장하는 인덱스들을 저장한 사전을 만들어줌

- 인덱스가 저장된 배열의 길이가 짝수일 때 짝이 맞춰지는 것임으로 홀수일 때가 바로 알파벳이 짝지어지지 않고 남는 경우

 

다른 사람 풀이1

봐도봐도 이해 안감.. 난 언제쯤 이정도로 할 수 있을까

from functools import reduce

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

 

다른 사람 풀이2

내가 하고싶었던 풀이와 비슷하다. 스택을 사용하고싶었는데 pop이 아닌 다른 삭제 메서드를 쓰게되면 스택이 의미없어져 포기했던 방법..

배열의 요소들이 숫자임으로 정렬하는 방법이 있었다!!!

def solution(A):
    
    A = sorted(A)

    while A:
        try : 
            a = A.pop()
            b = A.pop()
        except : 
            break

        if not a == b:
            break
            
    return a

(출처: https://smecsm.tistory.com/205)

 

다른 사람 풀이3

파이썬에서 sorted()의 시간복잡도는 O(N*log(N)) 스택 풀이와 오묘하게 섞인 느낌

def solution(A):
    if len(A) == 1:
        return A[0]

    A = sorted(A)
    for i in range(0, len(A), 2):
        if i+1 == len(A):
            return A[i]
        if A[i] != A[i+1]:
            return A[i]