PS/BOJ 백준 (6) 썸네일형 리스트형 /<BOJ 백준 15904번> UCPC는 무엇의 약자일까? - Java 문제 15904번 : UCPC는 무엇의 약자일까? 문제 해설 전형적인 그리디 알고리즘 문제이다. 입력받은 문자열에 순서대로 U, C, P, C가 존재하는지 확인만 하면 풀 수 있는 문제이다. 이를 코드로 나타내면 다음과 같다. public boolean isUCPC(String string) { int index = 0; for(char c : string.toCharArray()) { if(c == "UCPC".charAt(index)) { index++; if(index == 4) { return true; } } } return false; } string을 하나의 문자로 쪼개어 나눈다. 해당 문자가 문자열 "UCPC"의 index에 해당하는 문자와 일치하면 index를 1 추가하여 비교하는 방식이.. /<BOJ 백준 1343번> 폴리오미노 - Java 문제 1343번 : 폴리오미노 문제 해설 문제의 출력으로 "사전순으로 가장 앞서는 답을 출력한다." 라고 되어있으므로 여러 가지 정답 중 AAAA가 최대한 많이 나오는 경우가 정답이다. AAAA와 BB는 각각 4개와 2개의 알파벳으로 구성되어있으므로 입력으로 받는 X의 개수의 총합 또한 짝수가 되어야 한다. X의 개수가 홀수인 경우 폴리오미노를 덮을 수 없어 -1을 출력한다. 문제 해결 아이디어는 다음과 같다. 1. X의 개수를 세어 짝수인지 홀수인지 확인한다. 1-1. X의 개수가 홀수이면 -1을 출력하고 종료한다. 2. X의 개수가 4 이상이라면 폴리오미노 AAAA로 덮기 위해 X의 개수에서 4만큼 차감한다. 3. X의 개수가 2 이상이라면 폴리오미노 BB로 덮기 위해 X의 개수에서 2만큼 차감한다... /<BOJ 백준 1966번> 프린터 큐 - Java 문제 1966번 : 프린터 큐 문제 해설 문제의 이름과 설명에 나와있듯이 자료구조 큐(Queue)를 이용하여 문제를 풀 수 있다. 큐의 선입선출(First-In-First-Out) 특성을 이용하면 어렵지 않게 풀 수 있는 문제이다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Queue; import java.util.StringTokenizer; import java.util.LinkedList; public class Main { public void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStr.. /<BOJ 백준 1874번> 스택 수열 - Java 문제 1874번 : 스택 수열 문제 해설 본 문제의 이름과 본문에서는 스택을 이용하라는 내용이 제시되어있다. 따라서 자료구조 스택을 이용하여 이 문제를 해결해 보려고 한다. 다른 복잡한 조건이 없으므로 문제 해결 아이디어는 다음과 같다. 1. 주어진 정수 n에 대하여 1부터 n까지의 수열을 스택에 추가(push)한다. 2. 스택의 top에 있는 숫자와 입력받은 정수가 같을 때까지 스택에서 삭제(pop)한다. 3. 1번과 2번 과정으로 수열을 만들 수 있는 경우 push와 pop한 과정을 각각 "+"와 "-"로 나타낸다. 3-1. 수열을 만들 수 없는 경우 "NO"를 출력한다. 이를 코드로 구현하면 다음과 같다. int[] sequence = new int[n]; int currentNumber = 1; .. /<BOJ 백준 9012번> 괄호 - Java 문제 9012번 : 괄호 문제 해설 괄호 검사 문제는 자료구조 스택(Stack)을 사용하는 대표적인 문제이다. 본 문제 또한 스택을 이용하여 어렵지 않게 풀 수 있었다. 문제 해결 아이디어는 다음과 같다. 1. 괄호 '(' 가 오면 스택에 추가(push)한다. 2. 괄호 ')' 가 오면 스택 내부에 "(" 가 있는지 없는지 검사한다. 2-1. "(" 가 없으면 거짓임이다. 3. 제일 최근에 삽입된 "(" 를 스택에서 제거(pop)한다. 4. 위 2, 3번 과정을 테스트 케이스 수 T회 반복한다. 5. T번 반복 후 스택 내부에 괄호 "(" 가 있는지 없는지, 즉 스택이 비어있는지 확인한다. 이를 코드로 나타내면 다음과 같다. private static boolean isBalanced(String str.. /<BOJ 백준 1158번> 요세푸스 문제 - Java 문제 1158번 : 요세푸스 문제 문제 해설 N명의 사람이 모두 제거될 때 까지, 순서대로 K번째 사람을 제거하는 과정을 계속 진행하는 요세푸스 문제는 K-1번째 사람을 남겨두고 K번째 사람을 제거하면 된다. 이 아이디어는 자료 구조 "큐(Queue)"를 이용하여 해결할 수 있다. 큐는 먼저 들어온 데이터가 먼저 나가는 형식 First-In-First-Out 자료구조이다. 문제 제시된 바와 같이 순서대로 K번째 사람을 제거하는 것이므로 K-1번째 사람은 큐에서 제거한 후, 맨 뒤로 다시 추가하면 된다. 이 과정을 큐가 비어있을 때 까지 반복하면 된다. 자바에서 Queue 인터페이스는 LinkedList 클래스에서 구현되어 있다. 이를 코드로 구현하면 다음과 같다. while (!queue.isEmpty(.. 이전 1 다음