우선순위 큐3 [백준 Silver 4] 11656 접미사 배열 - Java 문제링크 : https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 접근 과정 : 문자열 S를 어떻게 자를지 / 접미사들을 어떻게 정렬시켜서 출력할지 두 가지만 생각하면 된다. 문자열을 자르는 방식으로는 substring 메소드와 char를 하나씩 더해주는 방법이 있다. 접미사를 정렬하는 방식에는 우선순위 큐와 배열+Arrays.sort / List+Collections.sort 가 있다. 소스 코드 및 결과 : /* 접미사 배열 */ import java.io.*; import java.util.*; public class Ma.. 2022. 1. 13. [백준 Gold 2] 1766 문제집 - Java 문제링크 : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 접근 과정 : 결국 먼저 풀어야하는 문제가 없고, 문제 번호가 작은 것부터 출력하면 된다. 문제는 2가지 방법으로 접근했다. 1. 해당 문제를 기준으로, 먼저 풀어야 하는 문제와 나중에 풀어야 하는 문제를 저장하는 List 2개를 이용해서 접근 우선순위 큐에는 현재 풀 수 있는 문제를 집어넣어서, 문제 번호가 작은 것부터 풀었다. 문제를 풀 때, 해당 문.. 2022. 1. 13. [백준 Gold 4] 1261 알고스팟 - Java 문제링크 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 접근 과정 : 결국 목적지까지, 벽을 최소한으로 뚫고 가야하는 문제이다. 일반적으로 벽을 뚫은 횟수를 포함한 BFS를 생각했다. 우선순위큐로 벽을 뚫은 횟수가 가장 적은 경우를 꺼내면서 BFS 탐색을 실시했다. 벽을 만났을 때는, 벽을 뚫은 횟수+1 해서 우선순위 큐에 집어넣고, 벽이 아니면 현재 벽을 뚫은 횟수를 집어넣는다. 이렇게 하면 쉽게 해결할 수 있다. .. 2021. 12. 29. 이전 1 다음
