Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처[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📖 문제 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로 나눈 나머지들의 합으로 정의 ..

🧫 문제 분석✔️ 출처행렬 테두리 회전하기 level 2📖 문제 현재 좌표에서 이동하는 문제다.1~row*columns 까지 이중 배열에 숫자를 각 넣어주고 그래프 탐색처럼, 이동 방향을 정하는 배열을 만든다. 이동 방향은 시계 방향 즉, 좌 하 우 상 순으로 움직인다. 이를 코드로 짜면 아래처럼 된다.  // 좌,하,우,상 int[] dy = {0, 1, 0, -1}; int[] dx = {1, 0, -1, 0};  방향을 정하고 주어진 queries의 좌표값 만큼 이동하면 된다. 주의할 점은 문제에서 queries 각 행은 [x1, y1, x2, y2] 로 주어지는데 x1행 y1열 이다. x2 - x1, y2 - y1 만큼 방향으로 이동하면서 이전 값을 넣어주고 기존 값을 따로 저..

🧫 문제 분석✔️ 출처다리를 지나는 트럭 level 2📖 문제 2번 재시도 끝에 풀은 문제다.  처음 시도에는 다리 위에 올라간 트럭이 경과한 시간을 잘 못 설계해서 계속 틀렸다.  두 번째 시도는 조건문 하나를 추가하지 않아서 틀렸었다. 4,5,6,9번  다리위에 있는 트럭을 제거해야하는 경우의 수는1. 다리에 트럭이 현재 올라갈 수 있는 트럭 최대 갯수만큼 있는 경우2. 새로운 트럭이 올라간다 했을 때 무게 하중을 넘어가는 경우3. 위 두 경우와는 별개로 다리의 맨 앞 트럭이 다리를 다 건너(시간이 지나) 빠져나가는 경우 이 세가지 경우에 대해서 트럭을 잘 빼준다면 문제없이 쉽게 풀 수 있을 것이다.  나는 3번을 안해서 계속 틀렸었다.. 🔅 문제 풀이import java.util.*;class..

🧫 문제 분석✔️ 출처숫자 카드 나누기 level 2📖 문제 영희, 철수 각각 하나의 카드를 선택해서 소인수 분해 후분해한 수들을 영희 카드와 철수카드를 나눠본다.  영희 카드 중 하나를 소인수분해 했을 경우영희 자신의 모든 카드 수는 소인수로 나눠지면서, 철수 것은 나눠지면 안된다.  반대의 경우도 마찬가지이다.  🔅 문제 풀이import java.util.*;class Solution { // 가장 작은 수 선택후 소인수 분해 // 분해된 수들로 해당 배열을 다 나눠본다. boolean으로 나눠지는지 확인 // 다 나눠지면 상대 카드들을 나눠본다. boolean으로 나눠지는지 확인 int max = 0; public int solution(int[..

🧫 문제 분석✔️ 출처호텔 대실 level 2📖 문제 시작 시간을 기준을 정렬후빈 방이면 방을 배정해주고, 끝나는 시간 + 10 을 해준다. 그리고 다음 예약자는 우선, 배정된 방중 퇴실후 시간대인 방을 찾는다.없다면 새로운 빈 방을 배정해준다.  이를 반복하면 된다.  예약 시간이 자정을 넘어가는 경우는 없다.  🔅 문제 풀이import java.util.*;class Solution { public int solution(String[][] book_time) { // 최대 룸 개수, 시-분 Integer[] time = new Integer[1000]; // 시작 시간 순 정렬 Arrays.sort(book_time, (o1, o2) -..

🧫 문제 분석✔️ 출처마법의 엘리베이 level 2📖 문제  우선 예제를 보고 생각해보면어떨 때는 올림이 좋고 어떨 때는 내림이 좋다. 2554는 16번2454는 어떨까?단순히 5라고 올리면 17번이 된다.  하지만 전부 내리면 15번이면 된다. 555를 예로 들어보자. 5를 내리면 15번이지만5를 다 올리면 +1 5번  = 560+10 4번 = 600+ 100 4번 = 1000- 1000 1번 = 0 14번 이 된다.  즉, 5가 핵심이다. 연속으로 5가 나오면 올리는 것이 좋고아니라면 내리는 것이 좋다.  뒤에 숫자부터 판별한다.  🔅 문제 풀이class Solution { // 현재 층수 + 버튼 수로 이동 // 0보다 작으면 안움직임 // 0층이 가장 아래층 //..

🧫 문제 분석✔️ 출처쿼드압축 후 개수 세기 level 2📖 문제 분할 정복 문제 처음은 전체를 다 돌아본다. for문으로 주어진 영역이 모두 같은 수 인지 확인 아니라면 4등분으로 영역을 나눠서 각각 영역별로 재호출영역 길이 / 2 한 값으로 4등분한다. 여기서는 행의 길이가 영역을 정한다. 비슷한 문제 포스팅 백준 1074번 : Z백준 1030번 : 프렉탈 평면백준 2447번 : 별 찍기 - 10백준 2448번 : 별 찍기 - 11🔅 문제 풀이class Solution { // 분할 정복 // for문으로 해당 영역 탐색 int[] count = new int[2]; public int[] solution(int[][] arr) { divAndConque..