프로그래머스 레벨3 - 카카오 2020 외벽점검

문제주소

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

내 풀이

from collections import deque
from itertools import permutations

# 항상 index 처리가 어렵다. 맨 앞, 뒤 index는 특별하게 확인해주기
def checkVisited(weak, friends):
    index = 0
    visited = [False for _ in range(len(weak))]
    for friend in friends:
        dist = 0
        while friend >= dist and index < len(weak)-1:
            visited[index] = True
            index += 1
            dist += weak[index] - weak[index - 1]
        # 끝부분 index도 처리
        if friend >= dist:
            visited[index] = True
    if False in visited:
        return False
    else:
        return True


def solution(n, weak, dist):
    answer = 1
    if len(weak) == 1:
        return answer
    q = deque(weak)
    while answer <= len(dist):
    	# 순열으로 모든 경우 탐색
        for friends in list(permutations(dist, answer)):
        	# 시작점을 변경
            for _ in range(len(weak)):
                point = q.popleft()
                q.append(point + n)
                # 가능한 경우 체크하고 가능하다면 종료
                if checkVisited(q, friends):
                    return answer
        # 탐색하는 친구의 수 추가(순열의 수 증가)
        answer += 1
    # 다 탐색했는데도 안된다면 탐색이 불가한 경우
    return -1

푸는데 상당히 오래걸렸고, 카카오 풀이에서 제공되는 힌트도 참고했다. 결국 스터디 시간안에 못 풀어서 다른 사람 풀이도 참고했다. 😂 약간 어거지로 끼워맞춘 느낌이지만 결국 풀려서 시원하다.

 

완전탐색 문제이다. 카카오 문제는 느낌뿐인지 모르겠지만 완전탐색이 많이 나오는 것 같다. 원형을 돌리는 경우 맨 앞 숫자를 빼고 뒤에 +n으로 더해주면서 그 차이만 유지하며 돌린다. (원형으로 주어진 경우 탐색 방식 --> 이렇게 탐색하면 시계방향, 반시계방향이 큰 의미가 없다.) queue를 사용하여 그 배열 값을 차이만 유지한 채 바꿔준다.

 

checkVisited에서 index 처리에 오래걸렸다. ✨index 자신이 없다면 맨 앞, 뒤 index는 특별 케이스로 처리해주자!✨ visited를 두어 bit mask로 방문 여부를 체크해주며 확인했다.

다른 사람 풀이

BFS, DFS로도 많이 풀었다고 한다. 

정리

원형으로 주어진 탐색방식, 순열로 탐색 가능한 친구의 배열을 늘려가며 탐색, bit mask, index 처리가 이 문제의 주요 키워드였다.

 

언제나 그렇든 문제를 해석하려고 하기보다는 가능하면 문제가 요구하는 대로 풀도록 하자!