JH 개발 블로그

from collections import deque


def rotate(lr, lc, rr, rc, board):
    locs = []

    for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        nlr, nlc, nrr, nrc = lr + dr, lc + dc, rr + dr, rc + dc
        if board[nlr][nlc] == 1 or board[nrr][nrc] == 1:
            continue
        locs.append((nlr, nlc, nrr, nrc))

    if lr == rr:
        if lc < rc:
            if board[lr - 1][lc + 1] == 0 and board[lr - 1][lc] == 0:  # 반시계
                locs.append((lr, lc, lr - 1, lc))
            if board[lr + 1][lc + 1] == 0 and board[lr + 1][lc] == 0:  # 시계
                locs.append((lr, lc, lr + 1, lc))
        else:
            if board[lr + 1][lc - 1] == 0 and board[lr + 1][lc] == 0:  # 반시계
                locs.append((lr, lc, lr + 1, lc))
            if board[lr - 1][lc - 1] == 0 and board[lr - 1][lc] == 0:  # 시계
                locs.append((lr, lc, lr - 1, lc))

    else:
        if lr < rr:
            if board[lr + 1][lc + 1] == 0 and board[lr][lc + 1] == 0:  # 반시계
                locs.append((lr, lc, lr, lc + 1))
            if board[lr + 1][lc - 1] == 0 and board[lr][lc - 1] == 0:  # 시계
                locs.append((lr, lc, lr, lc - 1))
        else:
            if board[lr - 1][lc - 1] == 0 and board[lr][lc - 1] == 0:  # 반시계
                locs.append((lr, lc, lr, lc - 1))
            if board[lr - 1][lc + 1] == 0 and board[lr][lc + 1] == 0:  # 시계
                locs.append((lr, lc, lr, lc + 1))

    return locs


def solution(board):
    n = len(board)
    board = [[1] * (n + 2)] + [[1] + b + [1] for b in board] + [[1] * (n + 2)]
    q = deque([[1, 1, 1, 2, 0]])
    visited = set()

    while q:
        lr, lc, rr, rc, cnt = q.popleft()
        if (lr, lc, rr, rc) in visited:
            continue
        if (lr, lc) == (n, n) or (rr, rc) == (n, n):
            return cnt
        visited.add((lr, lc, rr, rc))

        for loc in rotate(lr, lc, rr, rc, board) + rotate(rr, rc, lr, lc, board):
            q.append([*loc, cnt + 1])

최단경로 => bfs

하지만 이문제는 좌표를 두개 차지한다는 점과, 회전시킨다는 조건이 있어서 구현이 어려웠음

기계를 왼쪽, 오른쪽으로 나눠서 왼쪽을 축으로 회전하고, 오른쪽을 축으로 한번 더 회전해야한다.

따라서 rotate 함수를 두번 사용했다. 

밑에 코드는 rotate 함수를 좀 더 간단하게 줄인 코드

from collections import deque


def rotate(lr, lc, rr, rc, board):
    locs = []

    for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        nlr, nlc, nrr, nrc = lr + dr, lc + dc, rr + dr, rc + dc
        if board[nlr][nlc] == 1 or board[nrr][nrc] == 1:
            continue
        locs.append((nlr, nlc, nrr, nrc))

    if lr == rr:
        for i in [-1, 1]:
            if board[lr + i][lc] == 0 and board[rr + i][rc] == 0:
                locs.append((lr, lc, lr + i, lc))
                locs.append((rr, rc, rr + i, rc))
    else:
        for i in [-1, 1]:
            if board[lr][lc + i] == 0 and board[rr][rc + i] == 0:
                locs.append((lr, lc + i, lr, lc))
                locs.append((rr, rc + i, rr, rc))
    return locs


def solution(board):
    n = len(board)
    board = [[1] * (n + 2)] + [[1] + b + [1] for b in board] + [[1] * (n + 2)]
    q = deque([[1, 1, 1, 2, 0]])
    visited = set()

    while q:
        lr, lc, rr, rc, cnt = q.popleft()
        if (lr, lc, rr, rc) in visited:
            continue
        if (lr, lc) == (n, n) or (rr, rc) == (n, n):
            return cnt
        visited.add((lr, lc, rr, rc))

        for loc in rotate(lr, lc, rr, rc, board):
            q.append([*loc, cnt + 1])

축을 왼쪽으로 하든 오른쪽으로 하든 회전이 가능하다면, 반대쪽 축에서도 회전이 가능한 것을 이용해

rotate 함수를 좀더 간단하게 만들 수 있었다.

1. 순열을 이용하여 완전탐색

from itertools import permutations
from bisect import bisect_right

def solution(n, weak, dist):
    l = len(weak)
    weak_line = weak + [w+n for w in weak]
    answer = []
    for friends in permutations(dist):
        for i in range(l):
            cnt = 0
            position = weak[i]
            for friend in friends:
                cnt += 1
                position += friend
                if position < weak_line[i+l-1]:
                    position = weak_line[bisect_right(weak_line,position)]
                else:
                    answer.append(cnt)
                    break
                    
    return min(answer) if answer else -1

예를들어 n=12, weak = [1,5,6,10], dist = [1,2,3,4]일때, weak_line = [1,5,6,10,13,17,18,22]를 만든다.

그 후 permutations(dist)로 순열을 만든다. 친구를 한명씩 투입해 각 취약점을 검사한다.

현재 투입된 친구로 모든 취약점을 검사하지 못했다면, 현재 위치에서 가장 가까운 다음 취약점에서 친구를 한명 더 투입한다.(bisect_right 사용)

모든 취약점을 확인했다면, 검사에 투입된 친구의 수를 answer에 추가한다.

2. dist 내림차순 정렬 후 모든 취약점 검사

def solution(n, weak, dist):
    l = len(weak)
    weak_line = weak + [w + n for w in weak]
    dist.sort(reverse=True)
    repaired_list = [()]
    cnt = 0

    for d in dist:
        repairs = []
        cnt += 1

        for i in range(l):
            start = weak[i]
            repairs.append(set([w % n for w in weak_line[i:i + l] if start + d >= w]))

        can = set()
        for r in repairs:
            for x in repaired_list:
                new = r | set(x)
                if len(new) == l:
                    return cnt
                can.add(tuple(new))
        repaired_list = can
    return -1

마찬가지로 weak_line을 만들고, 탐색거리가 긴 친구부터 모든 취약점을 검사하고 set에 저장한다. 시간효율성이 훨씬 좋음

def impossible(answer):
    for x,y,a in answer:
        if a == 0:
            if (x,y-1,0) in answer or (x-1,y,1) in answer or (x,y,1) in answer or y == 0:
                continue
            else:
                return True
        else:
            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
            else:
                return True
    return False

def solution(n, build_frame):
    answer = set()
    for x,y,a,b in build_frame:
        item = (x,y,a)
        if b:
            answer.add(item)
            if impossible(answer):
                answer.remove(item)
        else:
            answer.remove(item)
            if impossible(answer):
                answer.add(item)

    return sorted(map(list,answer),key=lambda x:(x[0],x[1],x[2]))

먼저 설치 또는 제거하고, 모든 구조물이 조건에 맞는지 검사한다.

만약 조건에 맞지 않다면 원상복구하고, 맞다면 그대로 둔다.

1. 정렬 후 이분탐색

ex) [probb ,proaa, prozz,procc]는 정렬 후 [proaa,probb,procc,prozz]가 된다.

probb,procc는 proaa와 prozz 사이에 있음에 착안해서, ?를 a와 z로 바꾼후 그 사이에 있는 단어의 개수를 센다.

from collections import defaultdict
import bisect

def find_result(word,left,right):
    left_idx = bisect.bisect_left(word,left)
    right_idx = bisect.bisect_right(word,right)
    return right_idx-left_idx

def solution(words, queries):
    answer = []
    word_list = defaultdict(list)
    reversed_word_list = defaultdict(list)
    for word in words:
        word_list[len(word)].append(word)
        reversed_word_list[len(word)].append(word[::-1])

    for key in word_list.keys():
        word_list[key].sort()
        reversed_word_list[key].sort()

    for query in queries:
        if query[0] != '?':
            answer.append(find_result(word_list[len(query)],query.replace('?','a'),query.replace('?','z')))
        else:
            query = query[::-1]
            answer.append(find_result(reversed_word_list[len(query)],query.replace('?','a'),query.replace('?','z')))
    return answer

2. trie 자료구조

trie와 거꾸로된 trie를 만든다. pro?? 형태라면 trie를 탐색하고, 만약 ??pro 라면 거꾸로된 트라이를 탐색한다.

????? 형태라면 길이에 맞는 단어의 개수를 출력한다.

import sys
sys.setrecursionlimit(10**6)

def make_trie(trie, words):
    for word in words:
        cur = trie
        l = len(word)
        for w in word:
            if w in cur:
                cur = cur[w]
                cur['!'].append(l)
            else:
                cur[w] = {}
                cur = cur[w]
                cur['!'] = [l]
    return trie


def find_result(trie, query, length):
    cnt = 0
    if query[0] == '?':
        return trie['!'].count(length)
    elif query[0] in trie:
        cnt += find_result(trie[query[0]], query[1:], length)
    return cnt


def solution(words, queries):
    answer = []
    rev_words = []
    count_len_words = []
    for word in words:
        rev_words.append(word[::-1])
        count_len_words.append(len(word))

    trie = make_trie({}, words)
    rev_trie = make_trie({}, rev_words)

    for query in queries:
        if query[0] == '?' and query[-1] == '?':
            answer.append(count_len_words.count(len(query)))
        elif query[-1] == '?':
            answer.append(find_result(trie, query, len(query)))
        elif query[0] == '?':
            answer.append(find_result(rev_trie, query[::-1], len(query)))

    return answer

def solution(key, lock):
    n,m = len(lock),len(key)
    new_map = [[0]*(2*(m-1)+n) for _ in range(2*(m-1)+n)]
    for i in range(n):
        for j in range(n):
            new_map[m-1+i][m-1+j] = lock[i][j]

    for _ in range(4):
        for i in range(m-1+n):
            for j in range(m-1+n):
                for k in range(m):
                    for l in range(m):
                        new_map[i+k][j+l] += key[k][l]
                flag = True
                for k in range(n):
                    for l in range(n):
                        if new_map[m-1+k][m-1+l] != 1:
                            flag = False
                            break
                if flag:
                    return True
                for k in range(m):
                    for l in range(m):
                        new_map[i+k][j+l] -= key[k][l]
        key = list(zip(*key[::-1]))
    return False

bfs로 푸는건 테스트케이스 7개가 시간초과가 났다..

결국 배열의 크기를 확장해서 lock을 배열의 중앙에 두고 key를 옮겨가며 맞춰보는 방법으로 풀었다.

def make_u_v(s):
    cnt1 = cnt2 = 0
    for i in s:
        if i == '(':
            cnt1 += 1
        else:
            cnt2 += 1
        if cnt1 == cnt2: break
    return s[:cnt1 + cnt2], s[cnt1 + cnt2:]

def is_right(s):
    cnt1 = cnt2 = 0
    for i in s:
        if i == '(':
            cnt1 += 1
        else:
            cnt2 += 1
        if cnt2 > cnt1: return False
    return True

def solution(p):
    if p == '':
        return p
    answer = ''
    u, v = make_u_v(p)
    if is_right(u):
        answer += u
        answer += solution(v)
    else:
        answer += '(' + solution(v) + ')' + ''.join(')' if x == '(' else '(' for x in u[1:-1])
    return answer

u를 뒤집은거와 u[::-1]이 같을거라고 생각해버리는 오류를 범했다..

문제에서 구현 하라는대로만 구현 하면 되는 문제였다.