Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처부대 복귀 level 3📖 문제 최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다.  몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다.  목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되방문한 곳이 source[i] 면 거리값을 저장한다.   물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다.   참고 HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버..

🧫 문제 분석✔️ 출처연속 펄스 부분 수열의 합  level 3📖 문제 문제를 잘못 이해해서 삽질했다. 펄스 수열을 연속 수열에 패턴대로 곱했을때 최댓값이 나오는 연속 펄수 부분수열을 구하는 것이였다. 나는 잘못 이해해서 펄스 수열 처럼 수열의 연속 부분수열이 3,-6,1,-4 이런식으로 1,-1 이런 패턴이 유지되는 연속 부분 수열에만 펄스 부분 수열 1,-1을 곱해서 양수가 되는 것만 합쳐서 최댓값을 구했다. 당연히 틀렸고 이 문제는 사실 펄스 수열은 페이크고 누적합 문제이다.   주어진 수열에 펄스 수열 패턴을 곱해서 2개의 수열로 만든다.1,-1 패턴을 곱한 수열-1, 1 패턴을 곱한 수열 이제 누적합으로 풀면 된다.  나는 누적합 하면서 최댓값과 최솟값을 구하고  최댓값 - 최솟값을 하되 최..

🧫 문제 분석✔️ 출처섬 연결하기 level 3📖 문제 다익스트라로 했다가 생각해보니 이건 최단경로가 아닌 최소비용으로 연결하는 거였다.알고리즘 시간때 배웠던 걸로 기억하는데 최소신장트리 였던걸로 기억한다.  서로소 집합, 유니온, find 등 같은 걸 배웠었는데 기억이 안나서 결국 찾아봤다. https://sskl660.tistory.com/72 자세한 이론은 위 블로그 참조 핵심은 최소 비용으로 정렬하고 연결하는 두 노드(섬)의 부모가 서로 달라야한다. (사이클 방지, 최소 신장 '트리' 이기에 사이클은 없어야한다. )이때 find 메서드를 사용해서 각각 부모를 찾는다. 두 노드의 부모가 서로 다르다면 union 메서드를 사용해서 두 노드 중 부모가 더 작은 곳으로 편입된다. 이때 실제 원소가 편..

🧫 문제 분석✔️ 출처기지국 설치 level 3📖 문제 간단하면서도 생각할게 좀 있는 문제였다.N은 2억이므로 배열을 만들 생각은 하면 안된다.  stations가 최대 10만이므로 stations을 이용해서 푸는 문제이다.  나는 우선 처음 기지국의 전파범위와 처음 아파트 사이의 거리를 구하고 그 거리가 0이하가 아니라면 그 거리를 새로운 기지국을 설치했을때 전파범위로 나눈 값을 더했다.  그리고 기지국 사이에도 위와같이 연산을 해주고 마지막아파트와 마지막 기지국 사이의 거리도 동일하게 계산해주었다.   이번에 하면서 Math.ceil 과 직접 나누기와 나머지연산을 더하는 식으로 2가지로 해봤는데좋은 경험을 한 것 같다. - 664 / 667 을 연산했을 때 -0.9955 정도의 값이 된다.  Ma..

🧫 문제 분석✔️ 출처단속카메라 level 3📖 문제 탐욕법 문제로예전에 포스팅했던 요격시스템과 비슷한 문제다.  시작지점을 기준으로 정렬하고 (다음 차량의 시작지점 이때 다음 차량의 끝지점이 기준 차량의 끝지점보다 작다면 기준 차량의 끝지점을 갱신한다.  왜냐하면 최소한의 카메라를 설치해야하기에 최대한 겹치는 부분에 카메라를 놓아야한다. 이때 끝지점이 제일 작은 것을 기준으로 그 안에 겹치는 부분이 최대 중복 차량의 위치이며카메라 설치 위치이다. 잘 모르겠다면 요격시스템 포스팅을 보길 바란다.  🔅 문제 풀이import java.util.Arrays;class Solution { // 고속도로 진입 지점을 기준으로 정렬 // 끝 범위 안에 시작지점이 있으면 하나로 취급 pu..

🧫 문제 분석✔️ 출처숫자 게임 level 3📖 문제 B팀은 A를 이길 수 있게 순서를 바꾼다. 원소가 같다면 승점을 얻지 못한다. A팀에 원소에 맞게 B팀 원소를 바꾸면 된다.  오랜만에 투 포인터 문제가 나왔다. A팀과 B팀을 오름차순 정렬한다. (어짜피 A팀은 순서가 있다 하더라도 B팀은 A팀에 이기도록 순서를 바꿀 것이기에 정렬해도 상관없음) 그리고 각각 원소를 비교해서 B가 더 크면 승점을 얻어주면 되는 간단한 문제이다. 🔅 문제 풀이import java.util.Arrays;class Solution { // 승점만으로 답 판단, B팀은 순서를 바꿀 수 있음 public int solution(int[] A, int[] B) { int answer = 0; ..

🧫 문제 분석✔️ 출처최고의 집합 level 3📖 문제 각 원소의 합이 S가 되면서 각 원소의 곱이 최대가 되는 집합을 구하는 문제이다.  각 원소의 곱이 최대가 되려면각 원소의 값이 대체로 균일해야한다.  즉, s를 n개의 원소로 나눈  균등한 값을 n개가 나눠 갖고,s를 n으로 나눴을 때 나머지 만큼 원소에 더해준다.  문제에서 오름차순 정렬로 반환하라는 것과s를 n으로 나눴을때 나머지가 n을 넘길 수 없다는 걸 알고 있을 것이다.  즉, 나머지 값을 횟수로 사용하여집합 배열 맨 마지막 인덱스부터 거꾸로 나머지 값 횟수만큼 이동하면서  1씩 추가해주면 된다.  ex)n = 3, s = 17 이라 했을 때17 /3 = 5 answer = {5,5,5} 17 % 3 = 2 2번 뒤에서부터 1씩 추가 ..

🧫 문제 분석✔️ 출처단어 변환 level 3📖 문제 begin 알파벳 중 하나를 words 단어중 하나의 알파벳으로 바꿀 수 있다.순서는 상관없고, 변경을 최소한으로 해서 target을 만들면 된다.   백트래킹하면서 words를 탐색한다.  words 각 단어의 알파벳을 begin의 각 알파벳과 비교해서 2개이상 다르면 바꾸지 않고 넘어가도록 한다.  만약 알파벳이 1개만 다르다면 그 단어를 begin으로 하고백트래킹 탐색을 한다. 🔅 문제 풀이class Solution { // 완전탐색 // 백트래킹 boolean[] visited; int min = Integer.MAX_VALUE; public int solution(String begin, Str..

🧫 문제 분석✔️ 출처야근 지수 level 3📖 문제 약간 탐욕법 문제인듯하다.Demi가 퇴근까지 N시간 남았고, 그 시간안에 남은 작업량(works)를 적절히 분배해서 작업을 하여 야근 피로도가 최소가되게 즉, S={w^2 ∣ w∈works} 이 최솟값이 되게 하면 된다.   예시 1번을 보면 4,3,3 이 남은 작업량, n이 퇴근까지 4시간 남았다.야근 피로도는 제곱이기에 값이 매우 커진다. 따라서 남은 작업량들을 균등하게 만들어야한다.  works[0] - 2, works[1] - 1,  works[2] - 1= 2, 2, 2이렇게 분배하여 최솟값을 구하면 된다.   풀이 정리해당 문제는 배열로 풀면 좋을 것 같아서 배열로 풀어보았다.각 works의 값을 인덱스로 하고 개수를 카운팅한 뒤 max..