문제를 처음 읽고 설계까지 시간이 좀 걸렸다. 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를 이용해서 각 자리에 들어갈 수를 구해야 한다는 걸 알게 되었지만 로직을 이해하기 ..

문제 이름이 이중 우선순위 큐라서 우선순위 큐로 풀어야 하나 생각했다. 그런데 코드를 반쯤 작성하고 나니 TreeMap을 이용하는게 더 간단하겠다는 생각이 들어 TreeMap을 이용해서 다시 짰다. 골드 4 문제치고는 쉬운편이라고 느꼈다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeMap; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamR..

N의 입력 크기가 1,000,000 까지 가능하므로 2중 for문을 사용해서 단순 비교를 하면 바로 시간초과가 날것을 예상했다. 그래도 한번 작성해 보았는데 1%에서 바로 시간초과가 난다. 어떻게 해야 할지 30분 정도 고민을 하다가 검색을 통해 힌트를 얻었다. 문제 해결의 키포인트는 정렬이다. 각 입력값을 낮은값부터 순위를 매겨서 처리하는것이다. 각 입력값에 대한 순위값을 출력하면 된다. HashMap을 이용해서 입력값과 순위값을 넣고 원본 배열과 비교하며 출력하면 된다. 구현이 어려운 문제는 아니지만 정렬이 필요하다는것과 적절하게 HashMap을 사용해야 한다는 생각을 하기 쉽지 않았다. 실패 코드(시간 초과) import java.io.BufferedReader; import java.io.Inpu..

처음에는 쉬운 구현 문제인줄 알고 HashSet을 이용해서 통과했다. 다 풀고 문제 유형을 확인해보니 비트 연산으로 분류 되어 있어 BitSet을 사용해서 다시 풀어보았다. HashSet을 이용할때보다 시간이나 메모리가 줄어들것으로 생각되었으나거의 차이가 없었다. if-else와 Stringtokenizer를 똑같이 사용해 그런것 같다. 최종코드(HashSet 사용) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { static int n; static HashSet set; static Strin..

처음에는 완전 탐색으로 구현하려고 했는데 코드를 작성하다 막혀서 포기하고 문제 유형을 확인했는데 그리디, 정렬이었다. 감을 잡을 수가 없어서 검색을 통해 힌트를 얻고 풀었다. 종료시간을 기준으로 정렬하게 되면 겹치는 회의와 겹치지 않는 회의를 알 수 있고 겹치지 않는 회의 중 가장 빠르게 끝나는 회의를 선택하면 된다. 문제가 그리디를 사용한다는 걸 파악하기 어려웠고, 정렬 또한 생각하기 어러웠다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(..

전형적인 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이라는 것도 쓰여있었는데 계속 실수하는 것 같다. 모든 연산자 배열을 나는 직접 입력했지만, 다른분들은 순열을 이용해서 배열을 생성했다. 확장성을 고려한다면 이 방법이 맞다고 생각이 ..

문제 설명이 좀.. .길다... 그냥 위에는 읽지않고 입출력 부분만 보고 풀었다. Map을 사용하면 간단하게 풀수 있는 문제이다. 다만 이 문제도 n과 m이 100,000까지 들어올 수 있어서 시간초과가 날수있다. 처음에는 HashMap을 하나만 생성해서 숫자가 입력되면 key값으로 value를 찾고 문자면 keySet을 반환해서 value로 key를 찾았다. 다만 keySet으로 반환해서 탐색하는 시간이 걸려서 시간 초과가 났다. 그래서 그냥 HashMap을 2개 생성해서 풀었다. 실패 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringToken..