본문 바로가기

알고리즘/스택, 큐16

[백준-실버4] 1021번 회전하는 큐(큐, deque, 파이썬) https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net - idx_list에 뽑아야할 수의 인덱스를 저장했다.(이 때 문제 인덱스는 1부터 n 임을 주의) - queue는 인덱스를 나타낸다. 따라서 1-n까지의 값을 넣어주었다. - idx_list를 순회하면서 어느 방향으로 회전하는게 최소인지 파악한다. - left는 큐에서 뽑아야하는 idx의 인덱스를 나타낸다. - right는 left(현재 위치)를 제외하고 오른쪽으로 어느 정도 길이인지 확인한.. 2022. 2. 18.
[백준-실버3] 1874번 스택 수열(스택, 파이썬) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net - 1-N까지 반복문을 돌면서 수행 - temp에 차례대로 push해주고 ans에 '+'를 담아주었다. - 그리고 i와 answer의 인덱스 0부터 비교를 해주었다. 이 때 temp에 원소가 있어야함. - 일치하면 idx를 1 증가시켜 다음 정답 리스트와 비교하도록하고, result에 temp에 있는 원소를 옮긴다... 2022. 2. 17.
[백준 -실버4] 18258번 큐 2(큐, 파이썬) https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net - 시간복잡도를 고려하여 리스트에서 맨 앞 원소를 뽑는 pop(0)을 사용 안함 -> 이건 복잡도 O(n) - 따라서 deque를 사용해서 popleft()이용함 -> 이건 복잡도 O(1) - 그런데도 시간초과가 떴다,,, 입력 받을 때 sys.stdin.readline 이용해야함 from collections import deque import sys n = int(sy.. 2022. 2. 4.
[백준 -골드4] 17298번 오큰수(스택, 파이썬) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 22/02/18 O - n이 최대 100만이기 때문에 시간복잡도가 n^2이면 시간초과가 발생한다. - 따라서 최대한 n에 가깝게 코드를 구현해야한다. - for문으로 입력받은 데이터의 모든 원소를 탐색한다. - 이때 stack에 원소가 있고, 스택의 마지막 원소보다 해당 데이터의 크기가 클때 while문 수행 - 스택의 원소를 pop하고, result 배열에 값을 넣어준다. - 매번 스택에 값을 차례대로 추.. 2022. 2. 3.

티스토리툴바