지금까지는 대부분의 코딩 테스트 연습을 프로그래머스에서 했다. 이제 유형별로 다양한 문제를 접해보고 싶어 백준도 틈틈이 풀어보려고 한다. 문제를 처음 읽고 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 (..

문제를 보자마자 큐를 이용해야 한다는 느낌이 왔다. 다만 실제 코드 작성은 쉽게 되지 않았다. 특히 까다로웠던 부분은 다리 위 트럭 무게 총합 + 다음 올라와야 하는 트럭 무게가 다리 하중보다 큰 경우였는데 이때 가장 먼저 올라갔던 트럭이 내려와야 하므로 대기하는 시간을 추가하는 부분이었다. 이 부분을 고려하지 못해서 계속 실패하다 검색을 통해 힌트를 얻어 해결했다. 최종 코드 import java.util.LinkedList; import java.util.Queue; class Solution { public int solution(int bridge_length, int weight, int[] truck_weights) { int answer = 0; Queue queue = new LinkedL..

문제를 해결하기 위해서는 크게 두 부분이 필요했다. 첫 번째는 주어진 numbers에서 모든 조합을 찾는 것이고 두 번째는 조합에서 소수를 판별해서 그 개수를 반환하는 것이다. 소수를 판별하는 부분은 금방 작성했지만 모든 조합을 찾는데 시간이 정말 오래 걸렸다. 모든 조합을 찾는 방법이 재귀, 백트래킹 등등 어려 방법이 있었는데 재귀를 거의 써본 적이 없어서 재귀 기본 강의를 듣고 실제 코드 작성은 막히는 부분마다 검색으로 해결하여 풀었다. 프로그래머스 말고도 백준에서 재귀와 백트래킹 유형을 풀면서 익숙해져야겠다. 최종 코드 import java.util.HashSet; import java.util.Iterator; class Solution { // 전역변수로 HashSet 선언 HashSet hs ..