-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
곳감 문제 시간복잡도에 관해서
22.11.21 00:35 작성 조회수 204
0
이 문제를 시간복잡도를 생각해서 다르게 풀었는데 그 판단이 맞는지 질문드립니다.
우선 저의 코드는 다음과 같습니다.
def solution():
# setting
sys.stdin = open('problem_8.txt', 'rt')
# inputs
n = int(input())
area: List[List[int]] = [list(map(int, input().split())) for _ in range(n)]
m = int(input())
rotations: List[List[int]] = [list(map(int, input().split())) for _ in range(m)]
# process
for rotation in rotations:
row_num: int = rotation[0]
direction: int = rotation[1]
step = rotation[2]
row = area[row_num - 1]
step = step if direction == 0 else -step
left = row[step:]
right = row[:step]
area[row_num - 1] = left + right
deviation: int = 0
summation: int = 0
for row_num in range(n):
for column_num in range(0 + deviation, n - deviation): # 04 13 22
summation += area[row_num][column_num]
if row_num < n // 2:
deviation += 1
else:
deviation -= 1
# output
print(summation)
TimeCounterRunner(solution).run()
저는 슬라이싱 기능을 이용해서 했는데 이렇게 한 이유는 리스트의 pop에 파라미터를 안넘기면 시간복잡도가 1이지만 제가 알기로 파라미터가 있는 경우 N이 되는 것으로 알고 있습니다.
거기에 추가로 pop은 루프를 돌면서 해야하기 때문에 N^2가 된다고 생각했습니다.
거기에 회전 숫자가 1인 경우에는 insert를 써야하는데 이것도 시간복잡도가 N으로 되는 것으로 알고 있었습니다.
그러면 어림잡아서 시간복잡도가 라인도 읽어야 하니까 N^3이 되는 것 같아서 저같은 경우 위에처럼 하면
슬라이싱에서 N이고 리스트를 더하는 것이 제가 알기론 시간복잡도가 N이긴 하지만 중첩으로 가지 않아서 N^2로 끝날 수 있을 것 같았는데 맞는 판단인지 알고 싶습니다.
답변을 작성해보세요.
0
김태원
지식공유자2022.11.24
안녕하세요^^
네. pop(0)을 하면 맨 앞에 자료가 제거되고 그 뒤에 것들이 하나씩 앞으로 당겨지므로 O(n)이 맞습니다.
N제한이 20정도라서 그냥 pop(0)을 사용했습니다. 시간복잡도를 생각하면서 더 좋은 코드를 짜려고 노력하는 모습이 좋아보입니다. 잘 하셨습니다.
답변 1