231121 - kakao2020 : 재귀 특징 활용, 배열회전+확장, 배열없는시뮬, 트라이활용, 원형탐색->선형, BFS+두개블록+이동및회전

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/60058

괄호 변환 (재귀 특징 활용)

올바른 괄호쌍이라는 친숙한 내용과 관련된 문제입니다. 문제에는 짝이 맞지 않는 괄호가 주어졌을 때, 이를 짝이 맞는 괄호로 변환하는 방법이 제시되었습니다. 괄호쌍을 확인하는 방법과 재귀함수에 대해 이해하고 있고, 문제에 주어진 대로 정확히 코딩할 수 있다면 어렵지 않게 해결할 수 있었습니다.

def divide(p):
    open_p = 0
    close_p = 0

    for i in range(len(p)):
        if p[i] == "(":
            open_p += 1
        else:
            close_p += 1
        if open_p == close_p:
            return p[:i+1], p[i+1:]

def check(S):
    stack = []
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if not stack:
                return False
            stack.pop()
    return True

def solution(p):

    if not p:
        return ""

    # u, v를 분리
    u, v = divide(p)
    if check(u):
        # 제일 처음 올바른 괄호가 앞에 붙음
        return u + solution(v)
    else:
        # 올바르지 않은 괄호가 나왔을 대 아래 절차대로 진행
        answer = '('
        answer += solution(v)
        answer += ')'

        for s in u[1:len(u) - 1]:
            if s == "(":
                answer += ')'
            else:
                answer += '('

    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/60057

문자열 압축

첫 번째로 배치된, 가장 쉬운 문제입니다. 문자열 길이가 최대 1,000으로 제한이 크지 않기 때문에, 가능한 모든 방법을 탐색하면 됩니다. 문자열 길이가 N일 때, 길이가 N/2 보다 크게 잘랐을 때는 길이가 줄지 않습니다. 따라서 1 ~ N/2 길이로 자르는 방법을 모두 탐색한 후 그중 가장 짧은 방법을 선택하면 됩니다.

def solution(s):
    n = len(s)
    answer = n

    for k in range(1, n // 2 + 1):
        string = ""
        prev = ""
        cnt = 1
        for i in range(0, n, k):
            # print(s[i:i+k], end = " ")
            if prev == s[i:i+k]:
                cnt += 1
            else:
                if cnt >= 2:
                    string += str(cnt) + prev
                    cnt = 1
                else:
                    string += prev
                prev = s[i:i+k]
        if prev:
            if cnt >= 2:
                string += str(cnt) + prev
            else:
                string += prev

        answer = min(answer, len(string))

    return answer

[robert-min]

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

자물쇠와 열쇠 (배열회전+확장)

제한이 크지 않기 때문에 가능한 모든 경우를 탐색해 볼 수 있습니다. 2차원 배열을 회전하는 함수를 하나 만들어 둔다면 코드를 더욱 깔끔하게 작성할 수 있습니다.

최대 4번까지 배열을 회전시키면서 가능한 경우를 모두 탐색한 다음, 자물쇠의 모든 홈을 채워 비어있는 곳이 없도록 할 수 있다면 true를, 그렇지 않다면 false를 return 하면 됩니다.

key와 lock을 순서대로 맞춰보는 방법 중 하나는 우선 lock 배열을 가로, 세로 길이가 3배인 새로운 배열의 중앙 부분으로 옮긴 후, key 배열을 새로운 배열의 좌측 상단부터 순서대로 이동시키면서 겹치는 부분만 확인해보면 됩니다. 이때, 겹치는 부분은 자물쇠의 모든 홈이 채워지더라도, 겹치지 않는 부분에 여전히 자물쇠의 홈 부분이 남아있을 수 있으므로 모든 홈이 채워졌는지를 정확히 확인해야 합니다.

def attach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] += key[i][j]

def detach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] -= key[i][j]

def rotate90(arr):
    return list(zip(*arr[::-1]))

def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M+i][M+j] != 1:
                return False;
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
    # 자물쇠 중앙 배치
    for i in range(N):
        for j in range(N):
            board[M+i][M+j] = lock[i][j]

    rotated_key = key
    # 모든 방향 (4번 루프)
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        # 위 아래 이동
        for x in range(1, M+N):
            for y in range(1, M+N):
                # 열쇠 넣어보기
                attach(x, y, M, rotated_key, board)
                # lock 가능 check
                if(check(board, M, N)):
                    return True
                # 열쇠 빼기
                detach(x, y, M, rotated_key, board)

    return False

[robert-min]

!!! 모든 구현 문제가 꼭 matrix에 저장해서 풀 필요가 없음

• 이 문제를 보면 이전까지 설치할 수 있는 좌표만 따로 저장해서 확인하면 됨!!!!!!!

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

기둥과 보 (배열없는시뮬)

• 주어진 대로 시뮬레이션 하면 되는 문제입니다. 기둥과 보를 설치하거나 삭제할 때, 인접한 기둥과 보가 조건을 만족하는지 정확하게 확인해야 합니다.

  
  def check(answer):
  for x, y, stuff in answer:
      if stuff == 0: #기둥 체크
          #'바닥 위' or '보의 한쪽 끝 위' or '또 다른 기둥 위' 
          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
      elif stuff == 1: #보 체크
          #'한쪽 끝 부분이 기둥 위' or '양쪽 끝 부분이 다른 보와 동시 연결'
          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 True

def solution(n, build_frame): answer = [] for build in build_frame: x, y, stuff, operation = build if operation == 1: # 설치 answer.append([x, y, stuff]) if not check(answer): answer.remove([x, y, stuff]) elif operation == 0: # 삭제 answer.remove([x, y, stuff]) if not check(answer): answer.append([x, y, stuff]) answer.sort() return answer

[robert-min]

가사검색 (트라이활용)

• 정확성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하면서 개수를 세면 됩니다.
• 효율성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하는 방법으로는 효율성 풀이를 통과할 수 없습니다. queries에 담긴 문자열이 words에 있는지 탐색하는 효율적인 방법으로 트라이(Trie) 자료구조를 사용할 수 있습니다.이때, 원래 문자열을 이용해 만든 트라이와, 문자열을 뒤집어서 만든 트라이 두 개를 이용해야 합니다. ???가 접두사인 경우는, 문자열을 뒤집어서 ???가 접미사로 나온다고 생각할 수 있기 때문입니다. 예를 들어, “??ost”의 경우 “tso??”로 생각할 수 있습니다.단어를 트라이에 넣을 때는 길이에 따라 서로 다른 트라이에 넣어줘야 합니다. 같은 접두사를 가지더라도 길이에 따라 개수가 달라질 수 있기 때문입니다. 단어 하나의 길이가 최대 1만이기 때문에 길이가 1인 문자열을 넣을 트라이부터 길이가 1만인 문자열을 넣을 트라이까지 생성합니다. 이제 각 단어별로 길이에 맞는 트라이에 넣어줍니다.단어를 넣을 때는 각 문자별로 해당 노드의 count를 1씩 증가시켜 줍니다. 이후에 단어를 검색할 때는 접두사에 해당하는 노드까지 이동한 후 해당 노드의 count를 return 하면 됩니다.이 외에도 문자열을 정렬한 다음 이분탐색하는 방법 등을 사용할 수 있습니다.

  
  class Node(object):
  def __init__(self, key):
      self.key = key
      self.count = 0
      self.children = {}

class Trie(object): def init(self): self.head = Node(self)

def insert(self, string):
    curr_node = self.head

    for char in string:
        curr_node.count += 1
        if char not in curr_node.children:
            curr_node.children[char] = Node(char)

        curr_node = curr_node.children[char]

    curr_node.count += 1

def starts_with(self, prefix):
    curr_node = self.head
    result = 0

    for char in prefix:
        if char == "?":
            break

        if char in curr_node.children:
            curr_node = curr_node.children[char]
        else:
            return 0
    return curr_node.count

def solution(words, queries): answer = [] tries = {} reverse_tries = {}

for word in words:
    if len(word) in tries:
        tries[len(word)].insert(word)
        reverse_tries[len(word)].insert(reversed(word))
    else:
        trie = Trie()
        reverse_trie = Trie()

        trie.insert(word)
        reverse_trie.insert(reversed(word))

        tries[len(word)] = trie
        reverse_tries[len(word)] = reverse_trie

for query in queries:
    if len(query) in tries:
        if query[0] != "?":
            trie = tries[len(query)]
            answer.append(trie.starts_with(query))
        else:
            trie = reverse_tries[len(query)]
            answer.append(trie.starts_with(reversed(query)))
    else:
        answer.append(0)    

return answer

[robert-min]

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

외벽 점검 (원형탐색->선형으로변환)

dist의 길이가 최대 8로 크지 않기 때문에, 가능한 모든 방법을 탐색해서 해결할 수 있습니다. 따라서 dist에서 친구 한 명을 선택해 나열하는 방법, 친구 두 명을 선택해 나열하는 방법 … 친구 여덟 명을 선택해 나열하는 방법을 모두 고려해주면 됩니다.

이제 각각의 방법에 대해 취약지점을 모두 점검할 수 있는지 확인합니다. 먼저 점검해야 될 벽이 원형이 아니라 직선이라고 가정해 보면, 모든 취약지점을 점검하기 위해서는 시작 지점부터 순서대로 배정해야 된다는 점을 알 수 있습니다. 친구 한 명을 배정한 다음에는 아직 점검하지 않은 지점 중에서 바로 다음 지점에 친구를 순서대로 배정하면 됩니다.

배정을 마친 후에도 아직 점검하지 않은 취약지점이 남아있다면 해당 배치 방법으로는 모든 취약지점을 점검할 수 없다는 뜻입니다. 이제, 원형으로 이루어진 벽을 고려하기 위해, 다음 시작 지점을 기준으로 직선으로 펼쳐주면 됩니다.

예를 들어, N = 12, weak = [1, 5, 6, 10]인 경우 처음에 위치 1을 기준으로 직선으로 펼쳤다면, 이번에는 위치 5를 기준으로 [5, 6, 10, 13]과 같이 직선 형태로 만들어 주면 됩니다. 이때, 13은 값이 증가하는 형태로 만들어 주기 위해 1 + 12를 해준 결과입니다.

이제 각 친구들을 선택해 나열하는 방법에 대해서 모든 시작 지점에 대해 직선으로 펼친 후 취약 지점에 배정해본 다음, 그중 가장 적은 친구들을 선택하는 방법을 찾으면 됩니다.

from itertools import permutations

def solution(n, weak, dist):
    result = []
    L = len(weak)

    # 선형으로
    weak_point = weak + [w+n for w in weak]

    for i, start in enumerate(weak):
        # 친구들을 배치할 수 있는 모든 경우의 수
        for friends in permutations(dist):
            cnt = 1
            position = start

            for friend in friends:
                position += friend

                # 도달 못했을 때
                if position < weak_point[i+L-1]:
                    cnt += 1 # 친구 더 투입
                    # 현재 위치 보다 멀리 있는 취약 지점 중 가까운 위치로
                    position = [w for w in weak_point[i+1: i+L] if w > position][0]
                else:
                    # 도달 했을 때
                    result.append(cnt)

    answer = -1
    if result:
        answer = min(result)

    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/60063

블록 이동하기(BFS+두개블록+이동및회전)

BFS를 이용해 해결할 수 있지만, 코딩에 상당한 난이도를 요구했던 문제입니다. 기본적으로 간선의 비용이 1인 최단거리 문제와 동일하나, 로봇이 회전할 수 있다는 점을 신경 써야 합니다.

먼저 현재 로봇의 상태를 표현하기 위해 다음과 같이 상태를 정의해줍니다.

(r, c, d) : (r, c) 위치에서 d 방향에 있는 칸을 한 칸 더 차지하고 있음

로봇이 두 칸을 차지하고 있기 때문에 로봇이 (r, c), (r, c + 1) 위치에 놓인 경우, (r, c) 위치에서 (r, c + 1) 칸을 한 칸 더 차지하고 있음과 (r, c + 1) 위치에서 (r, c) 칸을 한 칸 더 차지하고 있음이 같은 상태라는 점을 주의해야 합니다.

현재 상태에서 로봇이 움직이는 방법은 다음과 같이 8가지입니다.

로봇이 상, 하, 좌, 우로 움직임(4가지) 로봇이 첫 번째 칸을 기준으로 시계방향, 반시계 방향으로 회전(2가지) 로봇이 두 번째 칸을 기준으로 시계방향, 반시계 방향으로 회전(2가지)

로봇이 회전하는 경우 벽과 충돌하면 안 되기 때문에, 충돌 판정은 다음과 같이 할 수 있습니다.

로봇은 항상 수평, 또는 수직으로만 놓이기 때문에, 충돌 확인을 해야 하는 후보칸은 회전축을 기준으로 대각선 방향에 있는 칸 4개입니다. 충돌 확인을 해야 하는 칸은 회전하기 전에 로봇이 위치한 칸(축이 아닌 칸)까지의 맨해튼 거리와 회전한 후에 로봇이 새로 위치한 칸까지의 맨해튼 거리가 1입니다.

이를 이용해 회전 후 충돌 판정을 확인해야 되는 칸이 어디인지 찾아낼 수 있습니다. 이외에도 다양한 방법을 이용해 충돌 판정을 확인할 수 있습니다.

이제 각각의 상태에 대해 BFS 탐색을 진행하면서 가장 빠른 시간을 찾으면 됩니다.

from collections import deque

def can_move(cur1, cur2, new_board):
    Y, X = 0, 1
    cand = []
    # 평행이동
    DELTAS = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for dy, dx in DELTAS:
        nxt1 = (cur1[Y] + dy, cur1[X] + dx)
        nxt2 = (cur2[Y] + dy, cur2[X] + dx)
        if new_board[nxt1[Y]][nxt1[X]] == 0 and new_board[nxt2[Y]][nxt2[X]] == 0:
            cand.append((nxt1, nxt2))
    # 회전
    if cur1[Y] == cur2[Y]: # 가로방향 일 때
        UP, DOWN = -1, 1
        for d in [UP, DOWN]:
            if new_board[cur1[Y]+d][cur1[X]] == 0 and new_board[cur2[Y]+d][cur2[X]] == 0:
                cand.append((cur1, (cur1[Y]+d, cur1[X])))
                cand.append((cur2, (cur2[Y]+d, cur2[X])))
    else: # 세로 방향 일 때
        LEFT, RIGHT = -1, 1
        for d in [LEFT, RIGHT]:
            if new_board[cur1[Y]][cur1[X]+d] == 0 and new_board[cur2[Y]][cur2[X]+d] == 0:
                cand.append(((cur1[Y], cur1[X]+d), cur1))
                cand.append(((cur2[Y], cur2[X]+d), cur2))

    return cand

def solution(board):
    # board 외벽 둘러싸기
    N = len(board)
    new_board = [[1] * (N+2) for _ in range(N+2)]
    for i in range(N):
        for j in range(N):
            new_board[i+1][j+1] = board[i][j]

    # 현재 좌표 위치 큐 삽입, 확인용 set
    que = deque([((1, 1), (1, 2), 0)])
    confirm = set([((1, 1), (1, 2))])

    while que:
        cur1, cur2, count = que.popleft()
        if cur1 == (N, N) or cur2 == (N, N):
            return count
        for nxt in can_move(cur1, cur2, new_board):
            if nxt not in confirm:
                que.append((*nxt, count+1))
                confirm.add(nxt)