외벽 점검

외벽 점검
2020 KAKAO BLIND RECRUITMENT
637명 완료

https://programmers.co.kr/learn/courses/30/lessons/60062

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

공식 해설
https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

효율성 테스트가 없길래 혹시나 해서
재귀(깊이우선탐색)로 풀어보았습니다.
결과는 역시나... 실패...

def solution(n, weak, dist):
    result = repair(n, set(weak), dist[:])
    return -1 if result == -1 else len(dist) - result


def repair(n, weak, dist):
    if not weak:
        return len(dist)
    if not dist:
        return -1
    width = dist.pop()
    max_val = -1
    for start in weak:
        visited = set()
        for point in weak:
            if start <= point <= start + width or start <= point + n <= start + width:
                visited.add(point)
        max_val = max(max_val, repair(n, weak - visited, dist[:]))
    return max_val

테스트 1 〉	통과 (0.25ms, 9.61MB)
테스트 2 〉	통과 (0.26ms, 9.52MB)
테스트 3 〉	통과 (9001.59ms, 9.49MB)
테스트 4 〉	통과 (2331.66ms, 9.64MB)
테스트 5 〉	통과 (12.44ms, 9.45MB)
테스트 6 〉	통과 (1632.81ms, 9.53MB)
테스트 7 〉	통과 (0.07ms, 9.45MB)
테스트 8 〉	통과 (1.22ms, 9.68MB)
테스트 9 〉	통과 (1.11ms, 9.53MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	통과 (380.90ms, 9.49MB)
테스트 17 〉	통과 (2010.03ms, 9.68MB)
테스트 18 〉	통과 (472.27ms, 9.44MB)
테스트 19 〉	통과 (5.93ms, 9.49MB)
테스트 20 〉	통과 (39.36ms, 9.59MB)
테스트 21 〉	통과 (5.11ms, 9.53MB)
테스트 22 〉	통과 (3.90ms, 9.58MB)
테스트 23 〉	통과 (5.26ms, 9.43MB)
테스트 24 〉	통과 (4.59ms, 9.43MB)
테스트 25 〉	통과 (2.31ms, 9.6MB)

해설을 보니 순열도 된다고 하네요... 쉽고 간단하니.. 한번...

def solution(n, weak, dist):
    from itertools import permutations
    result = float('inf')
    for split_index in range(len(weak)):
        new_weak = weak[split_index:] + [each + n for each in weak[:split_index]]
        for widths in permutations(dist):
            points = new_weak[::-1]
            for width_index, width in enumerate(widths):
                point = points.pop()
                for neighbor in tuple(points):
                    if point < neighbor <= point + width:
                        points.remove(neighbor)
                if not points:
                    result = min(result, width_index + 1)
                    break
    return -1 if result == float('inf') else result

테스트 1 〉	통과 (0.24ms, 9.54MB)
테스트 2 〉	통과 (0.24ms, 9.52MB)
테스트 3 〉	통과 (2238.86ms, 9.57MB)
테스트 4 〉	통과 (1840.25ms, 9.54MB)
테스트 5 〉	통과 (4.96ms, 9.67MB)
테스트 6 〉	통과 (460.28ms, 9.59MB)
테스트 7 〉	통과 (0.10ms, 9.68MB)
테스트 8 〉	통과 (1.21ms, 9.53MB)
테스트 9 〉	통과 (1.18ms, 9.43MB)
테스트 10 〉	통과 (4120.22ms, 9.72MB)
테스트 11 〉	통과 (4093.35ms, 9.67MB)
테스트 12 〉	통과 (4091.18ms, 9.54MB)
테스트 13 〉	통과 (4270.81ms, 9.51MB)
테스트 14 〉	통과 (4181.27ms, 9.71MB)
테스트 15 〉	통과 (4025.57ms, 9.5MB)
테스트 16 〉	통과 (3142.15ms, 9.68MB)
테스트 17 〉	통과 (3431.62ms, 9.58MB)
테스트 18 〉	통과 (3374.64ms, 9.75MB)
테스트 19 〉	통과 (2613.99ms, 9.71MB)
테스트 20 〉	통과 (3009.59ms, 9.54MB)
테스트 21 〉	통과 (2716.36ms, 9.62MB)
테스트 22 〉	통과 (1.22ms, 9.54MB)
테스트 23 〉	통과 (1.24ms, 9.5MB)
테스트 24 〉	통과 (1.22ms, 9.61MB)
테스트 25 〉	통과 (607.40ms, 9.5MB)

로직 자체는 단순하지만
weak 리스트를 계속 만져줘야 된다던지 (이럴 땐 변수명 정하는 것도 피곤한 일)
for를 4개나 동원한다던지
약간 까다로운 문제.. 

순열로만 풀기에는 뭔가 아쉬워서... 

너비 우선 탐색으로 검색하면 뭔가 다를까?

예전에 비슷한 문제를 풀어본 적 있습니다.
https://comdoc.tistory.com/entry/%EB%8B%A8%EC%96%B4%EB%B3%80%ED%99%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC 

def solution(n, weak, dist):
    level, remains = repair(dist, {tuple(weak)}, 0, len(dist), n)
    return level if () in remains else -1


def repair(dist, remains, level, max_level, n):
    if level == max_level or not dist or () in remains:
        return level, remains
    width = dist.pop()
    new_remains = set()
    for points in remains:
        for start in points:
            remained_points = []
            for point in points:
                if not (start <= point <= start + width or start <= point + n <= start + width):
                    remained_points.append(point)
            new_remains.add(tuple(remained_points))
    level += 1
    return repair(dist, new_remains, level, max_level, n)

테스트 1 〉	통과 (0.03ms, 9.6MB)
테스트 2 〉	통과 (0.08ms, 9.52MB)
테스트 3 〉	통과 (16.24ms, 9.71MB)
테스트 4 〉	통과 (7.50ms, 9.68MB)
테스트 5 〉	통과 (1.94ms, 9.53MB)
테스트 6 〉	통과 (23.37ms, 10.2MB)
테스트 7 〉	통과 (0.03ms, 9.46MB)
테스트 8 〉	통과 (0.13ms, 9.53MB)
테스트 9 〉	통과 (0.37ms, 9.52MB)
테스트 10 〉	통과 (111.40ms, 12.7MB)
테스트 11 〉	통과 (88.53ms, 10.9MB)
테스트 12 〉	통과 (62.50ms, 10.6MB)
테스트 13 〉	통과 (543.43ms, 17.2MB)
테스트 14 〉	통과 (212.54ms, 13.9MB)
테스트 15 〉	통과 (46.53ms, 10.5MB)
테스트 16 〉	통과 (2.01ms, 9.52MB)
테스트 17 〉	통과 (10.80ms, 9.66MB)
테스트 18 〉	통과 (4.28ms, 9.56MB)
테스트 19 〉	통과 (0.28ms, 9.59MB)
테스트 20 〉	통과 (1.43ms, 9.49MB)
테스트 21 〉	통과 (0.30ms, 9.44MB)
테스트 22 〉	통과 (1.78ms, 9.64MB)
테스트 23 〉	통과 (2.68ms, 9.5MB)
테스트 24 〉	통과 (2.39ms, 9.48MB)
테스트 25 〉	통과 (0.25ms, 9.52MB)

헐 빠름~!

재귀를 반복으로

def solution(n, weak, dist):
    remains = {tuple(weak)}
    level = 0
    max_level = len(dist)
    while level != max_level and dist and () not in remains:
        width = dist.pop()
        new_remains = set()
        for points in remains:
            for start in points:
                remained_points = []
                for point in points:
                    if not (start <= point <= start + width or start <= point + n <= start + width):
                        remained_points.append(point)
                new_remains.add(tuple(remained_points))
        remains = new_remains
        level += 1
    return level if () in remains else -1

테스트 1 〉	통과 (0.03ms, 9.49MB)
테스트 2 〉	통과 (0.08ms, 9.49MB)
테스트 3 〉	통과 (16.18ms, 9.77MB)
테스트 4 〉	통과 (7.43ms, 9.54MB)
테스트 5 〉	통과 (1.97ms, 9.54MB)
테스트 6 〉	통과 (23.34ms, 10MB)
테스트 7 〉	통과 (0.03ms, 9.65MB)
테스트 8 〉	통과 (0.13ms, 9.48MB)
테스트 9 〉	통과 (0.31ms, 9.68MB)
테스트 10 〉	통과 (114.54ms, 12MB)
테스트 11 〉	통과 (91.15ms, 10.3MB)
테스트 12 〉	통과 (63.47ms, 10.2MB)
테스트 13 〉	통과 (554.94ms, 14.4MB)
테스트 14 〉	통과 (223.14ms, 12.5MB)
테스트 15 〉	통과 (46.81ms, 10.2MB)
테스트 16 〉	통과 (1.89ms, 9.6MB)
테스트 17 〉	통과 (9.82ms, 9.58MB)
테스트 18 〉	통과 (4.34ms, 9.54MB)
테스트 19 〉	통과 (0.27ms, 9.45MB)
테스트 20 〉	통과 (1.47ms, 9.4MB)
테스트 21 〉	통과 (0.29ms, 9.46MB)
테스트 22 〉	통과 (1.72ms, 9.63MB)
테스트 23 〉	통과 (3.04ms, 9.54MB)
테스트 24 〉	통과 (2.09ms, 9.45MB)
테스트 25 〉	통과 (0.25ms, 9.54MB)

뭔 코드인지 모를 정도로 줄이면 ..... 7줄.... 헐....

def solution(n, weak, dist):
    level, max_level, remains = 0, len(dist), {tuple(weak)}
    while level != max_level and dist and () not in remains:
        width = dist.pop()
        remains = set(tuple(point for point in points if not (start <= point <= start + width or start <= point + n <= start + width)) for points in remains for start in points)
        level += 1
    return level if () in remains else -1

테스트 1 〉	통과 (0.03ms, 9.57MB)
테스트 2 〉	통과 (0.09ms, 9.66MB)
테스트 3 〉	통과 (18.46ms, 10.4MB)
테스트 4 〉	통과 (9.33ms, 9.85MB)
테스트 5 〉	통과 (2.65ms, 9.66MB)
테스트 6 〉	통과 (25.96ms, 11MB)
테스트 7 〉	통과 (0.04ms, 9.52MB)
테스트 8 〉	통과 (0.15ms, 9.43MB)
테스트 9 〉	통과 (0.49ms, 9.5MB)
테스트 10 〉	통과 (121.54ms, 13.6MB)
테스트 11 〉	통과 (98.21ms, 11.9MB)
테스트 12 〉	통과 (66.94ms, 11.5MB)
테스트 13 〉	통과 (576.62ms, 15.4MB)
테스트 14 〉	통과 (233.78ms, 13.8MB)
테스트 15 〉	통과 (50.68ms, 11.5MB)
테스트 16 〉	통과 (2.03ms, 9.45MB)
테스트 17 〉	통과 (10.72ms, 10.1MB)
테스트 18 〉	통과 (4.81ms, 9.71MB)
테스트 19 〉	통과 (0.31ms, 9.45MB)
테스트 20 〉	통과 (1.71ms, 9.5MB)
테스트 21 〉	통과 (0.33ms, 9.53MB)
테스트 22 〉	통과 (1.96ms, 9.55MB)
테스트 23 〉	통과 (3.03ms, 9.77MB)
테스트 24 〉	통과 (2.53ms, 9.74MB)
테스트 25 〉	통과 (0.31ms, 9.46MB)