[프로그래머스][KAKAO_BLIND][2020] 외벽 점검

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from itertools import combinations
from bisect import bisect_right, bisect_left

def solution(n, weak, dist):
    to_check = len(weak)
    weak += [i+n for i in weak]
    all_checked = set()
    for num_friend, l in enumerate(sorted(dist, reverse=True)):
        num_friend += 1
        checked = set()
        for s_i, s in enumerate(weak):
            e = s + l
            e_i = bisect_right(weak, e)
            checked.add(frozenset(map(lambda x: x % n, weak[s_i:e_i])))

        nw_checked = set()
        for now in checked:
            if len(now) == to_check:
                return num_friend
            nw_checked.add(now)
            for before in all_checked:
                nw = now | before
                if len(nw) == to_check:
                    return num_friend
                nw_checked.add(nw)
        all_checked = nw_checked

    return -1

• 원형 큐
  
  • 마지막과 처음이 이어지는 경우를 고려하기 위해 weak를 2배로 만들어줌
• 집합
  • 탐색한 모든 weak를 set으로 저장
  • 친구가 추가될 때마다 합집합으로 탐색 weak들을 누적하여 확인
  • 모든 weak를 탐색하면 종료

 

다른 사람이 작성한 코드

def solution(n, weak, dist):

    W, F = len(weak), len(dist)
    repair_lst = [()]  # 현재까지 고칠 수 있는 취약점들 저장 (1,2,3)
    count = 0  # 투입친구 수
    dist.sort(reverse=True) # 움직일 수 있는 거리가 큰 친구 순서대로

    # 고칠 수 있는 것들 리스트 작성
    for can_move in dist:
        repairs = []  # 친구 별 고칠 수 있는 취약점들 저장
        count += 1

        # 수리 가능한 지점 찾기
        for i, wp in enumerate(weak):
            start = wp  # 각 위크포인트부터 시작
            ends = weak[i:] + [n+w for w in weak[:i]]  # 시작점 기준 끝 포인트 값 저장
            can = [end % n for end in ends if end -
                   start <= can_move]  # 가능한 지점 저장
            repairs.append(set(can))

        # 수리 가능한 경우 탐색
        cand = set()
        for r in repairs:  # 새친구의 수리가능 지점
            for x in repair_lst:  # 기존 수리가능 지점
                new = r | set(x)  # 새로운 수리가능 지점
                if len(new) == W:  # 모두 수리가능 한 경우 친구 수 리턴
                    return count
                cand.add(tuple(new))
        repair_lst = cand

    return -1

• 집합을 이용한 완전탐색방식
  
  • 처음에 Combination으로 r을 하나씩 증가시키려 했는데 너무 복잡했다
  • 집합을 이용하는 방식을 위 코드에서 배웠다

https://velog.io/@tjdud0123/%EC%99%B8%EB%B2%BD-%EC%A0%90%EA%B2%80-2020-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-python

외벽 점검 - 2020 카카오 공채 (python)

 

기억해야할 것

• 원형 큐
  
  • 원형 큐 문제를 처음 접해봐서 해매었다
  • 비슷한 문제를 더 풀어보고 싶어서 아래 문제를 풀었다
•  집합
  • 집합으로 탐색 영역을 표시하는 방법은 유용할 것 같아서 기억해둬야겠다

2021.08.30 - [[개발] 공부하기/코딩테스트] - [백준][분할정복] 퍼즐 자르기

[백준][분할정복] 퍼즐 자르기