오블완

풀이N개의 문자 중, 가장 왼쪽 문자를 기준으로 다음에 오는 문자들과 비교한다.사전 순으로 빠른 문자는 가장 왼쪽(First)에 배치하고, 반대라면 가장 오른쪽(Last)에 배치한다.  문제를 읽고 예제 출력을 봤을 때 조금 의아했다.분명 사전 순서로 배치되었을 텐데 어떻게 ASDFG, AAABCBC가 나오는 걸까. A S D F G 의 알파벳 카드가 주어졌을 때, A를 먼저 뽑고 다음으로 S, D... 순서로 뽑게 될 것이다.현재 소지 중인 가장 왼쪽에 있는 카드와 다음으로 뽑은 카드를 비교한다.D 카드를 뽑았을 때, 사전 순서대로라면 A 카드 오른쪽에 배치해야하지만 이미 S 카드가 배치된 상태이다. 여기서 그리디 알고리즘을 다시 살펴보면모든 경우에 최적해를 보장하지 않는다.한번 결정한 것은 번복하지 ..

풀이거스름돈 동전의  최소 개수를 계산하는 것에 있어서 가장 효율적인 방법은 5원부터 사용하는 것이다.5원으로 가능한 한 많이 나누고, 나머지 금액을 2원으로 맞춰야 한다. 구현 1 - 실패import java.io.*;public class Main { static final int[] COINS = {5, 2}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int count = 0; ..

풀이생성 마법은 고양이를 1마리씩 소환하고, 복제 마법은 현재 고양이 수 이하만큼 소환할 수 있다. 생성 마법이든 복제 마법이든 최소한의 행동으로 입력된 n마리의 고양이를 소환해야 한다. 두 가지 마법 중 가장 최적의 마법을 선택하고, 현재 고양이 수에서 해당 마법으로 추가한 고양이 수를 더한다.이 과정을 고양이 수가 n이 될 때까지 반복한다. 이때, 마법이 선택될 때마다 행동 횟수를 증가시킨다. 구현1 - 실패(시간초과)import java.util.Scanner;public class Main { static long catCount = 0; // 현재 고양이 수 static final int GENERATE_COUNT = 1; // 생성 마법은 무조건 1마리씩 추가한다. public..

풀이모든 토마토가 익는 최소 일수를 구하는 BFS 문제이다.창고 칸에 맞게 입력된 토마토에서 익은 토마토들만 Queue에 저장한다.BFS로 위,아래,왼쪽... 총 6 방향을 탐색하여 익지 않은 토마토 0인 경우 익은 토마토 1로 변경한다. 이때, 익은 토마토 1이라는 표시 대신 익은 날짜를 넣는다.익은 토마토들로 채워진 창고를 순회하여 0이 하나라도 있으면 -1을 반환하고0이 없다면 익은 날짜값들의 최댓값을 찾아 반환한다. 구현1 - 실패문제에 높이, 가로, 세로 값이 주어졌는데도 3차원 배열이 아닌 2차원 배열을 사용했다.개발하면서 3차원 배열까지 구현해본 적이 없어서인지 2차원 배열로도 풀 수 있을 줄 알았다. 탐색해야 하는 6개의 방향 중 앞, 뒤를 탐색할 때 문제가 발생했는데창고 크기를 초기화할 ..