2020 KAKAO 코딩테스트- 외벽 점검, 파이썬

문제

---

• 프로그래머스 문제 링크

풀이

---

필요역량

• 레벨 3
• Brute force, permutation

---

• 정렬하고 간격으로 어떻게 풀어보려다 결국 테스트케이스에 실패, 다른 코드를 참고했다.
• weak 배열 크기도 작고, dist 배열 크기도 작기 때문에 완전탐색으로 문제를 풀 수 있다 (=쉽게 푼다고 머리만 쓰고 틀리지 마라)

  파이썬 순열 : from itertools import permutations

• 파이썬 순열 라이브러리 몰라서 새로 짜서 썼다. (= 어리석음)
• 배워가야할 부분은 1. 완전탐색이 가능하면 단순하게 완전탐색으로 일단 풀자. 2. 원형으로 주어진 자료를 선형으로 풀자.
• 코드 풀이는 아래 주석으로 달아놓았다.

코드

---

from itertools import permutations

def solution(n, weak, dist):
    # L = 취약 지점 개수
    L = len(weak)
    cand = []
    # 원형을 선형으로 변경, 예시 1번의 경우 [1, 5, 6, 10, 13, 17, 18, 22]
    # 출발지점이 1인경우 13까지, 6인 경우 18까지 도달해야함
    weak_point = weak + [w+n for w in weak]
    # 출발지점을 다르게 해서 모든 케이스를 시도해본다. 
    for i, start in enumerate(weak):
        # 출발지점마다 가능한 dist의 모든 경우를 체크한다. 
        for friends in permutations(dist):
            count = 1
            position = start
            for friend in friends:
                # 시작지점에서 dist 원소의 값을 더해준다.
                position += friend
                # weak_point[i+L-1]은 도달해야할 목표치 원소. 포지션이 모자르면 친구를 더씀
                if position < weak_point[i+L-1]:
                    count += 1
                    # 포지션이 취약지점에 도달하지 못하면 다음 시작지점은 도달하지 못한 취약지점으로 한다. 
                    for p in weak_point[i+1:i+L] :
                        if p > position :
                            position = p
                            break
                # 목표 취약지점에 도달하면 친구를 그만 쓰고 count를 후보(cand)리스에서 더해주고 반복문을 빠져나온다. 
                else:
                    cand.append(count)
                    break
    if not cand :
        return -1
    return min(cand)