[프로그래머스 | Programmers] 월간 코드 챌린지 시즌2 5월 문제풀이

 

프로그래머스에서 월간 코드 챌린지를 진행했다 ! 시간이 적절한 시간대에 잡혀서 여유롭게 참여할 수 있었다.

4월달에 한 번, 이번 달에 한 번이 시즌 2 챌린지였는데, 나는 이번 챌린지를 두 번째 대회가 돼서야 접했다.

두 번째 대회까지 총 8문제 중에 4문제만 풀어도 이벤트에 응모할 수 있다는데, 이번에 3문제를 풀면서 아쉽게 응모는 하지 못했다.

---

월간 코드 챌린지 안내

 

4월에 챌린지를 알고 있었더라면..

 

 

이번 달 챌린지에서는 6546명 중 53위를 달성했다 ! 개인적으로 DP가 굉장히 약한 편이라고 생각하는데, 이번 문제셋에서는 구현 / 그리디 / 자료구조 / 그래프 쪽으로 출제돼서 3문제를 맞았다.

 

코드 테스트 챌린지 리더보드. 총 400점 중 300점을 획득해 53등으로 마무리했다.

 

---

 

1. 약수의 개수와 덧셈

약수의 개수가 짝수면 더하고, 홀수면 빼야 한다.

약수의 개수가 홀수인 경우는 제곱수인 경우이고, 수의 범위가 $1000$ 이니까 $32^2=1024$ 까지 배열에 넣어준다.

$left$ 에서 $right$ 까지 훑으면서 수가 제곱수면 빼고, 그렇지 않으면 더해준다

def solution(left, right):
    t = [x**2 for x in range(1, 33)]
    ret = 0
    for i in range(left, right+1):
        ret -= (i if i in t else -i)
    return ret
 

 

2. 2개 이하로 다른 비트

세 가지 경우의 수를 나눠서 문제를 해결했다.

• 짝수의 경우에는 마지막 비트가 0이므로 1을 더한다.
• $2^K-1$꼴의 경우, 모든 비트가 1이므로 최상위 비트 '1'을 '10'으로 바꾼다.
• 그 외의 경우, 가장 낮은 0 비트를 찾아서 1로 바꾸고, 그 다음 비트를 0으로 바꾼다.

처음 문제를 해결할 때는 bin 함수를 사용해서 수를 이진수 문자열로 바꿔서 문자열 replace 로 해결했는데, 이번에 다시 풀면서 bitwise operation 을 사용했다. 200ms는 거뜬히 잡아먹던 수행시간이 20-50ms까지 줄었다. 편하면 그만큼 느리다..

def f(n):
    bit_length = n.bit_length()
    if not n & 1:
        return n | 1
    if not (n+1) & n:
        return (n | (n+1)) ^ (1 << (bit_length-1))
    for i in range(bit_length):
        if (1 << i) | n != n:
            n |= (1 << i)
            n ^= (1 << (i-1))
            return n
 
def solution(numbers):
    return [f(x) for x in numbers]
 

 

3. 110 옮기기

문제를 보자마자 백준의 문자열 폭발이 생각났다. 옛날에 스택 가지고 놀다가 이 문제 보고 꽤 쩔쩔맸는데, 그때 많이 삽질한 게 도움된 것 같다.

스택을 이용해서 110 을 카운트해가면서 뺀 다음에, 가장 오른쪽에 있는 0 뒤에 110 을 센 만큼 넣어 준다. 남은 게 1 뿐이라면, 가장 앞에 110 을 추가하면 된다.

가장 오른쪽에 있는 0 뒤에 110 을 넣는게 해답이 되는 이유는, 가장 오른쪽에 있는 0 뒤의 모든 비트는 1 이고, 110 은 그보다 사전순으로 앞에 오기 때문이다. 또한 0 앞에 110 을 넣게 되면, 사전순으로 뒤로 올 수밖에 없다

예) 1(110)0101, 1010(110)1

def f(n):
    stk = []
    cnt = 0
    for i in n:
        stk.append(i)
        if i == '0' and stk[-3:] == ['1', '1', '0']:
            del stk[-3:]
            cnt += 1
    idx = -1
    for i in range(len(stk)):
        if stk[i] == '0':
            idx = i
    if idx < 0:
        ret = "110"*cnt + ''.join(stk)
    else:
        ret = ''.join(stk[:idx+1]) + "110"*cnt + ''.join(stk[idx+1:])
    return ret
def solution(s):
    return [f(x) for x in s]
    

 

4. 중력 작용

백준에서 segment tree + lazy propagation까지 문제를 해결해본 다음 도전했던 게 HLD (heavy-light decomposition)이었다. 문제를 보고 HLD를 써야겠다 싶었다. 노드 수 10만개, 쿼리 수 10만개로 HLD나 세그트리로 해결할 수 있을까 생각했지만 그 이상을 생각해낼 수 없었다.

HLD를 쓴다고 해도 쿼리를 날려줄 때 segtree에서 어떤 방식으로 값을 갱신해야 할지 몰랐다.

해설에는 HLD + Treap (tree + heap)을 사용해서 구간을 돌리고 뒤집는 연산을 빠르게 할 수 있다고 하는데, 공부할 게 하나 더 늘었다.

 

 

다음 챌린지때는 상품 타야지~