본문 바로가기

ALGORITHM

 (212)
백준 1913 달팽이 (Java) 1. 문제 링크 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 흔히 생각하는 달팽이의 역순 진행이다. 제일 큰 숫자부터 돌면서 방향 벡터를 이용해 숫자를 채웠다. 표를 벗어나거나 이미 숫자가 들어간 자리라면 방향을 바꾼다. 그리고 출력은 꼭 StringBuilder로 해야 하는 것 같다. System.out.print로 모든 것을 출력하니까 시간 초과가 나왔다. 4. 코드 import java.io.BufferedReader; import java.io.IOExcept..
백준 9012 괄호 (Java) 1. 문제 링크 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 큐를 이용해 여는 괄호가 나오면 큐에 넣고, 닫는 괄호가 나오면 큐에서 꺼낸다. 큐에서 꺼낼 때 큐가 비어있거나, 모든 문자열이 끝났는데 큐에 남아 있다면 VPS가 아니다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.uti..
백준 9205 맥주 마시면서 걸어가기 (Java) 1. 문제 링크 2. 문제 및 입출력예제 3. 문제 풀이 시작점과 끝점이 정해져 있어 좌표 기준으로 BFS를 진행했다.. 시작점을 큐에 넣고 큐가 빌 때까지 탐색한다. 편의점과 현재 위치를 전부 비교하면서 맥주 20병으로 갈 수 있는 거리(1,000) 이내인지 확인하면서 큐에 넣고 방문 처리를 한다. 페스티벌 위치에 도착하면 happy를 출력한다. 끝까지 도착하지 못한다면 sad를 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; public class Main { stati..
백준 1402 아무래도이문제는A번난이도인것같다 (Java) 1. 문제 링크 1402번: 아무래도이문제는A번난이도인것같다 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)이 주어진다. 테스트 케이스마다 두 정수 A, B(-231 ≤ A, B ≤ 231-1)가 주어진다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 처음에는 아무 생각 없이 문제를 풀다가... 어느 순간 문제 조건이 너무 없는 걸 보고 생각한 결과 특정값을 만들 때 어느 정도를 만들어 놓고 1과 -1을 조합하면 어떤 값이든 만들 수 있을 것 같다는 생각이 들었다. 그래서 코드가 아주 간단하게 끝났다! 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..
백준 13305 주유소 (Java) 1. 문제 링크 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 일직선 상에 있는 도시를 가는데 최소 주유 비용을 찾는 문제이다. 처음에는 해당 숫자가 몇번까지 숫자중에 제일 큰 가격인지 확인하려 했지만.. 숫자가 너무 커서 패스 도시를 지나가면서 제일 작은 가격이 나오면 저장하고 거리 길이만큼 곱해서 갔다. 여기서 마지막 도시는 주유하지 않으니까 리터 당 가격을 저장하지 않았다. 4. 코드 import java.io.BufferedReader; impor..
백준 10250 ACM 호텔 (Java) 1. 문제 링크 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 엘리베이터를 타고 이동하는 거리는 신경쓰지 않기 때문에 1호실이 다 차고 2호실이 다 차는 방향으로 진행된다. 그래서 높이 기준으로 나누어 떨어지는 경우와 아닌 경우로 나눴다. 나누어 떨어지면 마지막 층으로 가야 하고(0층이 없으니까), 아니라면 나머지에 해당하는 층으로 간다. 호수는 몫으로 했고 99호까지 있다는 형식에 맞춰서 2자리로 맞춰서 출력했다. 4. 코드 import java.io.B..
백준 1021 회전하는 큐 (Java) 1. 문제 링크 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 문제가 큐라서 큐로 풀어보려고 했는데 위치를 찾기 위해 LinkedList로 풀었다. LinkedList를 이용하니까 offer와 poll 모두 first와 last를 이용해 앞 뒤를 간단하게 확인할 수 있다. 찾아야 하는 원소의 위치를 찾고 중간보다 앞이라면 왼쪽으로, 중간보다 뒤라면 오른쪽으로 이동한다. 4. 코드 import java.io.BufferedReader; import java.io.I..
백준 2252 줄 세우기 (Java) 1. 문제 링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 두 학생의 키를 비교해 전체 학생을 줄 세우는 위상정렬 문제이다. 학생 전체에 대한 비교가 아니라 인접리스트를 이용했다. 방향 그래프를 입력받으면서 진입차수를 늘렸다. 진입차수가 0이 되면 큐에 넣고, 큐가 빌 때까지 큐에서 뽑으면서 인접 노드를 처리한다. 큐에서 뽑은 순서대로 ArrayList에 넣고 출력한다. 4. 코드 import java.io.Buffere..

티스토리툴바