[프로그래머스] 22주차 스터디 (60059 자물쇠와 열쇠, 60061 기둥과 보 설치, 60062 외벽 점검)

문제를 읽는데....
도저히 무슨 말인지 모르겠어서 다음 문제부터 풀려고 넘김
그렇게 넘기다 보니 세 문제를 다 넘기게 됨
🙄......
그래서 이번 주 풀이는 모두 책을 참고했습니다..

60059 자물쇠와 열쇠

📌문제 링크

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

💡 문제 풀이

이 문제는 입력 값이 작기 때문에 완전 탐색 (무식하게 다 비교해보는 방법)을 사용한다.

1. 자물쇠 리스트의 크기를 3배 이상으로 늘려 탐색한다. (NxN -> 3Nx3N)
2. 열쇠 배열을 왼쪽 위부터 한 칸씩 이동시키며 탐색한다. 회전하는 경우에 따라 4번 탐색한다.
3. 열쇠 부분과 자물쇠 부분을 겹쳤을 때, 자물쇠 부분이 모두 1인 경우 true를 반환한다.

📋코드

# 60059 자물쇠와 열쇠

# 2차원 리스트 시계방향 90도 회전
def rotate(a):
    n = len(a) # 행 길이
    m = len(a[0]) # 열 길이
    # 90도 회전 -> n이 열 길이, m이 행 길이가 됨
    result = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j]
    return result


# 원래 자물쇠 부분(3배 확장한 자물쇠의 가운데 부분)이 모두 1인지 확인
def check(new_lock):
    lock_length = len(new_lock)//3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                return False
    return True


def solution(key, lock):
    n = len(lock) # 자물쇠 크기
    m = len(key) # 열쇠 크기
    
    # 자물쇠 크기 3배 확장
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    
    # 새로운 자물쇠 중앙 부분에 기존의 자물쇠 값 넣기
    for i in range(n):
        for j in range(n):
            new_lock[n + i][n + j] = lock[i][j]
    
    # 4가지 회전 방향에 대해 열쇠로 자물쇠를 열 수 있는지 확인
    for rotation in range(4):
        key = rotate(key) # 열쇠 회전
        
        # 왼쪽 위부터 한 칸씩 옮기며 탐색
        for x in range(n * 2):
            for y in range(n * 2):
                # 열쇠를 자물쇠에 끼워넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                
                # 새로운 자물쇠에 열쇠가 들어맞는지 검사
                if check(new_lock) == True:
                    return True
                
                # 자물쇠에서 열쇠 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    
    # 모든 경우에도 열쇠가 자물쇠에 맞지 않는 경우
    return False

60061 기둥과 보 설치

📌문제 링크

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

💡 문제 풀이

문제에서 알려준 방법 그대로 따라가며 풀면 될 것 같다는 생각은 들었지만... 구조물이 조건을 만족하는지 어떻게 검사해야 할 지가 감이 안 잡혔다. 기둥과 보의 위치를 모두 기록해놔야하나 싶었음....

책 풀이를 보니 명령의 개수가 1000 이하이므로 명령을 수행할 때마다 구조물 전체를 확인해도 시간 안에 풀 수 있다고 한다.

📋코드

# 60061 기둥과 보 설치

# 현재 설치된 구조물이 '가능한' 구조물인지 확인
def possible(answer):
    for x, y, stuff in answer:
        # 기둥인 경우
        if stuff == 0:
            # 바닥 위, 보의 한쪽 끝부분 위, 다른 기둥 위일 때만 가능
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            # 아니라면 return False 
            return False
        # 보인 경우
        elif stuff == 1:
            # 한쪽 끝부분이 기둥 위, 양쪽 끝부분이 다른 보와 동시에 연결될 때만 가능
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                continue
            # 아니라면 return False
            return False
    
    # 모든 조건을 만족할 경우
    return True


def solution(n, build_frame):
    answer = []

    for frame in build_frame:
        x, y, stuff, operate = frame

        # 구조물을 삭제할 경우
        if operate == 0:
            # 일단 삭제한 다음
            answer.remove([x, y, stuff])
            # 가능한 구조물인지 확인
            if not possible(answer):
                # 불가능하다면 다시 설치 (작업 무시)
                answer.append([x, y, stuff])
        
        # 구조물을 설치할 경우
        if operate == 1:
            # 일단 설치한 다음
            answer.append([x, y, stuff])
            # 가능한 구조물인지 확인
            if not possible(answer):
                # 불가능하다면 다시 삭제 (작업 무시)
                answer.remove([x, y, stuff])

    return sorted(answer)

60062 외벽 점검

📌문제 링크

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

💡 문제 풀이

이 문제도 입력 데이터 개수가 작기 때문에 완전 탐색으로 풀 수 있다.

1. 원형으로 이어진 취약 지점을 선형으로 만든다. (취약 지점 2번 나열해 반시계 방향으로 도는 경우 포함)
   ex. n = 12이고 취약 지점이 1, 3, 4, 9, 10일 때
   -> 1, 3, 4, 9, 10, 13, 15, 16, 21, 22
   -> 4m에서 반시계 방향으로 7m 이동 == 9부터 16까지 시계방향 이동
   -> 모두 점검할 수 있는지는 취약지점의 개수로 검토
2. 친구를 나열하는 모든 경우의 수를 순열 라이브러리를 사용해 구한다.
3. 각각의 경우에 대해 취약 지점을 모두 검사할 수 있는지 반복하며 확인한다.
   -> 취약 지점이 있는 곳에서 시작하는 게 효율적이므로 취약 지점이 있는 곳에서부터 이동할 수 있는 거리 안에 모두 점검할 수 있는지 확인
   -> 친구를 1명 투입하는 경우부터 시작, 불가능하다면 1명씩 늘리며 확인

📋코드

# 60062 외벽 점검
from itertools import permutations

def solution(n, weak, dist):
    # 길이를 2배로 늘려 원형 벽을 선형으로 변형
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    
    # 투입할 친구의 최솟값을 비교해야 하므로 최대값보다 1 큰 수로 초기화
    answer = len(dist) + 1

    # 취약 지점을 각각 시작점으로 설정 (start : 취약 지점의 인덱스)
    for start in range(length):
        # 친구를 나열하는 모든 경우의 수에 대해 반복
        for friends in list(permutations(dist, len(dist))):
            count = 1 # 투입할 친구의 수

            # 해당 친구가 점검할 수 있는 마지막 위치
            position = weak[start] + friends[count - 1]
            
            # 시작점부터 모든 취약 지점 확인
            for index in range(start, start + length):
                # 점검할 수 있는 위치를 벗어나는 경우
                if position < weak[index]:
                    count += 1 # 투입할 친구 수 증가
                    # 친구를 더 투입할 수 없을 경우
                    if count > len(dist):
                        break

                    # 현재 위치에서 시작해 새로운 친구가 점검할 수 있는 마지막 위치 계산
                    position = weak[index] + friends[count - 1]
            
            # 투입한 친구의 최솟값 갱신
            answer = min(answer, count)
    
    # 모든 친구를 투입해도 점검할 수 없는 경우
    if answer > len(dist):
        return -1
    else:
        return answer

이번 주 스터디 후기:
레벨3는 정말로 어렵구나.......
그래도 구현을 푸는 방법을 다양하게 알게 되었다