문제 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 풀이 이 문제는 Deque(덱)을 이용해 풀이하면 된다. 덱은 양쪽에서 삽입과 삭제가 모두 가능한 자료구조이다. 풍선의 번호와 풍선에 적혀 있는 숫자를 저장할 풍선 data class를 정의하고, 이를 이용하여 입력 받은 수를 덱에 저장한다. 그 후, 덱이 비어질 때까지 반복하면서 풍선을 터뜨리는 순서를 구하면 된다. 덱의 첫번째 풍선을 터뜨리고, 풍선에 적힌 숫자에 따라 덱을 업데이트한다. 숫자가 양수인 경우, 덱의 앞부분에 있는 풍선을..

문제 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 스택을 활용해 올바른 괄호열인지 확인하여 값의 계산까지 구현하는 문제이다. 계산은 전체를 더한 결과값 sum과 중간 단계를 나타내는 tmp로 두 개의 변수를 사용한다. 여는 괄호인 경우 괄호에 해당하는 값을 스택에 넣어주고 tmp에 곱해준다. 닫는 괄호인 경우에 스택이 비어있거나 바로 전 괄호가 짝이 맞지 않다면 잘못된 괄호열이으로 결과값을 0으로 출력해준다. 잘못된 괄호열이 아니라면 바로 전 괄호가 짝이 맞다면 tmp를 sum에 더해주고, 스택..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용하여 최단 거리를 찾을 수 있다. 알고리즘은 우선 순위 큐를 활용하여 현재까지 발견된 최단 거리를 가진 정점을 기준으로 탐색한다. 각 정점까지의 사용되는 비용을 저장하는 배열을 만들고 시작 지점의 비용을 초기화해준다. 그 후, 우선 순위 큐에 시작 지점을 추가하고 탐색을 시작한다. 탐색 중에는 현재까지 저장된 비용보다 더 작은 비용으로 이동할 수 있는 경우에 해당 정점의 비용을 갱신하고 큐에 추가한다. 이 과..

문제 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 풀이 부등호를 만족하는 최소와 최대 정수를 백트래킹으로 찾는 문제이다. 입력받은 부등호에 따라 올바른 숫자를 선택하고 재귀적으로 탐색을 진행한다. 가장 먼저 완성된 답이 최소 정수, 가장 나중에 완성된 답이 최대 정수가 되는 것으로 각각 출력해주면 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val num = br.readLine(..

문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 주어진 도로와 도시 정보에서 모든 도시간의 거리가 1이라는 점을 이용해 너비 우선 탐색(BFS)으로 해결할 수 있다. 시작 도시로부터 BFS를 수행하며 거리를 계산하고 거리 배열에 저장해준다. 여기서 모든 도시간의 거리가 1이기 때문에 도시에 처음 도착했을 때의 거리가 최단 거리일 것이다. 탐색이 끝난 후 찾으려는 거리에 도시가 있다면 도시를 출력해주고, 없다면 -1을 출력한다. ..