스택10 [Kotlin] 백준 12789 : 도키도키 간식드리미 문제 링크 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 해설 스택을 사용하여 문제를 해결할 수 있다. 간식을 받기 위해서는 1번부터 순서대로 간식 받는곳으로 이동해야 한다. 그런데 줄이 뒤죽박죽 섞여있어서 왼쪽에 있는 1열의 공간을 이용하여 줄을 순서대로 간식을 받을 수 있게 해야한다. 이 1열의 공간을 일종의 스택으로 취급하여 문제를 해결하면 된다. 입력받은 학생 번호 순서대로 아래와 같이 간식 받기를 시도한다. 만약 현재 간식을 받아야 할 번호와 줄 맨 앞의 학생 번호가 일치하지 않는다면 대기 공.. 2023. 8. 9. [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] 백준 2812 : 크게 만들기 문제 링크 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해설 N자리 수에서 K개의 숫자를 지워서 만든 가장 큰 수라는 것은 결국 앞자리 숫자가 뒷자리 숫자보다 커야한다는 것을 의미한다. 이를 처리하기 위해 스택을 사용할 수 있다. 입력으로 주어진 수를 각 자리수의 배열로 생각하여 진행한다. 앞에서부터 각 자리의 숫자를 스택에 삽입한다. 이 때, 스택에 숫자를 삽입하기 전에 이미 삽입된 숫자들을 순차적으로 확인하여 현재 삽입해야 할 숫자보다 작은 숫자를 모두 제거하고, 제거한 숫자의 개수를 기록한다. 제거한 숫자의 개수가 K개가 되었다면 남은 모든 숫자를 스택에 삽입한다. 모든 .. 2023. 4. 4. [Effective Java] 상속보다는 컴포지션을 사용하라(Feat. Stack) 목차 상속보다는 컴포지션을 사용하라 - 이펙티브 자바 3/E 아이템 18 상속은 자바가 갖는 유연한 구조의 기반이 되는 기법이다. 잘 사용한 상속 구조는 애플리케이션의 확장과 유지보수를 수월하게 해주지만, 잘못 사용한 상속 구조는 예상하지 못한 문제를 일으킬 수 있다. 이번 포스트에서는 자바의 Stack 클래스를 예시로 잘못 사용한 상속 구조에서 발생할 수 있는 문제와 컴포지션을 통해 이러한 문제를 해결하는 것을 다룰 것이다. 상속 일단 여기서 다루는 상속은 오직 클래스에서 클래스로의 상속만 해당된다. 상속을 사용하면 기본적으로 자식 클래스는 부모 클래스의 public과 protected 속성 + 자식 클래스만의 속성을 갖게 된다. 이 과정에서 상속은 캡슐화를 깨트리게 된다. 자식 클래스는 부모 클래스에.. 2023. 2. 27. [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. [Kotlin] 백준 25497 : 기술 연계마스터 임스 문제 링크 25497번: 기술 연계마스터 임스 $1$, $2$, $S$ - $K$, $2$로 스킬을 성공적으로 총 4번 사용했다. www.acmicpc.net 문제 해설 이전에 많이 나왔던 괄호 짝 맞추기와 비슷하게 스택을 활용하는 문제이다. 연계 기술 LR과 SK의 짝을 맞춰서 기술 성공 횟수를 카운트해야 하는데, 문제에 연계 기술을 사용할 때 사전 기술과 본 기술 사이에는 다른 기술을 사용해도 연계가 정상적으로 이루어진다는 언급이 있다. 즉, LSRK이나 SLKR 등과 같이 L, R, S, K가 섞여있어도 상관없다는 것이다. 이를 구현하기 위해 LR의 짝을 맞출 스택과 SK의 짝을 맞출 스택, 총 2개의 스택을 선언하여 문제를 해결한다. 연계 기술은 사전 기술과 본 기술이 모두 성공해야 1회로 카운트.. 2023. 1. 6. [Kotlin] 백준 17952 : 과제는 끝나지 않아! 문제 링크 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 문제 해설 문제의 규칙 1, 2번에 의해 스택을 사용하면 된다는 것을 알 수 있다. 과제의 점수와 남은 시간을 나타내는 객체를 담는 스택을 선언한 후 입력에 따라 스택에서 연산을 진행한다. 0이 입력되어 과제가 주어지지 않았다면 스택의 가장 윗부분 과제의 남은 시간을 1 줄인다. 1이 입력되어 과제가 주어졌다면 스택에 새로운 과제를 추가한다. 이 때, 과제를 받자마자 바로 시작하기 때문에 과제의 남은 시간에서 1을 뺀 값을 추가해야 한다. 각 연.. 2023. 1. 5. [Kotlin] 백준 9935 : 문자열 폭발 문제 링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해설 스택을 사용하여 해결할 수 있다. 문제 해결 과정은 다음과 같다. 먼저 문자열을 앞에서부터 순회하면서 스택에 문자를 삽입한다. 스택에 문자를 삽입하는 도중에 폭발 문자열의 마지막 글자가 나타나면 폭발 문자열의 길이만큼 스택에서 문자를 제거하여 폭발 문자열인지 체크할 문자열을 만든다. 이 때 스택에서 현재 스택의 크기가 폭발 문자열의 길이보다 작을 수 있기 때문에 EmptyStackException을 방지하기 위한 체크 로직을 .. 2022. 12. 19. 이전 1 2 다음
