암호생성기 (코딩테스트, SW Expert Academy)

[S/W 문제해결 기본] 7일차 - 암호생성기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD 

SW Expert Academy

코드

for test_case in range(1,11):
    # ///////////////////////////////////////////////////////////////////////////////////
    T = int(input())
    input_case = list(map(int, input().split()))
    cut = True
    while cut:
        for i in range(1,6):
            input_case[0] = max(0,input_case[0]-i)
            input_case.append(input_case[0])
            del input_case[0]
            if input_case[-1] == 0:
                cut = False
                break
    print(f"#{T} {' '.join(map(str, input_case))}")
            
    # ///////////////////////////////////////////////////////////////////////////////////

다른 문제와 다르게 테스트케이스 갯수를 명시하지 않아 자체적으로 10번 테스트를 진행하게 만들었다.

그냥 설명에 맞게 구현하는 단순한 문제였으나 테스트케이스가 조금 까다롭게 주어졌더라면 런타임 에러가 생길 듯

 

런타임 문제가 발생할 경우는 어떻게 해결해야 했을까 고민해볼 필요가 있다고 생각하였다.

 

자료구조 Queue를 사용하면 시간절약을 할 수 있다.

from collections import deque

queue = deque([1,2,3,4,5,6])

queue.append(7)
print(queue)

queue.appendleft(0)
print(queue)

queue.popleft()
print(queue)

queue.pop()
print(queue)

위 코드를 실행시켜본다면 간단히 이해할 수 있을 것이다.

 

하지만 특정 인덱스의 값을 찾을 때는 list보다 안좋기 때문에 상황에 맞게 사용하는 것이 중요하다.

길이가 1억인 리스트에서 9000만번 째 값을 찾기 위해 deque는 앞에서부터 순차적으로 접근을 할 것이다.(?)

즉 O(n)의 시간복잡도를 가진다고 한다.

 

 

인덱스로 리스트의 특정 값에 접근이 빈번한 경우: list

queue 기능이 빈번한 경우 : deque