덱5 [Kotlin] 백준 28078 : 중력 큐 문제 링크 : https://www.acmicpc.net/problem/28078문제 해설조금 변형된 큐 문제. 큐의 방향에 따라 내용을 처리해야 한다. 큐의 방향에 따라서 공이 앞부분으로 나올 수도 있고 뒤부분으로 나올 수도 있기 때문에 덱(Deque)을 사용한다. 편의 상 본문에서는 큐라고 언급한다. 큐의 방향에 대해 생각해보자. 큐의 방향은 90도씩 회전하는 4가지 방향만 존재하기 때문에 큐의 앞부분이 바라보는 방향을 오른쪽부터 시계방향으로 0, 1, 2, 3으로 지정할 수 있다.var direction = 0 // 0: right, 1: down, 2: left, 3: up각 쿼리에 대한 동작을 구현하기 전에 큐에서 공의 개수와 가림막의 개수를 구하는 방법을 생각해보자. 단순히 count() 메소.. 2024. 5. 17. [Kotlin] 백준 12789 : 도키도키 간식드리미 문제 링크 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 해설 스택을 사용하여 문제를 해결할 수 있다. 간식을 받기 위해서는 1번부터 순서대로 간식 받는곳으로 이동해야 한다. 그런데 줄이 뒤죽박죽 섞여있어서 왼쪽에 있는 1열의 공간을 이용하여 줄을 순서대로 간식을 받을 수 있게 해야한다. 이 1열의 공간을 일종의 스택으로 취급하여 문제를 해결하면 된다. 입력받은 학생 번호 순서대로 아래와 같이 간식 받기를 시도한다. 만약 현재 간식을 받아야 할 번호와 줄 맨 앞의 학생 번호가 일치하지 않는다면 대기 공.. 2023. 8. 9. [Kotlin] 백준 1021 : 회전하는 큐 문제 링크 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 해설 덱의 양방향 삽입, 삭제 연산을 통해 회전하는 큐를 구현할 수 있다. 수를 뽑아내기 위한 인덱스는 항상 가장 앞으로 고정되어 있으므로 주어진 입력의 순서대로 수를 뽑으려면 원소들을 좌우로 이동시키면서 주어진 수가 가장 앞으로 오게 만들어야 한다. 예제 2의 경우는 아래 그림과 같은 과정을 거치게 된다. 이 때 뽑아낼 수가 큐의 가장 앞에 오려면 왼쪽 또는 오른쪽 중에 더 가까운 쪽으로 \(x\)번 수를 이동시켜야 한다. 이 방향은 큐에서.. 2023. 7. 11. [Kotlin] 백준 23294 : 웹 브라우저 1 문제 링크 23294번: 웹 브라우저 1 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000) 둘째 줄에는 N개의 정수 CAPi www.acmicpc.net 문제 해설 [Kotlin] 백준 23300 : 웹 브라우저 2와 유사한 문제지만 캐시 용량의 제한이 추가되어 있는 문제이다. 캐시 용량을 다루는 것을 제외하면 기본적인 풀이는 동일하다. 각 페이지의 캐시 공간은 배열에 저장하여 사용했다. 뒤로 가기 공간과 앞으로 가기 공간을 각각 덱으로 구현하고 B 또는 F를 수행할 때마다 저장된 페이지와 현재 페이지를 옮기면 된다. 이 두 경우에는 이미 캐시 공간에 저장된 .. 2023. 4. 19. [Kotlin] 백준 23300 : 웹 브라우저 2 문제 링크 23300번: 웹 브라우저 2 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000) 둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음 www.acmicpc.net 문제 해설 뒤로가기 목록을 저장할 스택과 앞으로가기 목록을 저장할 큐를 각각 만들면 손쉽게 해결할 수 있다. 본 코드에서는 덱을 사용했지만 크게 상관은 없다고 생각한다. 압축 기능은 뒤로가기 목록의 2번째 페이지부터 마지막 페이지까지 이동하면서 이전 페이지와 같으면 제거하는 식으로 구현했다. Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedRe.. 2023. 1. 26. 이전 1 다음
