https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 이분탐색으로 푸는 방법도 있던데 그 방법은 풀이를 봐도 잘 이해가 되질 않아서 일단 스택으로 풀었다. 더 공부를 해야 할 것 같다. 스택에 0을 미리 넣어놓고, width를 계산할 때 스택에서 pop을 한 후에 i - st[-1] -1 로 계산하는 부분, 그리고 마지막에 인덱스 하나를 더 탐색하는 것이 많이 헷갈렸다.. import sys input = sys.stdi..
알고리즘💻/스택&큐&덱
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 문자열 입력에서 앞 뒤의 '[', ']' 와 숫자 중간의 ','를 제거한다. 2. 큐를 만들어 문자열을 넣는다. 3. flag를 만들어 R이 나오는 경우에는 -1을 곱해준다. 3. D가 나오고 flag가 1인 경우에는 앞에서 pop, flag가 -1인 경우에는 뒤에서 pop 해준다. 4. 마지막으로 flag가 -1이면 배열을 뒤집어준 후 조건에 맞춰 출력한다. import sys from collections import deque input = ..
https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net 큐를 이용해서 푸는 것이라는 건 알았는데, 하나하나 pop할 때마다 K를 더해서 체크하는 방식으로 풀어가지고 계속 시간초과가 났다. 다시보니 굳이 그렇게 하지 않고 한번에 K-1번 혹은 반대인 경우는 K번 이렇게 돌면서 pop을 해주면 되는 것이었다. 이 방식을 잘 기억해야겠다. import sys from collections import deque input = sys.stdin.readline N, K, M = map(int, input()..
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 스택을 이용해서 열린 괄호가 나타나면 스택에 추가하고, 닫힌 괄호가 나타나면 그 전의 괄호가 ( 인 경우에는 스택에서 하나를 pop 한 후에 스택의 길이 즉, 지금까지 있는 쇠막대기의 개수만큼 더해준다. 그 전의 괄호가 ( 가 아닌 경우에는 쇠막대기가 끝나는 것이므로 하나를 더해주고 스택에서 하나를 pop한다. import sys input = sys.stdin.readline s = list(input()..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 스택에 주어진 수의 앞에서부터 하나씩 넣으면서 기존에 있던 스택 top의 수가 새로 넣을 수보다 작은 경우에 더 크거나 같은 수가 나올때까지 그리고 스택이 비지 않을때까지 pop한다. 그렇게 했음에도 K번 pop되지 않은 경우에는 마지막에 출력할때 앞에서부터 N-K만큼의 길이만 출력하면 된다. 스택으로 구현하였는데, 기존에 푼 방법이 속도가 더 빨랐다. 이건 pop이 아니라 del을 사용했으며 마지막에 출력할 때 반복문을 사용하지 않고 join을 사용해서 그런 것 같다. 같..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 한 종류의 괄호만 있는 가장 기본적이고 간단한 괄호 해결 문제였다. 스택을 이용하여 구현하였다. import sys input = sys.stdin.readline T = int(input()) for _ in range(T): s = list(input().rstrip()) st = [] flag = True for i in s: if (i=='('): st.app..
https://www.acmicpc.net/problem/20923 20923번: 숫자 할리갈리 게임 첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연 www.acmicpc.net 처음에 문제가 이해가 안되서 한참 보다가 질문에서 두 사람이 낸 카드의 총합이 M이라는 걸 보고 아.. 그제야 이해했다. 이해한 후에는 그렇게 어렵지 않았는데, 처음에 바보같이 그라운드의 카드를 종을 친 사람의 덱으로 가져올 때 그라운드를 스택이라고 생각하고 풀어서 시간초과가 났다. 아니 사실 pypy로 돌렸을 땐 틀렸습니다..
https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net i번째로 카드를 내려 놓았을 때 내려 놓은 카드는 N-i 카드 이므로 원래 가지고 있던 카드의 인덱스 0~N을 덱에 넣어놓은 후, 인덱스를 하나씩 빼면서 정답 배열에 카드를 넣어주었다. 1인 경우에는 덱의 제일 앞의 인덱스에 카드를 넣어주면 되고 2인 경우에는 덱의 앞에서 두번째 인덱스에 넣어주어야 하므로 맨 앞의 인덱스는 따로 저장해놓고 두번째 인덱스를 pop한 후, 다시 첫번째 인덱스를 앞에 ..
https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우를 활용한다고 하여도.. 같은 길이의 문자열을 찾으려면 K개의 범위를 다 돌아봐야 하니까 시간초과가 날 것 같은데... 하는 생각에 오래 고민하다가 슬라이딩 윈도우의 장점을 사용하기 위한 방법을 생각해보았다. 바로 문자열의 길이를 인덱스로 하는 배열을 따로 만든 후에 같은 길이의 문자가 윈도우 안에 있는경우 그걸 인덱스로 한 값을 +1 해주는 방식이었다. 이렇게 ..
https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 아... 정말 어려웠다... 사실 어려운 것보다 내가 너무 어렵게 생각했던 것 같다. 처음에는 주어진 입력을 각각 원소로 해서 2차 배열을 만들어 저장하고 maxHeight를 찾고 그걸 기준으로 어떻게 잘 나누어서 해보자.. 라고 접근을 했는데 이 방식도 계속 파고 들어가면 풀 수 있을 것 같긴 하나.. 이렇게 푸는 게 과연 맞는 건가 하는 의문이 계속 들었다. 그리고 나서는 아,..
