Coding 공부

import sys
input = sys.stdin.readline
def permutation(ind,C,string_list,particle_order):
    global result
    if ind == C:
        if len(string_list)>0:
            result.add(''.join(string_list))
        else:
            result.add('EMPTY')
        return
    else:
        for i in range(1,N+1):
            command_order = particle_order[i]
            if command_order >= len(order_list[i]):
                continue
            else: 
                if not visited[i][command_order]:
                    order_num = order_list[i][command_order]
                    new_stringlist = string_list[:]
                    check_error = False
                    for order in card_command[order_num]:
                        if order[0] == 'ADD':
                            new_stringlist.append(order[1])
                        else:
                            remove_index = int(order[1])
                            if len(new_stringlist) > remove_index:
                                new_stringlist.pop(remove_index)
                            else:
                                check_error = True
                                break
                    if check_error:
                        result.add('ERROR')
                        continue
                    else:
                        visited[i][command_order] = True
                        particle_order[i] += 1
                        permutation(ind+1,C,new_stringlist,particle_order)
                        visited[i][command_order] = False
                        particle_order[i] -= 1


N,C = map(int,input().split())

order_list = [[] for _ in range(N+1)]

for ind in range(1,N+1):
    input_list = list(map(int,input().split()))
    order_list[ind] = input_list[1:]



card_command = [[] for _ in range(C+1)]


for ind in range(1,C+1):
    commands = list(input().rstrip().split(','))
    temp = []
    for command in commands:
        new_command = list(command.split(' '))
        temp.append(new_command)
    card_command[ind] = temp

result = set()
visited = [[False for _ in range(len(order_list[ind]))] for ind in range(N+1)]
particle_order = [0 for _ in range(N+1)]
permutation(0,C,[],particle_order)
result = list(result)
result.sort()
for i in range(len(result)):
    sys.stdout.write(result[i]+'\n')

이 문제는 구현을 하면 되는 문제였다. 여기서 주의해야할 점은, 사람1이 소지한 순서대로 카드를 낸다는것이다.

그러므로 먼저 사람1~ 사람N 까지의 순열을 구하는데 느낌은 

사람이 가지고 있는 카드의 수만큼 중복되게 수를 구해주고 순열을 구해주는 느낌으로 풀면된다.

만약 사람1이 카드를 4장 사람2가 카드를 2장 사람3가 카드를 3장 가지고 있다고 하면

[1,1,1,1,2,2,3,3,3] 이런식으로 리스트를 만들어놓고 순열을 구해도 된다.

나 같은 경우엔 각 사용자별로 card_command에 각 명령어를 파싱해서 저장을 시켜주었다.

그리고 particle_order를 이용해서, 각 사용자가 몇번재 카드를 썼는지 확인을했다.

그 뒤에는 재귀를 이용해서 백트래킹을 해주었다.

particle_order의 숫자가 사람1의 전체 명령어 수와 같게 되면, 선택을 못하게 if문으로 판별을 해주었다.

prarticle_order가 각 사람의 명령어 수보다 적다면, 인제 이 명령어가 가능한지 판단을 한다.

명령을 수행하다가 error가 발생시, result에 add를 추가해주고, 다음번으로 넘어가준다.

그리고 명령을 정확하게 수행하면, visited[사람의 인덱스][그 사람의 몇번째 카드]에 방문을 표시를 해준다.

그리고 particle_order의 값을 1 늘려주고, 재귀를 해준다.

이렇게 재귀를 하면서 전체 카드수를 다 쓰면, 모든 명령을 잘 수행한것이 된다. 그러면 그때의 결과를 result에 추가하는데,

아무것도 안남아있으면 EMPTY를 추가해주면 된다.

그리고 재귀를 하다가 복귀하게 되었을때에는 visited를 초기화해주고, particle_order도 1을 빼주면 된다.

이 문제는 백트래킹을 어떻게, 그리고 순열을 어떻게 응용해서 하는지에 대한 문제였다.

그래서 긴 문제 지문에 비해 많이 어려운 편은 아니였다.

from itertools import permutations
from collections import defaultdict

N = int(input())
alphabet = set()
total = defaultdict(int)
for _ in range(N):
    temp = list(input())
    alphabet.update(temp)
    temp.reverse()
    num = 1
    for k in temp:
        total[k] += num
        num*= 10

result = 0
alphabet = list(alphabet)

num_list = list(range(10-len(alphabet),10))
for new_nums in permutations(num_list):
    temp = 0
    ind = 0
    for key in total.keys():
        temp += total[key]*new_nums[ind]
        ind += 1
    result = max(result,temp)
        

print(result)

from itertools import permutations
from collections import defaultdict

N = int(input())
alphabet = set()
total = defaultdict(int)
for _ in range(N):
    temp = list(input())
    alphabet.update(temp)
    temp.reverse()
    num = 1
    for k in temp:
        total[k] += num
        num*= 10

result = 0
list_of_alpha =  list(total.values())
num = 9
list_of_alpha.sort(reverse=True)

for k in list_of_alpha:
    result = result + k*num
    num -= 1
print(result)

from itertools import permutations
from collections import deque
def outOfrange(x,y):
    if 0 > x or x >3 or y<0 or y>3:
        return True
    return False

def dfs(start,end,copy_board):
    dp = [[-1]*4 for _ in range(4)]
    dp[start[0]][start[1]] = 0
    stack = deque()
    stack.append((start[0],start[1]))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            repeat = 0
            while True:
                nx = x + dx[i]*repeat
                ny = y + dy[i]*repeat
                if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
                    break
                repeat += 1
            for re in (1,repeat):
                nx = x + dx[i] * re
                ny = y + dy[i] * re
                if outOfrange(nx,ny):
                    continue
                if dp[nx][ny] == -1:
                    dp[nx][ny] = dp[x][y] + 1
                    stack.append((nx,ny))
                    if dp[end[0]][end[1]] != -1:
                        return dp[end[0]][end[1]]
    return dp[end[0]][end[1]]



def find_command(x,y,find_card,copy_board):
    dis1 = dfs((x,y),find_card[0],copy_board)
    dis2 = dfs(find_card[0],find_card[1],copy_board)
    return dis1+dis2




def solution(board, r, c):
    answer = float('inf')
    card_list = [[] for _ in range(7)]
    card_numbers = set()
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_list[board[x][y]].append((x,y))
                card_numbers.add(board[x][y])

    card_cnt = len(card_numbers)
    for combi in permutations(card_numbers):
        predict_dict = {}
        for k in range(1<<card_cnt):
            distance = 0
            mouse_cursor_x = r
            mouse_cursor_y = c
            copy_board = [row[:] for row in board]
            temp = ''
            for ind,num in enumerate(combi):
                start = int(bool((k&1<<(ind))))
                end = (start+1)%2
                temp += str(start)
                find_card = [card_list[num][start],card_list[num][end]]
                if not predict_dict.get(temp):
                    distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
                    predict_dict[temp] = distance
                else:
                    distance = predict_dict[temp]
                mouse_cursor_x = card_list[num][end][0]
                mouse_cursor_y = card_list[num][end][1]
                copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
                copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
                if distance > answer:
                    break
            if answer > distance:
                answer = distance
    return answer+2*card_cnt


a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)

문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.

기본 풀이 자체는 다음과 같다.

카드번호 1,2,3이 있다고 하면

1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.

그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면

1A->1B

1B->1A는 다를 것이다.

이 모든 경우를 돌려서 결과를 얻는 것이다.

그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.

만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는

000

001

010

011

100

101

110

111

이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.

이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.

bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.

이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.

위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.

이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.

from collections import deque
import functools
def solution(board,r,c):
    card_dict = [[] for i in range(7)]
    card_tuple = set() 
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_dict[board[x][y]].append((x,y))
                card_tuple.add(board[x][y])
    card_tuple = tuple(card_tuple)

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    def outOfrange(x,y):
        if 0 > x or x >3 or y<0 or y>3:
            return True
        return False

    @functools.lru_cache(maxsize=None)
    def bfs(s,t,cards):
        if s == t:
            return 0
        stack = deque()
        stack.append((s[0],s[1],0))
        visited = set()
        while stack:
            x,y,cnt = stack.popleft()
            for i in range(4):
                repeat = 0
                while True:
                    nx = x + dx[i]*repeat
                    ny = y + dy[i]*repeat
                    if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
                        break
                    repeat += 1
                for re in [1,repeat]:
                    nx = x + dx[i]*re
                    ny = y + dy[i]*re
                    if outOfrange(nx,ny):
                        continue
                    if (nx,ny) == t:
                        return cnt + 1
                    if (nx,ny) not in visited:
                        visited.add((nx,ny))
                        stack.append((nx,ny,cnt+1))

    @functools.lru_cache(maxsize=None)
    def find_card_short_count(cur_position,cards):
        if len(cards) == 0:
            return 0
        min_distance = float('inf')
        for pick_card in cards:
            position1,position2 = card_dict[pick_card]
            remain_cards = tuple(card for card in cards if card != pick_card)
            direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
            direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
            min_distance = min(min_distance,direction1,direction2)
        return min_distance

    answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
    return answer


a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)

위의 풀이 대신 이 풀이는 프로그래머스의 다른사람풀이를 보고 공부하면서 쓴 풀이다.

자세한 설명은 http://www.teferi.net/ps/problems/programmers/72415 이 링크를 참조하길 바란다.

기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.

이 두 방식을 통해 시간이 획기적으로 줄어들었다.

이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.

bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.

여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.

cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.

이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.

위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.

한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.

현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다.
그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.

이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.

direction1 = bfs(cur\_position,position1,cards) + bfs(position1,position2,cards) + find\_card\_short\_count(position2,remain\_cards)

direction2 = bfs(cur\_position,position2,cards) + bfs(position2,position1,cards) + find\_card\_short\_count(position1,remain\_cards)

이 식들이 위에서 설명해준것을 구현한 것이다.

여기서 중요한 역할을 하는 것은 functools.lru_cache 라는 데코레이터이다.

이 데코레이터의 역할은 함수의 호출을 기억해주는 것이다. 똑같은 입력값이 들어온 함수들을 기억해서, 다음번에 호출이 되는 경우 함수를 한번더 실행하는 것이 아닌, 기억한 결과값을 그대로 주는 것이다.

그렇기 때문에 이 데코레이터를 썼을 때, 메모라이즈를 해준것이기 때문에, 재귀함수를 쓰면서도 시간을 줄일 수 있다.

다음과 같이 시간을 100ms 이하로 줄일 수 있다.

functools.lru_cache를 쓰지 않으면 시간의 압박이 크다.

위의 풀이가 아닌 DP를 활용한 풀이를 보고 싶은 분들은 https://www.youtube.com/watch?v=FX9n1PFv2K4 해당 유튜브를 참조하길 바랍니다.