Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처단속카메라 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..

🧫 문제 분석✔️ 출처[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 level 2📖 문제 이진 탐색 문제다. 그런데 이진탐색을 했더니 시간초과나서 다른 방법을 찾아서 삽질을 하고 식을 제대로 세우고 이진탐색으로 풀었다. 문제에서 주어진 조건을 식으로 풀어보면 아래와 같다. limit >= (diff[i] - level) * (time_cur[i] + time_prev[i]) + time_cur[i] 이를 만족하는 level 최솟값을 찾으면 된다.  좀만 더 간단히하면문제에서 diff - level 번 만큼 이전 문제를 다시 풀고(time_prev) + 현재 문제를 다시 풀어야한다(time_cur) diff-level 번 틀린 후 다시 풀면 time_cur만큼 시간을 사용한다.  즉, limit - ..

🧫 문제 분석✔️ 출처조이스틱 level 2📖 문제 탐욕법인데 정말 어려웠다.   먼저 알파벳 변경은 매우 쉽다. 주어진 알파벳 - 'A' (앞으로 가는 경우) 와  'Z'  - 주어진 알파벳 + 1 (뒤로 가는 경우)최솟값을 answer에 다 더해주면 된다.   문제는 커서 이다. 시계 방향, 반시계 방향으로 인덱스 돌리는게 도무지 떠오르지 않아서 삽질을 엄청했다. 배열에서 두 인덱스 사이의 거리 최솟값시계방향, 반시계 방향의 최솟값을 찾으면 된다.// a b 인덱스 ,n은 배열의 크기// 반시계방향 시계방향Math.min((a - b + n) % n, (b - a + n) % n));  어떻게 해서든 풀어보자는 마인드로 문자 길이가 20인걸로 보아 백트래킹 써도 되겠다 싶..

🧫 문제 분석✔️ 출처가장 큰 정사각형 찾기 level 2📖 문제 2번 시도후 푼 문제다. 1차 시도 정 사각형을 찾는게 문제인데 처음에는 1차원 배열에 각 열에 대한 개수를 세서최솟값을 갱신하면서 카운트를 하고최솟값과 카운트 값이 같다면 가장 큰 정사각형 후보로 넣는 식이였다.당연히 틀렸고, 시간초과났다.  2차 시도문득 생각해보니 DP에 대해 배웠을 때 값을 누적하고 원하는 부분의 값을 얻는 방법이 떠올랐다.dp[i][j] - dp[i-1][j] - dp[i][j] + dp[i-1][j-1] 여기에 정사각형 한 변의 길이를 더해주고 영역 값을 구한 뒤  정사각형 넓이 == 영역 값  ? 한 변 길이 + 1 , 정사각형 넓이 최신화  이런식으로 하면 되지 않을까 라는 생각에 해봤는데 성공했다. 정사..

🧫 문제 분석✔️ 출처디펜스 게임 level 2📖 문제 우선순위 큐를 사용한 탐욕법(그리드) 알고리즘 문제이다.  내가 생각한 방법1 ~ k번째까지는 무적권을 사용한다 가정하고 우선순위 큐에 넣는다.이때 최댓값을 저장한다.  2가지 경우 무적권 사용 라운드를 바꾼다. 현재 라운드의 적 수 >= 무적권을 사용한 라운드의 최대 적 수 현재 라운드의 적 수 > 무적권을 사용한 라운드의 최소 적 수 이 두가지를 만족하면서 최소 적수를 n에서 뺐을때 0미만이 안될때 무적권 사용 라운드를 바꾼다.그리고 최댓값을 갱신한다.   위 2가지 경우가 아니라면 남은 n 명이 현재 라운드 수보다 크거나 같으면 빼주어 현재 라운드를 막는다.  🔅 문제 풀이import java.util.*;class Solution { ..

🧫 문제 분석✔️ 출처테이블 해시 함수 level 2📖 문제 매우 간단한 구현문제 다만 4번 항목이 헷갈렸다.모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로 반환S_i를 누적합한다음 XOR 하라는 건가? 싶은데 그건 또 아닌거같아서 1번 데이터와 2번 데이터를 XOR 연산 후그 데이터를 또 3번 데이터와 XOR 연산 .. 이런식이다.  🔅 문제 풀이import java.util.Arrays;class Solution { // 해시 함수 매개변수 col, row_begin, row_end // col 번째 컬럼 기준 오름차순 , 같다면 기본키(첫번째 컬럼) 기준 내림차순 // 정렬후 S_i를 i 번째 행의 튜플에 대해 각 컬럼 값을 i로 나눈 나머지들의 합으로 정의 ..