programmers 행렬과 연산 python
2022년 12월 07일
#algorithm#python#programmers#queue
문제
풀이
표를 적당히 쪼개서 deque로 풀면 된다. 맨 왼쪽 열과 맨 오른쪽 열을 따로 저장해서 deque 2개를 만들고, 각 행의 인덱스를 저장한 deque를 만든다. ShiftRow 연산 시, q, leftq, rightq에 저장된 마지막 인덱스를 맨 앞으로 옮겨준다. Rotate 연산 시, leftq, rightq에서 값을 적절히 옮겨준다. 행의 길이가 2일 때는 rcq가 비어있기 때문에, 다르게 처리해야한다.
굳이 인덱스를 q에 저장해서 마지막에 옮길 필요는 없을 것 같다.

풀이 코드
from collections import deque
def solution(rc, operations):
answer = []
h = len(rc)
q = deque(i for i in range(h))
rcq = list(map(deque, rc))
qleft, qright = deque(), deque()
for i in range(h):
qleft.append(rcq[i].popleft())
qright.append(rcq[i].pop())
# query 연산
for oper in operations:
if oper[0] == "R": #Rotate
topIdx = q.popleft()
q.appendleft(topIdx)
bottomIdx = q.pop()
q.append(bottomIdx)
if len(rcq[0])==0: # 행의 길이가 2인 경우
qright.appendleft(qleft.popleft())
qleft.append(qright.pop())
else: # 행의 길이가 2가 아닌 경우
qright.appendleft(rcq[topIdx].pop())
qleft.append(rcq[bottomIdx].popleft())
rcq[bottomIdx].append(qright.pop())
rcq[topIdx].appendleft(qleft.popleft())
else: #ShiftRow
q.appendleft(q.pop())
qleft.appendleft(qleft.pop())
qright.appendleft(qright.pop())
# q에 저장된 index에 맞게 행 옮기기
topIdx = q.popleft()
temprcq = deque()
for i in range((h-topIdx)%h):
temprcq.appendleft(rcq.pop())
answer = list(temprcq)+list(rcq)
# qrc, qleft, qright 합치기
for i in range(h):
answer[i].appendleft(qleft.popleft())
answer[i].append(qright.popleft())
answer = list(map(list, answer))
return answer관련 글
백준 2927 남극탐험 Python
https://www.acmicpc.net/problem/2927 트리에서 노드 연결, 단일 업데이트, 구간합 쿼리를 수행하는 문제이다. 연결 여부는 union-find로 관리하고, 먼저 모든 연결 쿼리를 수행하여 HLD를 해준다. 이후, 순서대로 쿼리를 처리하면 된다. HLD 과...
BOJ 25910 게이트웨이 정하기 python
문제 게이트웨이 정하기 풀이 비트 연산의 특징을 알아야 풀 수 있는 문제였다. 1. 임의의 노드에서 시작한 결과를 dp에 저장한다. 2. 각 비트를 0인 그룹과, 1인 그룹으로 나눈다.(temp에 1일 경우만 저장) 3. 모든 노드에 대해 헤더와 XOR연산으로 비용을 구한다. 4....
BOJ 16118 달빛 여우 python
문제 달빛 여우 풀이 먼저 일반적인 다익스트라 알고리즘으로 여우의 이동시간을 구해서 dp에 저장해준다. 늑대의 경우에는 빨리 이동해서 도착했을 때, 느리게 이동해서 도착했을 때의 시간을 따로 저장해야 한다. 두 dp를 비교해서 ans를 구한다. > 추가시간이 없는 문제라서 파이썬으...