60059, 60061, 60062 (프로그래머스)

60059(프로그래머스) 자물쇠와 열쇠

📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60059

💡 문제 풀이

• 이게 글로는 설명이 어렵지만 대충 (n+2m-2)*(n+2m-2) 크기의 보드를 만든다.
• 그 후, 자물쇠(n*n)를 보드의 가운데로 위치시킨다
• 초기 세팅으로 열쇠를 맨위 왼쪽에 위치시킨 후, 열쇠를 움직여가며(움직인 뒤 90도 회전 3번) 자물쇠와 열쇠의 홈이 일치하는지 확인한다
• 알고리즘 자체는 막 엄청 어렵지않지만, 직접 구현하는것에 시간이 들었다

뭐 풀긴 풀었지만.. 효율이 안 좋을것 같다.. ㅎㅎ
📋코드

# 자물쇠 영역의 합이 n*n이라면 정답.
# 한 구역이라도 2이상이면 돌기가 겹치는 것 이므로 건너뛴다.
def sum_check(key_board,board,n,m):
    sum = 0
    for i in range(0,n):
        for d in range(0,n):
            if board[i+m-1][d+m-1] + key_board[i+m-1][d+m-1] >= 2:
                return False
            else:
                sum += board[i+m-1][d+m-1] + key_board[i+m-1][d+m-1]
    if sum == n*n:
        return True
    else:
        return False

#0, 90, 180, 270도 바꿔가며 sum_check함수를 호출한다
def check(key_board,board,n,m):
    if sum_check(key_board,board,n,m)==True:
        return True
    for _ in range(3):
        tmp_keyboard = list([0]*(n+2*m-2) for _ in range(n+2*m-2))
        #90도 회전
        for i in range(n+2*m-2):
            for d in range(n+2*m-2):
                tmp_keyboard[d][n+2*m-3-i] = key_board[i][d]
        if sum_check(tmp_keyboard,board,n,m)==True:
            return True
        else: key_board=list(tmp_keyboard)
    return False

def solution(key, lock):
    n = len(lock)
    m = len(key)
    # n+2*m-2크기의 board를 생성한다
    board = list([0]*(n+2*m-2) for _ in range(n+2*m-2))

    # 자물쇠를 보드의 가운데에 위치시킨다
    for i in range(0,n):
        for d in range(0,n):
            board[i+m-1][d+m-1]=lock[i][d]

    # 열쇠를 맨위왼쪽부터 이동시켜가며 체크한다
    for i in range(n+m-1):
        for d in range(n+m-1):
            key_board = list([0]*(n+2*m-2) for _ in range(n+2*m-2))
            for x in range(m):
                for y in range(m):
                    key_board[i+x][d+y] = key[x][y]
            
            if check(key_board,board,n,m) == True:
                return True
            else: 
                continue
    return False
                    

60061(프로그래머스) 기둥과 보 설치

📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60061

💡 문제 풀이

• 엄청 복잡한 풀이방법은 아니였지만 풀이방법을 도출하는 시간이 오래걸렸다..

• 그리고 그걸 구현해가며 헷갈려서 더 오래걸림

• 해당 위치에 기둥 또는 보가 설치 가능한지 검사하는 check함수를 정의한다. 가능하면 true, 불가능하면 false

• 설치/제거의 경우를 나눈 뒤, check함수를 이용하여 각 경우의 모든 조건을 검사한다.

• 검사 결과에 따라 설치/제거를 한다

📋코드

#설치 가능한지 검사 (d가 true면 삭제가능한지 검사)
def check(x,y,a,board,delete):
    if delete==True and board[x][y][a]==False:
        return True
    if a==0: #기둥
        #바닥면이거나, 기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
        if y==0 or board[x][y-1][0] or (x!=0 and board[x-1][y][1]) or board[x][y][1]:
            return True
    elif a==1: #보
        #기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
        if board[x][y-1][0] or board[x+1][y-1][0] or ((x!=0 and board[x-1][y][1]) and board[x+1][y][1]):
            return True
    return False

def solution(n, build_frame):
    # board[][]의 첫 원소는 기둥, 두번째 원소는 보를 의미
    board = list([list([False,False]) for _ in range(n+1)] for _ in range(n+1))
    
    for x,y,a,b in build_frame:
        if b==0: #삭제일 경우
            board[x][y][a] = False
            if a==0:
                if not(check(x,y+1,0,board,True) and check(x,y+1,1,board,True) and check(x-1,y+1,1,board,True)):
                    board[x][y][a] = True
                    continue
            elif a==1:
                if not(check(x,y,0,board,True) and check(x+1,y,0,board,True) and check(x-1,y,1,board,True) and check(x+1,y,1,board,True)):
                    board[x][y][a] = True
                    continue
        elif b==1: #설치일 경우
            if a==0: #기둥
                #바닥면이거나, 기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
                if check(x,y,a,board,False):
                    board[x][y][0]=True
            elif a==1: #보
                #기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
                if check(x,y,a,board,False):
                    board[x][y][1]=True       
    answer = []
    for i in range(n+1):
        for d in range(n+1):
            if board[i][d][0]==True:
                answer.append([i,d,0])
            if board[i][d][1]==True:
                answer.append([i,d,1])
    return answer

60062(프로그래머스) 외벽점검

📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60062

💡 문제 풀이

풀다가 못풀겟어서 검색했다..

• d를 내림차순으로 정렬해서 큰 값부터 시작한다.
• current는 현재 weak이 된다.
• 취약지점부터해서 d 만큼 조사한다고 했을때 나머지 취약지점을 저장한다.
• 이를 반복한다. (d를 다음 순서일때 q에 저장된 취약지점을 조사해서 없어질 때까지.

📋코드

from itertools import permutations


def solution(n, weak, dist):
    weak_length = len(weak)
    # 배열을 두배 늘려주면 방향 고민할 필요 없다
    for i in range(weak_length):
        weak.append(weak[i] + n)

    answer = int(1e9)  # 점검 불가능한 경우 가정
    dist_order = list(map(list, permutations(dist, len(dist)))) 
    for i in range(weak_length):
        # 시작점을 하나씩 바꾸면서, weak의 길이만큼 잘라서 사용
        start = [weak[j] for j in range(i, i + weak_length)]
        for order in dist_order:  # 탐색
            result = 1  # 친구 활용 개수
            check_len = start[0] + order[result - 1]  # 첫번째 친구가 확인할 수 있는 최대 거리
            for k in range(weak_length):
                if start[k] > check_len:  # 확인가능한 최대거리를 넘은 경우
                    result += 1  # 활용되는 dist의 친구 수 추가
                    # 더 이상 투입 인원이 없는 경우
                    if result > len(order):
                        break
                    # 다음 친구가 확인할 수 있는 거리 업데이트
                    check_len = start[k] + order[result - 1]

            answer = min(answer, result)

    if answer > len(dist):
        return -1
    return answer