https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 원형 큐를 양방향 큐인 deque 즉, double-ended-queue로 생각하여 풀었다. 양수인 경우에는 popleft()를 하고 그걸 다시 append() 하고 음수인 경우에는 pop()을 하고 그걸 다시 appendleft() 하였다. import sys from collections import deque N = int(sys.stdin.readline()) num = list(map(int, sys.stdin.rea..
알고리즘💻/스택&큐&덱
www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제풀이: 스택을 이용한 괄호체크 문제와 똑같이 푼다. "{"가 나올 경우에는 스택에 추가하고, "}"가 나올 경우에는 스택에서 하나를 pop 하는데, 이때 스택이 비어있는 경우 "}"->"{"로 바꾸는 연산을 수행해야 하므로 ans++ 후 스택에 "{"를 추가한다. 주어진 입력을 모두 체크한 후 스택이 비어있지 않은 경우 "{"를 "}"로 바꾸는 연산이 필요한데 한 번 연산하면 스택에서 두개 씩 pop한다..
www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 아이디어: 주어진 수열을 돌면서 F(Ai) 배열을 채운다. 무식하게 풀어보자면.. 그냥 배열을 돌면서 다 비교할 수 있겠지만 그러면 O(n^2)이므로 시간초과가 날것이다.. 구글링을 해보니, 스택으로 조금만 생각하면 쉽게 풀 수 있었다. 일단 뒤에서부터 배열을 읽어나가는 게 핵심이다! 그리고 F[i]의 값을 스택에 push하되, 만약 현재 읽는 배열의 F[i]값이 스택의 top보다 작다면 NGF(i)는 스택의 top이 된다..
www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 아이디어: 스택을 이용하면 될 것 같은데. 앞서 풀었던 괄호 문제랑 비슷하게. 스택을 만들고 왼쪽 괄호인 경우에는 push, 오른쪽 괄호인 경우에는 스택의 하나를 pop한다. 이때 pop한 값이 왼쪽 괄호이고 짝이 맞으면 조건에 맞게 숫자를 push해야 되는데, 이때 스택에 남아 있는 값이 뭔지 peek해보고(값이 남아있지 않을 경우 예외처리 해줘야 함), 숫자가 있으면 그것도 pop해서 더한 후 숫자를 pu..
www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 아이디어: #덱 뽑고자 하는 원소가 맨 첫번째 원소가 될때까지 왼쪽이나, 오른쪽으로 이동시키는 최소 횟수를 구하면 된다. 근데 그 최소횟수는 어떻게 구하지? 덱에서의 해당 원소의 위치를 알아야 할 것 같은데.. -> index(x) index(x) popleft() 반대면 pop() 을 한다. 이 값이 뽑고자 하는 원소와 일치하지 않으면 각각 반대편에 다시 추가하고, ans+=1한다. 같은 경우 poplef..
www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 아이디어: #우선순위큐 파이썬에서 우선순의 큐를 구현하는 방법 # 우선순위가 높은 큐가 먼저 나온다. import queue q = queue.PriorityQueue() q.put((10, "a")) q.put((5, "b")) q.put((15, "c")) q.qsize() # 3 q.get() # (5, 'b') heapq로 구현하는 방법도 있다. import heapq h = [] heapq.heappush..
www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 아이디어: #큐 큐를 이용해서 n까지의 수를 모두 넣은 후 앞에서부터 차례대로 제거하면서 제거한 수를 다시 큐에 집어넣는 형태로 반복한다. 파이썬에서 queue를 구현하는 방법 1. 리스트 - 비효율적임 2. Queue # 내장 함수 queue를 사용하여 구현 import queue q = queue.Queue() q.put("a") q.put("b") q.put("c") q.qsize() # 3 q.get() # 'a' q.qsize() # 2 근데 queue를 이용해서 문제를 풀었더니 시간초과가 나..
www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 아이디어: #스택 이것도 스택의 대표문제인 괄호문제. 오른쪽 괄호인 경우에는 push 하고, 왼쪽 괄호인 경우에는 pop해서 짝이 맞는 지 확인한다. 이때 스택에 남아 있는 괄호가 없다면 오른쪽 괄호가 더 많은 거니까 False이고, 문자열을 모두 돈 후에 스택에 괄호가 남아있다면 왼쪽 괄호가 더 많은 거니까 False이다. import sys while (True): st = sys.stdin...
www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 아이디어: #스택 스택의 대표 유형이라고 볼 수 있다. 주어진 문자열을 돌면서 피연산자일 경우에는 push, 연산자일 경우에는 스택에서 두 개를 pop해서 연산을 한 후 값을 다시 push한다. 문자열을 모두 돌면 스택에 딱 한 값이 남고 그 값을 pop하면 답을 구할 수 있다. 파이썬에서는 스택 자료구조를 따로 제공하지 않기 때문에 list를 사용하여 구현한다. push는 append로, pop은 ..
