코드를 느껴바라

문제 링크성공 여부(걸린 시간): 성공 (1시간 20분 55초)아이디어문제를 읽다보니 값이 커서 완전탐색으로는 절대 불가능임을 인지하고 이분탐색으로 풀어야 겠다고 생각했다.일단 diffs의 최소 최대값을 기준으로 이분탐색 시행해주고이분탐색으로 middle값을 숙련도를 여기고숙련도에 따라 퍼즐을 해결할 수 있는지 검사한다.검사했을때 가능하다 -> left를 middle + 1로검사했을때 시간이 초과다 -> right를 middle -1로그래서 마지막에 나온 숙련도를 return해줌정말 간단한 문제이지만 이분탐색을 오랜만에 해서 그런가 middle+1, middle -1로 안하고 그냥 middle로left나 right를 갱신해줘서 50분을 고생했다.정답코드import java.util.*;class Solu..

문제 링크성공 여부(걸린 시간): 성공(20분)아이디어DP 기본 개념문제인듯 하다.우측 또는 아래로 밖에 이동을 못하고 웅덩이로는 갈 수가 없다.map에 웅덩이를 -1로 표시해주고dp배열을 따로 만들어서 진행해주었다.점화식은 이렇다dp[i][j] = (map[i-1][j]!=-1?dp[i-1][j]:0) + (map[i][j-1]!=-1?dp[i][j-1]:0)위에서 저장된 dp값과 왼쪽에서 저장된 dp값즉 해당 칸에 도달하기 이전 칸까지 갈 수 있는 경우의 수를 웅덩이가 아니라면 합해준다.그럼 끝.풀이 코드import java.util.*;class Solution { public int solution(int m, int n, int[][] puddles) { int answer =..

문제 링크성공 여부 (걸린 시간): 성공(28분 45초)아이디어사실 거의 크루스칼 알고리즘 개념 문제이다.그러나 처음엔 제출했을때 부분점수를 받았는데 이유는 처음 아이디어를 설명하고 나서 하겠다. 우선순위큐에 각 엣지들을 넣어서 작은 순서대로 엣지를 뽑으며 연결해줌단 사이클을 발생 시키는 엣지는 제외해야함사이클이 어떻게 발생하는 지는 hashSet에 이미 연결된 노드의 번호를 저장해두었기에만약 엣지의 양 노드가 모두 이미 저장되어 있다면 사이클로 간주하고 continue했음 -> 이 부분이 문제였다.아니라면 노드 추가해주고 answer+= 엣지 가중치 왜 문제가 생기느냐면 만약 이러한 경우가 있을때2와 3은 이미 set에 등록되어 있기에 2-3을 연결하는 엣지는 사이클이 아님에도 걸러지게 된다.그래서 이..

문제 링크성공 여부(걸린 시간): 성공(31분 52초)아이디어처음에는 일단 전부 BFS를 돈다고 했을때도 충분할 것 같다고 생각했고 (열만 다르면 중복해서 탐색함 ㅎㅎ..)계산해보니 최대 25000번 BFS를 돎 근데 BFS에서 한번에 최대 25000개의 블록을 방문할때25000^2 = 625000000 10초내로 가능하다고 생각하고 했더니 시간초과가 떠서 부분점수를 받게되었다. 그래서 느낀점 아슬아슬할때는 그냥 안전한 방법으로 하자 시간을 줄일 수 있는 방법을 고안해보았다. 사실 코드를 작성하다 생각났지만 외면했던 아이디어 BFS를 열마다 새롭게 전부 돌지않고 해당 석유 덩어리를 돌고 석유의 양을 전부 세었을때그 석유덩어리가 걸쳐있는 모든 열에 석유의 양을 마지막에 + 해준다.어떤식으로 했냐면 걸치는 ..

문제 링크성공 여부(걸린 시간): 실패(56분 5초)아이디어일단 처음에 생각한 순서는 이러했다.1. 소문자로 바꾼 헤드 기준으로 사전순 정렬2. head가 같으면 number 작은 순으로 stable하게 정렬3. 넘버도 같으면 들어온 순서 그대로4. 마지막에 도출된 순서대로 원본 파일명을 순서대로 넣어주고 return 일단 이렇게 하기 위해서 어떻게 문자열을 저장할건지가 관건이었다. 난 HashMap으로 소문자인 헤드가 key, 원본 head, 원본 number부분과 원본 tail을 나누어 저장하고추가로 int로 바꾼 nuber도 같이 저장해줄 (우선순위큐에 넣을때 int로 바꾼 number기준으로 정렬하기 위함)node로 저장한 우선순위큐를 value로 저장했다.  정렬기준은 처음에는 number 오름..

문제 링크성공 여부(걸린 시간): ❌(20분)아이디어처음에는 순서를 전부 브루트포스로 조합하면 최대 17개의 노드를 0을 제외하고 모든 순서대로 조합했을때는 16! 이다. 사실 16!은 엣지를 생각치 않고 진짜 전부 돌려본 경우고만약 실제 노드 연결을 고려해서 노드 방문 순서를 작성하면 결국 연산수는 동일하지 싶다. (이진트리이기 때문에) 그당시엔 그렇게 생각을 못했고 생각한건 DFS로 해야한다는 것이었는데 방문한 노드들의 자식노드로 이동할때해당 노드의 다른 자식 노드도 다음 이동할 방문 리스트로 추가해야 했다. 그런데 도저히 방법이 떠오르지 않았고 그렇게 LV2라고 생각하고 있어서 20분이 지나자실패처리하고 힌트를 보았다... (알고보니 레벨 3 였음ㅎㅎ) 😅여기서 힌트를 보고 바로 풀어보았다. [P..

문제 링크성공 여부(걸린 시간): 1시간 55분 16초(성공)아이디어브루트포스로 전부 해보기엔 말도 안되는 시간이 나올것이라 생각해 카운팅소트처럼 하려고 했었다.그래서 시작과 끝을 순회하며 +1씩 넣어주며 그걸 누적합하여 adv_time을 텀으로 두어 차이를 구해 최대를 구하려했다. 🤔그런데 그것도 계산해보니 만약 play시간이 최대이고 전부 최대로 30만개가 들어오면+1씩 해주는 것만 해도 시간초과가 나는 상황이었다. 🐵그런데 불현듯 구간에 해당하는 모든 초들을 돌필요 없이처음에 1 그리고 끝 지점에 -1을 해주는 방식으로 처리를 한다. 예) 1~3초 (끝나는 시간은 카운트 않음)012345010-100누적합을 돌면 해당 초마다 로그가 몇개있는지 나오게 되고012345011000그걸 누적합을 한번 ..

문제 링크성공 여부: 실패(부분점수 40점)아이디어처음에 경우의 수를 계산하는데 2^40을 16000이네~ 하고 넘어가서 그냥 DFS로 풀었다...그 결과 시간초과가 발생하여 40점으로 마감했는데다시해보니 DP라는 생각이 들어 배낭문제인가? 싶었으나 도저히 떠오르지 않아 찾아보았다.아래는 40점짜리 완탐 코드이다.//실패코드import java.util.*;class Solution { static class Node{ int a, b; public Node(int a, int b){ this.a = a; this.b = b; } } static PriorityQueue pq; static int [][] ..

문제 링크성공 여부(걸린 시간): 실패(45분) -> Lv2 40분이상 걸리면 실패로 간주아이디어처음에 사실 문제를 제대로 읽지 않고 조건의 1~40%의 할인율을 전부 고려해야 한다고 생각하니40^7이라는 어마어마한 연산수가 고려되었고 그래서 DP라고 혼자 굳게 결심하고 푸는데아무리 봐도 모르겠는 부분이었다. 그래서 문제를 차근차근 다시 읽어보니 10, 20, 30, 40%의 할인율만 존재하는 것을 깨닫고바로 조합을 통해 각 이모티콘에 대한 할인율을 String으로 생성하고 그 String을 하나씩 돌면서내부에서 유저별로 기준 할인율과 조합의 원소인 해당 제품의 할인율을 비교해서 사면 money에 +해주었다. 그리고 해당 유저에 대한 모든 이모티콘을 사는지 안사는지 검사가 끝났을때누적된 비용이 해당 유저..

문제 링크성공 여부(걸린 시간): 성공 (59분 31초)아이디어순서대로 설명해보자면1. info 처리 => 같은 조건인 점수들은 묶어서 저장처음에 생각한 것은 각 조건의 앞자리만 따서HashMap을 이용해서 key는 jbjp(각 조건의 첫자리만 땀. 겹치는 경우가 없기에 가능)value는 ArrayList에 저장하고 qeury문을 수행할때 정렬하고 조건에 맞게 수행해주려고 했다. 그런데 그렇게 했다간 단순히 생각만 해도 최악의 경우 50000 X 100000즉, 약 50초 정도로 시간초과가 날것이라는 확신이 들었다.그래서 어떻게 처리해야 빠르고 간단하게 X 점수 이상의 점수 개수를 구할 수 있을까 생각해보았다. 불현듯 생각이 든것. 🔍 쿼리는 X이상의 값의 개수를 구하는 것으로 방향이 고정되어있다.!!..