본문 바로가기
728x90

자료구조22

[python] 백준 1826 연료 채우기 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 해결 처음에 재귀(recursion)를 이용해 풀려고 했다. 하지만 모든 경우의 수를 다 찾아보는 것은 불필요하고 recursionError가 뜨게 되었다. 힙을 이용해 문제를 풀 수 있다고 하는데 어떻게 풀어야할지 몰랐다. 다른 분들의 풀이를 참고하여 풀 수 있게 되었다. 바로 계속 지나간다고 가정하고 만약 기름이 부족하게 되면 기름을 채우고 나서~채우.. 2023. 4. 4.
[python] 백준 10775 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제 해결 i번째 숫자 p인 비행기를 주차할 때 p부터 1까지 주차 가능한 지역을 살펴봐서 가능하면 주차하고 모두 안되면 지금까지 주차한 비행기 대수를 구하면 된다. 하지만 비행기 대수와 게이트 숫자가 매우 클 수 있다. $10^{5}$ 이므로 두번 풀로 for문을 돌릴 수 없다는 것이다. 그러면 한번에 찾을 수 있는 방법을 찾아야한다. 이 때 이용되는 것이 Un.. 2023. 3. 17.
[python] 백준 2812 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 stack을 쌓아서 앞쪽에 큰수들로 이루어지도록 하는 것이 포인트 특이 케이스로 같은 숫자가 계속 나와서(예: 33333) 제거하기 애매한 상황이 나올 수 있음 따라서 stack이 많이 쌓일 수도 있으므로 앞에서부터 n-k개를 출력해야한다. CODE import sys input = sys.stdin.readline from collections import deque n, k = map(int, input().split()) que = deque([int(c) .. 2023. 3. 16.
[python] 백준 5397 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제해결 포인터를 기준으로 왼쪽 오른쪽에 스택을 두고 이동시키는 것을 생각했다. 왼쪽으로 움직이면 왼쪽 스택의 마지막 것을 오른쪽에 넣는다. 오른쪽으로 움직이면 오른쪽 스택 마지막 것을 왼쪽에 넣는다. 지우면 왼쪽 스택의 마지막것을 지우면 된다. 사실 시간이 적기 때문에 시간초과가 나서 고민했다. 마지막 완성된 두 스택을 연결해서 정답을 추출할 때 ''.join(iterable)로 했다. .. 2023. 3. 15.
728x90