백준 - 18258- 큐2 [파이썬]

아아아아주 오랜만에 돌아온 개발일지..

학교 오전 부트캠프를 하는데 난이도가 한개도 안맞다. 진짜 뭔 소린지 하나도 못알아듣고 앉아있는즁..

인생은 박명수처럼

1. 문제

https://www.acmicpc.net/problem/18258

18258번: 큐 2

 

2. 이해 및 풀이

이전 자료구조 알고리즘 배울 때 뭣모르고 외웠던 것 덕분인가 (아니면 다 맞출 수 있는 쉬운 난이도였을 지도)

확실히 파이썬은 자바보다 구현이 쉽다. 자바였으면 배열로 구현할 때 사이즈 신경쓰느라 뇌가 조각났을 것이다.

알고리즘은 상당히 쉽게 구현해냈다.

(시간초과 이슈만 빼면..ㅎㅎ)

 

#첫번째 시도(시간초과)

N =int(input())
list=[]
for i in range(N):
    s = input().split()
    if s[0] == 'push':
        list.append(int(s[1]))
    elif s[0] == 'pop':
        if len(list) > 0:
            print(list[0])
            list.remove(list[0])
        elif len(list) ==0:
            print(-1)
    elif s[0] == 'size':
        print(len(list))
    elif s[0] == 'empty':
        if len(list)==0:
            print(1)
        else:
            print(0)
    elif s[0] == 'front':
        if len(list)==0:
            print(-1)
        else:
            print(list[0])
    elif s[0] == 'back':
        if len(list)==0:
            print(-1)
        else:
            print(list[len(list)-1])

파이썬에서 n개의 원소를 받고 싶다고 해서 조건을 걸 필요는 없다. 

그리고 상당히 가시적이다. 한번에 타입이 다른 자료형을 동시에 입력받고 싶으면 냅다 split()함수 쓰고 거기서 인덱스 처리해줘서 냅다 처리해주면 됨.

 

=> 시간 초과 오류가 났다.

파이썬 시간 초과 이슈는 요기서!!

 

 

#n번째 시도

import sys
from collections import deque

queue = deque()
N = int(sys.stdin.readline())

for _ in range(N) :
    i = sys.stdin.readline().split()

    if i[0] == 'push' :
        queue.append(int(i[1]))
    
    elif i[0] == 'pop' :
        if not queue :
            print (-1)
        else :
            print(queue[0])
            queue.popleft()
    
    elif i[0] == 'size' :
        print(len(queue))
    
    elif i[0] == 'empty' :
        if len(queue) == 0 :
            print(1)
        else :
            print(0)
    
    elif i[0] == 'front' :
        if not queue:
            print(-1)
        else :
            print(queue[0])
    
    elif i[0] == 'back' :
        if not queue :
            print(-1)
        else :
            print(queue[-1])

그래서

1. 입력할 때 sys 모듈에서 sys.stdin.readline()을 사용했다. (자바에서 stringbuffer를 사용하듯이! 파이썬은 컴파일러가 없어서 그렇다고 치는데 자바는 왜..?... 시간 초과 대비해서 스트링 버퍼를 사용하는 거지)

2. 일일히 다 코드를 읽기 때문에 리스트 말고 덱을 사용했다.(이게 효과가 있었으려나-> 효과가 있다고 한다.)

-> 리스트 사용하면 시간복잡도가 O(N)이 걸리지만 덱을 사용하면 시간복잡도가 O(1)이다.

덱을 사용하면 원소를 추가할 떄 맨 앞이나 맨 뒤에서 추가하니깐!!

그래서 맨앞이나 맨 뒤에서만 추가할 거면 덱을 사용하는 것을 추천!

 

 

마이도 틀려따..

 

남은 문제가 많댜!

부디.