문제 유형부터 DP를 이용하라고 나와 있었다. 저번처럼 Top-down 방식과 Bottom-up 방식 모두를 생각해서 풀었다. 나는 Top-down 방식이 먼저 떠올랐고 재귀를 통해 성공했다. 오히려 점화식을 도출해야 풀 수 있는 Bottom-up 방식이 더 어려웠다. Top-down 방식은 n의 조건이 최대 10이기 때문에 성공한 것 같다. 아마 n의 크기가 컸다면 재귀 호출이 많아져서 시간 초과가 났을것 같다. Bottom-up 방식에서는 동적으로 배열의 크기를 설정했는데 런타임 에러가 나서 초기값을 11로 고정해서 풀었다. Top-down 방식 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea..

문제 설명에 힌트가 이미 나와 있었다. 앞사람의 시간이 적어야 총 걸리는 시간이 최소일 것이다. 따라서 P배열을 오름차순으로 정렬하여 더하면 최소 시간이 된다. 간단한 문제였다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.pars..

지금까지는 대부분의 코딩 테스트 연습을 프로그래머스에서 했다. 이제 유형별로 다양한 문제를 접해보고 싶어 백준도 틈틈이 풀어보려고 한다. 문제를 처음 읽고 DP가 바로 떠오르지 않았다. 예전에 피보나치 문제를 풀면서 DP를 처음 접했던 기억이 있는데 잘 이해하지 못하고 겨우 풀었던것 같다. 이번에는 DP 문제인걸 알고서도 연습이 안되어 있어 한참을 고생했다. DP, DFS/ BFS, 최단거리, 그리디를 집중적으로 연습해볼 생각이다. N에서 1로 만드는 연산의 최솟값을 구하라고 하니 자연스럽게 Top-Down 방식이 먼저 떠올랐다. 재귀를 이용해야 하는데 아직 재귀가 익숙하지 않아 조금 버벅거렸다. IDE에서는 정답이 나오는데 백준에서는 계속 시간 초과에 걸려서 검색해본 결과 제한 시간내에 통과하기 위해서..

작년 카카오 공채 문제였다. 당시 처음으로 코딩 테스트를 경험해보고자 지원해서 풀어봤지만.. 1문제밖에 못풀었었다. 문제를 읽고 오랜만에 구현 방법이 제대로 떠오르지 않았다. Map을 이용해야 한다는 건 알겠는데 Map을 어떻게 이용해야 할지 명확하게 떠오르지가 않았다. 그래서 이중 for문을 마구 쓰며 풀었다. 구현하면서도 이건 아닌데 싶었는데 딱히 방법이 없어 끝까지 해봤다. 답은 구해지는데 테스트 케이스 7~8개에서 시간 초과가 났다. 처음 작성한 코드 public int[] solution(String[] id_list, String[] report, int k) { int[] answer = new int[id_list.length]; int[] cnt = new int[id_list.lengt..

문제를 읽자마자 완전탐색으로 구현해야 한다고 생각했다. 정렬을 해봐야 의미가 없고 던전의 개수도 8개 밖에 되지않아 완전탐색으로 충분히 해결할수 있을것 같다는 생각이 들었다. Dfs를 이용해서 어렵지 않게 풀었다. 최종코드 public int solution(int k, int[][] dungeons) { // DFS를 위한 전역변수 설정 public static boolean[] visit; public static int answer = 0; // 던전 개수만큼 visit 설정 visit = new boolean[dungeons.length]; // 최댓값을 위한 cnt int cnt = 0; DFS(k, dungeons, cnt); return answer; public static void DFS..

자카드 유사도를 구하는 문제이다. 예전에는 엄청난 문제 설명에 기가 죽어서 도전해보지 못했지만 이번에는 나름 설계를 먼저 한 후 구현에 도전했다. // 1. 두글자씩 끊기 // 1-1 소문자열로 통일 // 1-2 공백, 특수문자가 들어간 문자열 버리기 // 2. 교집합과 합집합 구하기 // 3. 자카드유사도 구하기 // 4. 65536을 곱하고 정수부만 출력 처음 작성한 코드 package progammers; import java.util.ArrayList; public class News_L2 { public static void main(String[] args) { String str1 = "FRAN C+E"; String str2 = "french"; int answer = 0; // 공백, 특..

처음에는 Queue로 접근해야 하나 고민했다. 그런데 문제에 캐시 교체 알고리즘이 LRU라고 쓰여있는 걸 보고 처음 보는 알고리즘이라 찾아보니 LinkedList가 기반인 알고리즘이었다. 그래서 조금 더 생각해보니 Queue가 아니라 LinkedList로 구현하는 게 훨씬 쉽겠다 싶었다. 어렵지 않게 작성하여 통과했다. 최종코드 import java.util.LinkedList; class Solution { public int solution(int cacheSize, String[] cities) { int answer = 0; // cities 값을 소문자로 변환 for (int i = 0; i < cities.length; i++) { cities[i] = cities[i].toLowerCase(..

예전에 레벨 1에서 봤던 괄호 문제보다 몇 단계 어려운 문제같이 느껴졌다. 문제가 상세한 요구사항이 있었는데 이를 하나씩 따라가면 답이 나오는 문제였다. 다만, 그 과정은 쉽지 않아 많이 고민했었다. 키포인트는 결국 재귀였는데 메서드를 분리해서 재귀를 구현하는 게 익숙하지 않아 디버그 모드를 많이 이용하여 풀었다. 최종 코드 import java.util.Stack; class Solution { public static String solution(String p) { // 입력 문자열이 공백이면 공백반환 if(p.equals("")) { return ""; } int cnt = 0; StringBuilder sb = new StringBuilder(p); StringBuilder u = new Str..

이번 문제는 오랜만에 재밌게 풀었던 문제였다. 처음 생각보다는 조금 시간이 걸렸지만 깔끔한 문제였다. 해시맵은 데이터 저장을 리스트는 로그를 남겨 반환했다. 해외에서는 한국처럼 인터넷을 쓸 수 없어서 너무 불편하다... 최종 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; class Solution { public String[] solution(String[] record) { // 로그를 저장하기 위한 리스트 List list = new ArrayList(); // 아이디와 닉네임을 저장하기 위한 해시맵 HashMap hm = new HashMap(); for (..