05. 기본 자료구조 - 핵심 유형 문제 풀이-2 -자료구조, 스택, 데크

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

17298번: 오큰수

• 자료구조, 스택

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))

result = []

for i in range(n): # 9548
    lstack, rstack = [], []

    for j in range(i+1, n): #548
        if data[i] < data[j]:
            lstack.append(data[j])
        elif data[i] > data[j]:
            rstack.append(data[i])
    if len(lstack) != 0:
        result.append(lstack[0])
    if len(rstack) != 0:
        if max(rstack) == max(data):
            result.append(-1)
        
result.append(-1)        
print(result)

 

• 정답은 야매로 했지만,  시간초과로 실패 함. 

n = int(input())
arr = list(map(int, input().split()))
stack = [] # 스택 초기화
NGE = [-1] * n

for i in range(n):
    x = arr[i]
    if len(stack) == 0 or stack[-1][0] >= x:
        stack.append((x, i)) # (수, 인덱스) 형태로 삽입
    else:
        while len(stack) > 0: # 역방향으로 하나씩 추출
            previous, index = stack.pop()
            if previous >= x: # 크기나 같은 이전 원소를 만났다면 다시 삽입
                stack.append((previous, index))
                break
            else:
                NGE[index] = x # 오큰수 기록
        stack.append((x, i)) # (수, 인덱스) 형태로 삽입
for x in NGE:
    print(x, end =' ')

• 이 문제는 다시 풀어봐야할듯

n = 11
data = [3,2,1,10,9,5,4,8,15,11,13]
LB = [-1] * n

stack = []
for i in range(n):
    x = data[i]
    if len(stack)==0 or stack[-1][0] >= x: # 최상단 원소가 새로운 값보다 같거나 클 때 스택 삽입 
        stack.append((x,i))
    else:
        while len(stack) > 0:
            value, idx = stack.pop()
            if value >= x:
                stack.append((value, idx))
                break
            else:
                LB[idx] = x
        stack.append((x, i))
        
for i in LB:
    print(i, end=' ')

 

• for i in LB:
      print(i, end=' ')
  • " print(i, end=' ')"를 통해 한줄에 한번에 출력
• 스택으로 문제를 접근함.
• "data = [3,2,1,10,9,5,4,8,15,11,13]" 아래 값이 입력으로 들어 왔다고 가정했을 때 새로운 큰 수가 나오기 전까지는 전부다 "stack"에 어팬드 해줌, 이후 큰 수를 만났을 때 추가되었던 스택 을 뒤에서 부터 하나씩 꺼내며 확인을 함
  • "value, idx = stack.pop()" 확인을 시작하는데
    • 현재 꺼낸 값이 최상단으로 들어온 "x" 보다 크다면 다시 꺼낸 값을 그대로 돌려놓고 반복문 종료 
      •  if value >= x: stack.append((value, idx))
                    break
    • 그렇지 않으면 다시 오큰수로 최상단 값을 기존 추가하였던 스택의 개별 인덱스로 저장함 LB[idx] = x
  • 이후 새로 들어온 x 값을 스택에 새로 추가함

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

1021번: 회전하는 큐

• 자료구조, 덱

 

# import sys
# input = sys.stdin.readline

from collections import deque

n, m = map(int, input().split()) # 원소 개수, 뽑아내는 횟수
data = list(map(int, input().split())) # 뽑아낼 원소 목록

d = deque([i for i in range(1, n+1)]) #덱

cnt = 0
for i in data:
    index = d.index(i)
    if index <= len(d) // 2:
        for i in range(index):
            d.rotate(-1)
            cnt +=1
    else:
        for i in range(len(d) - index):
            d.rotate(1)
            cnt +=1
    d.popleft()
                
print(cnt)

1. 문제의 핵심은 입력 받는 값 ex) 2, 9, 5 등 값들이 n까지의 원소들중 중간 앞에 위치하면 왼쪽 회전, 중간 뒤에 위치하면 우측 회전이다.
2. 원소 개수 "n"까지 데크를 만들어 둠. 이후 각각의 개별 데이터들"i"을 입력으로 받아옴
3. 현재 개별 데이터들이 생성해둔 데크 안에 어디에 위치하는지 알기 위해 인덱스로 위치를 개별 매칭함 "index = d.index(i)"
4. 앞서 1번에서 말한 것 처럼 중간 앞에 위치하면 "if index <= len(d)//2:" 
   1. 현재 "index" 값만큼 좌측회전 "d.rotate(-1)" 후 카운트
5. 위와 같이 만약 왼쪽에 위치한다면 "if index > len(d)//2" or "else"
   1. 현재 전체 데크의 길이 "lend(d) - index" 에서 인덱스를 뺀 횟수만큼 우측회전 " d.rotate(1) "
6. 끝으로 회전이 끝난 뒤 각 개별데이터들은 리스트 맨앞에 위치하므로 뽑기"d.popleft()"

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

11866번: 요세푸스 문제 0

• 자료구조, 덱

• 

from collections import deque
# n, m = 7,3
n, m = map(int, input().split())
d = deque([i for i in range(1, n+1)])
result = []

while len(d) > 0:
    d.rotate(-(m-1))
    result.append(d[0])
    d.popleft()

temp = str(result)[1:-1]
print(f"<{temp}>")

• 처음부터 좌측[0]을 기준으로 입력 받은 k-2 씩 좌측으로 회전해주면 끝인문제