본문 바로가기

알고리즘/스택, 큐16

[백준 -골드5] 6198번 옥상 정원 꾸미기(스택, 파이썬) https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net - 이번에도 신나게 풀다가 시간 초과 발생,,, 스택문제,, n이 최대 8만이기 때문에 이중 반복문 사용하면 연산량이 최대 16억,, 파이썬은 1초 2000만번,, 기억하자,,, - 우선 문제는 자신의 빌딩보다 낮은 빌딩은 내려다 볼 수있으니까 자신보다 낮은 빌딩을 세어야한다. - 그 다음 빌딩이 자신보다 높거나 같으면 안됨 - 우선 모든 빌딩을 확인해야 하기 때문에 for문으로 반복 수행.. 2022. 1. 23.
[백준 -골드5] 2493번 탑(스택, 파이썬) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 22/02/18 O +) 다시 풀어보니 17298번 오큰수랑 거의 유사한 문제 - 골드 문제인데 생각보다 쉽네하고 신나게 채점을 돌렸다.. 시간 초과... - 입력받은 탑을 for문으로 뒤에서부터 역순으로 순회한다. - 이 때 스택에 탑의 높이와 인덱스를 담아준다. - 스택이 비어있지 않고, 스택의 가장 끝에 있는 원소보다 다음에 들어온 탑이 더 크다면 - 스택에서 pop하고 reuslt[idx.. 2022. 1. 22.
[백준 -실버3] 1406번 에디터(스택, 파이썬) https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net - 스택 두개를 사용해서 구현함 - 그 전에 inser, remove 함수를 사용했는데 이 함수는 시간복잡도가 O(n)이라서 시간 초과 떠서 실패 import sys stack = list(sys.stdin.readline().strip()) temp = [] n = int(input()) for _ in range(n): order = sys.stdin.readline().strip() if or.. 2022. 1. 22.
[백준 -실버3] 10799번 쇠막대기(스택, 파이썬) https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net - 입력이 '('일때 - 스택에 넣어준다. - 입력이 '('이 아닐 때 -> 즉 ')' 일때 - 바로 직전 입력이 '(' 일때 --> 레이저임 - 스택에서 '(' 하나 빼줌 (레이저랑 짝꿍이기 때문) - 현재 스택의 길이를 ans에 더해준다.(잘린 막대기 갯수) - 바로 직전 입력이 ')' 일때 --> 막대기 끝 부분 - 스택에서 하나 빼주고 - ans +=1 data = list(input()) ans =.. 2022. 1. 22.

티스토리툴바