지금까지 풀어본 문제 중에 난이도가 가장 높았던 문제라고 생각한다. 지금까지 알고 있었던 지식을 총동원해야 풀 수 있는 문제였다. 정렬과 조합에 대해서 알아야 하고, 중간중간 생각해야 할 조건이 많아서 어렵게 느낀 것 같다. 특히 처음에 orders 배열을 정렬하지 않으면 기본 케이스 2개만 통과하고 점수는 하나도 얻을 수 없다. 만약 실제 시험이였다면 이 한 문제에 시간을 거의 다 쓰고. 처음 정렬의 하지않아 0 솔을 했을 것 같은 느낌이다.... 최종 코드 import java.util.*; class Solution { static HashMap stringMap; public String[] solution(String[] orders, int[] course) { // 1. orders의 값을 ..

문제를 처음 읽고 설계까지 시간이 좀 걸렸다. 8명의 프렌즈로 순열을 만들면 되는 건데 최대 8! 이니 숫자가 크지 않아서 dfs를 이용해 가능한 모든 순열을 만들고 조건을 검사하는것으로 생각했다. 만약 프렌즈의 숫자가 10을 넘어가는 숫자였다면 시간 초과가 날 가능성이 높아 백트래킹으로 풀었어야 할 것 같다. 최종 코드 class Solution { static int answer; static String[] arr = {"A", "C", "F", "J", "M", "N", "R", "T"}; public int solution(int n, String[] data) { boolean[] visited = new boolean[8]; answer = 0; dfs("", visited, data); r..

얼마 전까지 Lv3에 있었던 문제였는데 얼마 전에 Lv2로 내려왔다. 다른 Lv2는 기본적인 알고리즘을 구현할 수 있다면 바로 풀리는 문제들이었는데 이 문제는 알고리즘 + 응용이 필요하다고 느꼈다. 그래서 많이 어려웠고 Lv2 보다는 Lv3에 가까운 문제가 아닐까 생각이 든다. 처음에는 가능한 모든 순열을 전부 구하고 이를 리스트에 저장해 k번째 항목을 출력할 생각이었다. 그러나 메모리 초과, 시간 초과 등으로 성공하지 못했고 조건에 n이 20 이하의 자연수라는 것을 보고 최대 20! 개의 순열이 나오는 걸 고려하지 않았다는 사실을 깨달았다. 다른 방법이 도저히 떠오르지 않아 검색을 하여 다른 분들의 정답을 참고했다. k를 이용해서 각 자리에 들어갈 수를 구해야 한다는 걸 알게 되었지만 로직을 이해하기 ..

전형적인 DFS / BFS 문제였다. 구현은 쉬웠는데 계속 통과가 안돼서 30분을 넘게 봐도 이상한 점을 못 찾았는데 전역 변수 사용 시 메서드 내에서 초기화를 해야 통과한다. 최종 코드 class Solution { static int numberOfArea; static int maxSizeOfOneArea; static int cnt = 0; static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,-1}; public int[] solution(int m, int n, int[][] picture) { numberOfArea =0; maxSizeOfOneArea=0; int[] answer = new int[2]; answer[0] = numberOfAre..

2020 카카오 인턴쉽 문제로 근래에 풀어본 문제 중 가장 어려웠다. 첫 구현까지는 1시간 30분 정도 걸렸고.... 모든 케이스를 맞추기까지는 3시간이 걸렸다... 한 번에 로직을 짜기도 쉽지 않고 List값을 삭제하면 List의 사이즈가 계속 달라지는데 이를 어떻게 처리할지 대부분의 시간을 쏟았다. 또, 아무 생각 없이 변수들을 int로 만들어서 테스트 케이스에서 계속 70점을 받았는데 이를 long으로 고치니 결국 모두 통과되었다. 시작부터 long answer = 0이라는 힌트도 있었고 문제에 중간 계산 값이 2^63이라는 것도 쓰여있었는데 계속 실수하는 것 같다. 모든 연산자 배열을 나는 직접 입력했지만, 다른분들은 순열을 이용해서 배열을 생성했다. 확장성을 고려한다면 이 방법이 맞다고 생각이 ..

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