Medical and Programming Study

역시나 지난번에 푼 문제에 이어서 collections에 있는 deque를 이용하는 문제이다.

이번에는 appendleft()가 추가되었다!

문제의 큰 흐름은 앞서 스택에서 했던 부분과 유사하여 크게 설명하지 않고 늘 그렇듯이 주석으로 남겼다.

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

deque_list = deque()    # collections library 중 deque를 사용하면 queue를 시간 안에 구현 가능
N = int(input())    # command 개수 입력

for _ in range(N):    # command 개수만큼 반복
    command = input().split()    # 줄바꿈 문자를 제외하고 공백을 기준으로 분리
    if command[0] == 'push_front':    # 명령어가 push_front일 경우 deque_list의 가장 처음에 값을 추가
        deque_list.appendleft(int(command[1]))
    elif command[0] == 'push_back':    # 명령어가 push_back인 경우 deque_list의 가장 마지막에 값을 추가
        deque_list.append(int(command[1]))
    elif 'pop' in command[0]:    # 명령어가 pop_front 또는 pop_back인 경우
        if len(deque_list) == 0:    # deque_list가 비어있다면 -1을 출력
            print(-1)
        elif 'front' in command[0]:    # 명령어가 pop_front인 경우 가장 처음 값을 pop
            print(deque_list.popleft())
        else:    # 명령어가 pop_back인 경우 가장 마지막 값을 pop
            print(deque_list.pop())
    elif command[0] == 'size':    # 명령어가 size인 경우 deque_list의 size를 출력
        print(len(deque_list))
    elif command[0] == 'empty':    # 명령어가 empty인 경우
        print(1 if len(deque_list) == 0 else 0)    # deque_list가 빈 값이면 1을 출력하고 아니면 0을 출력
    else:    # 명령어가 front 또는 back일 경우
        if len(deque_list) == 0:    # deque_list가 비어있다면 -1을 출력
            print(-1)
        elif command[0] == 'front':    # 명령어가 front일 경우 가장 처음 값을 출력
            print(deque_list[0])
        else:    # 명령어가 back일 경우 가장 마지막 값을 출력
            print(deque_list[-1])

지난 문제에 이어서 collections에 존재하는 deque를 적극 이용하는 문제였다.

처음에는 deque를 쓰지 않고 해결해볼까 생각했지만, 시간 복잡도나 여러 면에서 deque가 효율적일 것 같아서 처음부터 설계를 deque를 고려하여 진행하였다.

deque에는 rotate라는 기능이 존재했고, 지난 번에도 다뤘던 popleft라는 기능도 존재하여 이를 적절하게 사용하면 될 것이라고 생각했다.

rotate는 deque를 회전시키는 기능으로, 음수를 입력하면 왼쪽으로 회전한다고 한다.

즉, deque([1, 2, 3, 4, 5])가 존재하면 rotate(-1)을 할 경우 deque([2, 3, 4, 5, 1])가 되고, rotate(1)을 할 경우 deque([5, 1, 2, 3, 4])가 된다.

이를 적용하여 코드를 완성하였다. (list comprehension도 적극 이용해보았다!)

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

N, K = map(int, input().split())    # 입력을 받을 때 공백을 기준으로 분리한 후 각각을 int 타입으로 변환
num_list = deque(x for x in range(1, N+1))    # number를 1부터 N까지 담고있는 list 생성
result = []    # 결과를 저장하는 list

for _ in range(N):    # N개의 원소를 모두 꺼내므로 N만큼 반복
    num_list.rotate(-K+1)    # deque에 존재하는 rotate 함수를 이용하여 list 회전 (K번째 index를 꺼내므로 회전은 K-1번만 진행)
    result.append(num_list.popleft())    # 가장 좌측에 있는 값을 pop

print('<' + str(result).strip('[]') + '>')    # 예제 출력에 맞게 결과 출력

앞서 다룬 스택과는 다르게 큐는 LILO ( Last In Last Out )이라는 특징을 가지고 있다.

Last In Last Out은 글자 그대로 나중에 들어온 값이 나중에 나간다는 것이다.

이번에 코드를 짜면서 역시 시간 초과 문제가 발생할 것을 염두하여 collections module에 존재하는 deque를 사용하였다.

처음에 한 번 deque를 써보지 않고 해보려 했지만, 먼저 들어온 값을 내보내는 코드에서 reversed(queue_list).pop()도 불가능했고, queue_list[::-1].pop()을 해도 기존의 list가 변하지 않기에 del이나 remove를 사용해야 해서 결국 시간 복잡도가 증가하기에 ( O(N)으로 증가한다. ) deque를 사용할 수 밖에 없었다.

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

queue_list = deque()    # collections library 중 deque를 사용하면 queue를 시간 안에 구현 가능
M = int(input())    # command 개수 입력

for _ in range(M):    # command 개수만큼 반복
    command = input().split()    # 줄바꿈 문자를 제외하고 공백을 기준으로 분리
    
    if command[0] == 'push':    # 명령어가 push인 경우
        queue_list.append(command[1])    # push 다음에 존재하는 숫자를 queue에 추가
    elif command[0] == 'pop':    # 명령어가 pop인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 deque에 존재하는 popleft()를 이용하여 가장 처음 들어온 값을 pop
            print(queue_list.popleft())
    elif command[0] == 'size':    # 명령어가 size인 경우 queue의 길이 출력
        print(len(queue_list))
    elif command[0] == 'empty':    # 명령어가 empty인 경우
        if len(queue_list) == 0:    # 빈 queue라면 1 출력
            print(1)
        else:    # 빈 queue가 아니라면 0 출력
            print(0)
    elif command[0] == 'front':    # 명령어가 front인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 가장 앞에 있는 값 출력
            print(queue_list[0])
    else:    # 명령어가 back인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 가장 마지막에 있는 값 출력
            print(queue_list[-1])

사실 처음에 코드를 이렇게 작성했었다.

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

sentence = list(input().strip())    # 줄바꿈 문자를 제외한 input을 한 글자마다 split
# print(sentence)    # DEBUGGING
cursor = len(sentence)    # 문장이 입력되면 cursor는 마지막에 위치
M = int(input())    # command 개수인 M을 입력

for _ in range(M):    # command 개수만큼 반복
    cmd = input().strip()    # cmd를 줄바꿈 문자를 제외하여 입력
    try:
        cmd, str = cmd.strip().split(' ')    # 명령어가 P일 경우 split하여 str을 저장
    except:
        pass    # 명령어가 P가 아닐 경우 특별한 event가 존재X

    # print('before: ', cursor)    # DEBUGGING
    
    if cmd == 'L' and cursor != 0:    # L 명령어 + cursor가 맨 앞이 아니라면 왼쪽으로 한 칸 이동
        cursor -= 1
    elif cmd == 'D' and cursor != len(sentence):    # D 명령어 + cursor가 맨 뒤가 아니라면 오른쪽으로 한 칸 이동
        cursor += 1
    elif cmd == 'B' and cursor != 0 and len(sentence) != 0:    # B 명령어 + cursor가 맨 앞이 아니라면 cursor 위치의 값 제거
        # print(sentence)    # DEBUGGING
        cursor -= 1
        del sentence[cursor]    # 제거 후 자동으로 값이 들어오므로 cursor 위치를 옮길 필요X
        
        # print(sentence, cursor)    # DEBUGGING
    elif cmd == 'P':    # P 명렁어가 입력된 경우 cursor 위치에 str을 저장 한 후, 오른쪽으로 한 칸 이동
        # if cursor == len(sentence) - 1:
        #     sentence.insert(cursor + 1, str)
        # else:
        sentence.insert(cursor, str)
        cursor += 1
    
    # print('after: ', cursor)    # DEBUGGING

print(''.join(sentence))    # list를 str로 합침

사실 이것도 print()를 이용한 디버깅을 통해서 에러 잡고 잡고 잡고 잡아서 만든 코드였는데

시간 초과라니 ... ^^;;

stdin을 썼는데도 나타난 시간 초과 관련한 오류는 아직 잡을 수 있는 방법을 몰라서 인터넷에 뒤적여 봤다.

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

stack_left = list(input().strip())    # 입력받은 문자를 줄바꿈 문자를 제외하여 한 글자씩 리스트에 저장
stack_right = list()    # 커서가 가장 마지막에 있으므로 커서의 우측은 아직까지 없으므로 빈 리스트 생성
M = int(input())    # command 개수 입력

for _ in range(M):    # command 개수만큼 반복
    command = input()    # command 입력
    if command[0] == 'L' and len(stack_left) != 0:    # command가 커서 좌측 한 칸 이동이고, 커서가 가장 좌측에 위치하지 않았다면
        stack_right.append(stack_left.pop())    # 커서를 좌측으로 한 칸 이동 (이 때, 커서가 좌측으로 이동하면서 지나간 값은 stack_right에 저장)
    elif command[0] == 'D' and len(stack_right) != 0:    # command가 커서 우측 한 칸 이동이고, 커서가 가장 우측에 위치하지 않았다면
        stack_left.append(stack_right.pop())    # 커서를 우측으로 한 칸 이동 (마찬가지로, 커서가 우측으로 이동하면서 지나간 값을 stack_left에 저장)
    elif command[0] == 'B' and len(stack_left) != 0:    # command가 커서 위치에 있는 값 제거이고, 커서가 가장 좌측에 위치하지 않았다면
        stack_left.pop()    # 해당 값 제거 (제거이므로 stack_right에 저장하지 않으며 stack_left에서 pop을 진행하였기에 커서가 자동으로 이동되는 효과)
    elif command[0] == 'P':    # command가 커서 위치에 값 추가라면
        stack_left.append(command[2])    # 해당 위치에 문자 추가 (stack_left에 추가했기 때문에 커서가 자동으로 이동되는 효과)

stack_left.extend(stack_right[::-1])    # stack_right에는 원래 문자의 순서가 아닌 거꾸로 저장되어 있으므로 돌려서 stack_left와 합)
print(''.join(stack_left))    # 문자열로 출력하기 위한 join 함수 사용

참고 : https://bladejun.tistory.com/12

관련한 코드와 같이 적혀있었는데, 아이디어 적인 면에서는 정말 훌륭한 풀이였으나

"왜?"는 해결하지 못했다.

https://wayhome25.github.io/python/2017/06/14/time-complexity/를 보면 이유를 참고할 수 있다!

pop은 시간 복잡도가 O(1)인 반면 del은 O(N)이였고 insert도 시간 복잡도가 O(N)이였다.

그렇기에 시간이 훨씬 소모되어 시간 초과가 일어났던 것..!!

꽤나 고생 좀 했다..

사실 이 문제에는 강력한 힌트가 있었다.

test 케이스 숫자에 해당하는 "모든 정수"가 결국에는 pop이 되어야 했던 것.

이 사실을 늦게 알아서... 많이 고생했다. ㅋㅋㅋ

이 점을 적용하면 코드는 아래와 같이 간단해진다!

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

last_in = 1
result = []
num_list = []

FLAG = True

T = int(input())    # 테스트 케이스 개수를 입력

for _ in range(T):    # 테스트 케이스 개수만큼 반복
    num = int(input())    # 정수 입력
    
    while last_in <= num:    # 마지막 입력된 정수가 num이 될 때까지 반복
        num_list.append(last_in)    # 정수를 stack에 저장
        # print("input >>>", last_in)
        result.append('+')    # stack에 쌓으므로 '+' 저장
        last_in += 1    # 입력할 정수가 다음 숫자로 넘어감
        # print(last_in)

    # while num in num_list:
    if num_list[-1] == num:    # 내려올 때는 무조건 한 칸씩 내려와야 함
        result.append('-')    # pop이므로 '-' 저장
        num_list.pop()    # 마지막 값 pop
        # print("out >>>", last_out)
    else:    # 여러 칸 내려온다면?
        FLAG = False    # 불가능!
        break    # for문 종료

if FLAG:
    for value in result:
        print(value)
else:
    print('NO')

Python이기에 간단하게 작성 해 볼 수 있는 코드를 쓴 것 같은 느낌이 든다..ㅎㅎ

처음 든 생각은 단순하게 괄호 '('와 ')'의 개수 비교였으나 순서도 모두 맞아야 한다는 느낌이 들었고 역시나 테스트 케이스에도 그 점이 인지되어 있었다.

예전에 programmers 카카오 lv1 문제인가에서 (아마 id 생성 관련해서 7단계로 나누어서 해결하는 문제였던 것 같다.) best 풀이 중에 while로 탐색 및 반복하는 풀이가 기억에 강하게 남았었는데, 문득 이 방법이 생각나서 적용해보았다.

이를 활용하면 나중에 올바른 괄호 쌍의 개수도 쉽게 구할 수 있다!

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

num = int(input())    # 테스트 케이스 개수를 입력
for _ in range(num):    # 테스트 케이스 개수만큼 반복
    sentence = input().strip()    # 괄호 문자열을 입력받고 '\n'문자 제거
    while '()' in sentence:    # 괄호쌍이 문자에 존재하면 계속 반복
        sentence = sentence.replace('()', '')    # 괄호쌍을 없애버림
    print('YES') if sentence == '' else print('NO')    # 괄호쌍이 순서에 맞게 존재했다면 모두 제거되고 그렇지 않다면 남음

Python의 list to string과 string to list에 익숙해지는 시간입니다.

기본적으로, Python에서는 split()함수를 통해서 string을 list에 담고, join()함수를 통해서 list를 하나의 string으로 합칩니다.

10828번 문제에서도 split을 사용했지만, split을 사용하지 않는 풀이가 많이 존재했는데 이 문제는 split과 join을 알면 훨씬 쉽게 풀 수 있는 문제입니다.

10828번 문제에서 시간 초과 문제가 발생하여 이번에도 발생할 것 같아 (구조가 비슷해서) 똑같이 sys 모듈을 불러와서 input을 재정의 하였습니다.

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

num = int(input())    # 테스트 케이스 개수를 입력
sentence = []    # 테스트 케이스를 저장받을 리스트 선언

for _ in range(num):    # 테스트 케이스 개수만큼 반복
    sentence = input().strip().split(' ')    # 테스트 케이스를 입력받고, 공백으로 분리
    for idx, value in enumerate(sentence):    # enumerate로 index와 value를 받아오면서
        sentence[idx] = value[::-1]    # value의 값을 뒤집어서 저장
    print(' '.join(sentence))    # 출력물은 공백을 기준으로 리스트를 합침

자료구조의 첫 번째인 스택을 구현하는 문제입니다.

스택은 Last In First Out으로, 나중에 들어오는 값이 먼저 출력된다는 뜻입니다. (줄여서 LIFO - 후입 선출 이라고도 합니다.)

문제를 그대로 따라가면 풀리는데 문제는 input()을 그대로 사용하면 시간 초과 문제가 발생합니다.

따라서, 조금 더 시간을 적게 소모하는 sys.stdin.readline을 사용하여 input을 재정의하면 시간 초과가 발생하지 않습니다.

import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

rep_num = int(input())    # 명령어 개수 입력
stack = []    # stack list

for _ in range(rep_num):    # 명령어 개수만큼 반복
    command = input()    # 명령어 한 줄 입력
    if "push" in command:    # 명령어가 push라면
        stack.append(int(command.split(" ")[1]))    # 공백을 기준으로 split 한 후, 1번 인덱스 값을 int로 변환하여 stack에 저장
    elif "pop" in command:    # 명령어가 pop라면
        if len(stack) == 0:    # 빈 stack이라면 -1 출력
            print(f"{-1}")
        else:    # 빈 stack이 아니라면 stack의 마지막 값 추출 및 출력
            print(stack.pop())
    elif "size" in command:    # 명령어가 size라면
        print(len(stack))    # stack의 크기 출력
    elif "empty" in command:    # 명령어가 empty라면
        if len(stack) == 0:    # 빈 stack이라면 1 출력
            print(f"{1}")
        else:    # 빈 stack이 아니라면 0 출력
            print(f"{0}")
    else:    # 명령어가 top라면
        if len(stack) == 0:    # 빈 stack이라면 -1 출력
            print(f"{-1}")
        else:    # 빈 stack이 아니라면 stack의 마지막 값 출력
            print(stack[-1])