[스터디 후기] 6주차. 백준 문제 및 조별 과제 토의

1. 스터디 범위

1) 범위

별찍기, 덱 큐

 

 

2. 스터디 내용

1) 2448. 별 찍기 11

- 재귀를 이용하여 해결한다.

N = int(input())

def getPattern(n):
  
  if n == 3:
    return ['  *  ', ' * * ', '*****']

  pattern = getPattern(n//2)
  patterns = []
  
  patterns.extend([" "*(n//2) + i + " "*(n//2) for i in pattern])
  patterns.extend([i + " " + i for i in pattern])

  return patterns

for i in getPattern(N):
  print(i)

 

2) 2522. 별 찍기 - 12

- 예제와 동일하게 별 찍기

n = int(input())

for i in range(1, n+1): 
    print(' '*(n-i) + '*'*i)
    
for i in range(1, n):
    print(' '*(i) + '*'*(n-i))

 

3) 2556. 별 찍기 - 14

- 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요.- 정사각형 출력(non-sense)

n = int(input())

for i in range(n):
    print("*" * n)

 

4) 1996. 프린터 큐

- 중요도 리스트에 대한 인덱스를 따로 만들고 궁금한 문서 위치에 1 값을 부여하여 찾는다.

t = int(input())
for i in range(t):
    cnt=0
    
    n,m = map(int, input().split())         #문서의 개수,문서 위치
    il =list(map(int, input().split()))     #중요도 리스트
    
    m_il = [0 for i in range(n)]         #중요도 위치 인덱스 
    m_il[m]=1                            #중요도가 궁금한 문서(m번째 문서)의 인덱스를 임의로 1로 표시
    
    while True:                          #큐의 첫번째 값이 내가 찾는 값(m)일때까지 반복
        if il[0]==max(il):               #중요도가 제일 큰 값이면 cnt에 1을 더해준다
            cnt+=1
            
            if m_il[0]!= 1:              #원하는 문서가 아니라면
                del il[0]                #중요도의 첫번째 값 삭제
                del m_il[0]              #인덱스의 첫번째 값 삭제
                
            else:                        #원하는 문서라면
                print(cnt)               #cnt를 출력하고 반복문 종료
                break
                      
        else:                            #아니라면 중요도(il)의 첫번째값을 맨뒤에 넣어주고, 삭제
            il.append(il.pop(0))         
            m_il.append(m_il.pop(0))

 

5) 10866. 덱

 @ deque(덱)
- stack 이나 queue 처럼 한 방향에서 삽입과 삭제가 일어나는게 아닌 '양방향' 에서 삽입과 삭제가 일어나는 자료구조
- list와 유사하나 '시간복잡도' 에 차이가 있다.(list는 배열의 형태이기 때문에 삽입, 삭제가 일어나면 상당히 비효율적)
- list 의 삭제연산을 약 O(n) 의 시간이 걸리고 deque 의 삭제연산은 약 O(1) 

from collections import deque
dq = deque([1,2,3,4])
dq.append('a')
print(dq)

-----------------------------
deque([1, 2, 3, 4, 'a'])

from collections import deque
dq = deque([1,2,3,4])
dq.appendleft('a')
print(dq)

-------------------------------
deque(['a', 1, 2, 3, 4])

 

풀이

from collections import deque
import sys

d = deque()              # 덱 선언
n = int(input())

for i in range(n):                            #n만큼 커맨드 담기
    com = sys.stdin.readline().split()

    if com[0] == "push_front":
        d.appendleft(com[1])           # 덱 왼쪽에 넣어줌
        
    elif com[0] == "push_back":
        d.append(com[1])               # 덱 오른쪽에 넣어줌
        
    elif com[0] == "pop_front":        # 덱에 정수 없는 경우 -1 출력
        if len(d) == 0:             
            print("-1")  
            
        else:                          # 덱의 가장 앞에 있는 수를 빼고, 출력 
            print(d.popleft())
            
    elif com[0] == "pop_back":         # 덱에 정수 없는 경우 -1 출력
        if len(d) == 0:             
            print("-1")  
            
        else:
            print(d.pop())             # 덱의 가장 뒤에 있는 수를 빼고, 출력 
            
    elif com[0] == "size":
        print(len(d))
        
    elif com[0] == "empty":             # 덱이 비어있으면 1, 아니면 0
        if len(d) == 0:             
            print("1")
            
        else:
            print("0")
            
    elif com[0] == "front":             # 덱에 정수 없는 경우 -1 출력
        if len(d) == 0:             
            print("-1")
            
        else:                           # 덱 가장 앞 출력
            print(d[0])
            
    elif com[0] == "back":
        if len(d) == 0:                
            print("-1")
            
        else:
            print(d[-1])               # 덱 가장 뒤 출력