2020 KAKAO BLIND RECRUITMENT - 외벽 점검

끝이 다 와갑니다. KAKAO 외벽 점검 문제입니다.

 

https://programmers.co.kr/learn/courses/30/lessons/60062?language=python3#

코딩테스트 연습 - 외벽 점검

이 문제 역시 코딩테스트 당시 도망쳤던 문제죠.

튀어 !

다시 풀어봅시다 !!

---

문제를 읽어보셨다면, 문제 변수들의 범위가 작은 것을 알 수 있습니다.

 

완전 탐색으로 풀어라는거죠.

 

그 때 당시엔 잘 몰랐는데, 이제는 어떻게 접근을 해야하는지 슬슬 보이기 시작하네요.

그래도 어려운건 똑같음 ㅋ

저는 처음에 이 문제를 접근했을 때, DFS로 접근을 했습니다.

 

거리 범위를 가장 넓게 잡을 수 있는 친구부터 순서대로 한 군데씩 넣어가면서, 풀어봤었는데, 시간 초과가 뜨더라고요.

 

그 시간 초과를 극복하기 위해서 다른 방식으로 접근을 해봤습니다.

 

어떻게 접근을 해야했는지, 순서대로 알아보도록 합시다.

 

1. 결론은 약점을 극복할 수 있는 친구 최소 인원 수를 알아야 합니다. ==> 이 수가 정답

 

2. 친구의 범위로 어떻게 약점을 책임질 것인지 계산해야 합니다. ==> 문제를 해결할 수 있는지 여부 확인

 

3. 시계 방향으로 돌면서 친구들에게 할당시킬 약점을 모두 알아봐야 합니다. ==> 전체 탐색

 

앞에 시간 초과가 떴었다고 했었죠?

 

그 이유가 3번에서 시계방향으로 전체 탐색을 했음에도, 반시계 방향으로 한 번 더 전체 탐색을 진행해서 시간 초과가 떴었던 것이었습니다.

 

즉, 같은 짓을 두 번 한거죠.

 

1번의 경우엔,

 

처음엔 1명, 그 다음 2명, ... 그 다음 len(dist) 명까지 인원 수 만큼, 2번 함수에 범위를 보내가면서 확인하면 됩니다. (그 인원 수로 문제가 해결 가능한지) 

 

2번의 경우엔 방문 처리를 하면서 해결하면 될 것이고,

 

3번의 경우가 좀 아이디어 싸움인데, 완전 탐색 시작점을 정해줘야 합니다.

 

한마디로 친구들에게 할당시킬 약점을 정해줘야 한다는 것이죠. 짝짓기처럼

 

[1, 5, 9, 15]가 약점이라 했을 때 7, 3, 2를 확인하고 싶다면

 

[1, 5, 9, 15]

[5, 9, 15, n + 1]

[9, 15, n + 1, n + 5]

[15, n + 1, n + 5, n + 9]

 

이렇게 시작점을 바꿔가면서 이 중 반복문으로 확인하시면 됩니다.

 

이 아이디어가 이 문제에서 가장 중요했던거 같습니다.

 

코드 보시죠.

from itertools import permutations

weaks = []

def make_weaks(n, weak):
    cnt = 1
    weaks.append(weak)
    while cnt != len(weak):
        temp = []
        for i in range(cnt, len(weak)):
            temp.append(weak[i])
        for i in range(cnt):
            temp.append(weak[i] + n)
        weaks.append(temp)
        cnt += 1

def check(per):
    for weak in weaks:
        visited = [0 for _ in range(len(weak))]
        idx = 0
        for num in per:
            if visited[idx] == 0:
                visited[idx] = 1
                are = weak[idx] + num
                idx += 1
                for w in weak[idx:]:
                    if w <= are:
                        visited[idx] = 1
                        idx += 1
                    else: 
                        break
        if 0 in visited:
            continue
        else:
            return 1


def build(cnt, dist):
    pers = permutations(dist, cnt)
    for per in pers:
        if check(per):
            return 1
    return 0


def solution(n, weak, dist):
    make_weaks(n, weak)
    for cnt in range(1, len(dist) + 1):
        if build(cnt, dist):
            return cnt
    return -1

그렇게 쉽지만은 않았던 문제였습니다.

---

이상 2020 KAKAO BLIND RECRUITMENT - 외벽 점검 였습니다. ^_^