문제 1 / 제로 카드 게임
목표 : 카드 더미에서 두 그룹이 가진 카드의 합의 차이가 가장 작은 패널티를 구하기
해결방법 : 부분 집합의 합을 두 그룹으로 나눠 구해서 풀었다.
카드 갯수가 0개에서 2개까진 빠르게 구해줄 수 있어서 빠르게 계산해 리턴해줬다.
dp 배열은 i 개의 카드로 합이 j 가 가능한지 나타내는 배열이다.
sum/2 + 1 을 한 이유는 두 그룹의 합의 차이를 최소화하기 위해서 설정해줬다.
현재 카드를 사용하지 않는 경우, 이전 카드들로 합 j를 만들 수 있는 지를 가져오고
현재 카드의 값을 사용한다면 현재 카드 값을 사용해 합 j를 만들 수 있으면 dp[i][j]를 1로 설정하고 그렇지 않다면 이전 카드들로 합 j를 만들 수 있다면 그대로 유지한다.
이걸 반복해 dp[i][j]는 현재 카드 사용 여부에 따른 가능한 합을 모두 반영한다.
그 후 패널티가 가장 작은 값을 리턴해준다.
class Solution {
public int solution(int N, int[] cards) {
int answer = 0;
if(N==0) return 0;
if(N==1) return cards[0];
if(N==2) return Math.abs(cards[0]-cards[1]);
int sum = 0;
for(int card : cards) sum += card;
int[][] dp = new int[cards.length+1][sum/2+1];
dp[0][0] = 1;
for(int i=1; i<=cards.length; i++) {
for(int j=0; j<=sum/2; j++) {
dp[i][j] = dp[i-1][j];
if(j>=cards[i-1]) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-cards[i-1]]);
}
}
}
answer = sum;
for(int j=0; j<=sum/2; j++) {
if(dp[cards.length][j]==1) {
int groupOne = j;
int groupTwo = sum-groupOne;
answer = Math.min(answer, Math.abs(groupOne-groupTwo));
}
}
return answer;
}
}문제 2 / 세금
목표 : 세금 납부 정보에서 정보 수집을 위해 사용되는 min, max 값이 주어진다. min<= 세금 <= max 인 사람의 수를 구하기
해결방법 : 이분 탐색으로 풀었다.
처음엔 완전탐색으로 풀었는데 시간 초과가 났다. 그래서 시간복잡도를 줄여야겠다고 생각했다.
구해야될 배열에서 min 이상이고 max 이하인 것들만 조회하면 시간 복잡도가 해결된다고 생각했다. 그래서 배열을 정렬 후 min 이상인 값 중 최솟값인 minIndex와 max 값 초과 중 최솟값인 maxIndex를 구해서 maxIndex - minIndex 로 해당되는 인원의 수를 구해주었다.
import java.util.*;
class Solution {
public int[] solution(int N, int K, int[] arr, int[][] queries) {
List<Integer> answer = new ArrayList<>();
Arrays.sort(arr);
for(int[] query : queries) {
int min = query[0];
int max = query[1];
int startIdx = findMinIndex(arr, min);
int endIdx = findMaxIndex(arr, max);
answer.add(endIdx-startIdx);
}
return answer.stream().mapToInt(n -> n).toArray();
}
static int findMinIndex(int[] arr, int target) {
int left=0, right=arr.length;
while(left<right) {
int mid = (left+right)/2;
if(arr[mid]<target) {
left = mid+1;
} else {
right = mid;
}
}
return left;
}
static int findMaxIndex(int[] arr, int target) {
int left=0, right=arr.length;
while(left<right) {
int mid = (left+right)/2;
if(arr[mid]<=target) {
left = mid+1;
} else {
right = mid;
}
}
return left;
}
}문제 3 / 봉술가
목표 : N*N 크기의 맵에서 가장 가까운 그래플러와의 거리가 최대가 되는 빈 칸을 위치를 구하기
단, 여러 곳일 경우 가장 낮은 행 -> 가장 낮은 열 위치 반환
해결방법 : bfs로 풀었다.
- 각 그래플러마다 떨어져 있는 빈칸의 값들을 최소 거리로 변경해준다.
- 그 빈칸 거리 중 가장 먼 거리를 찾아준다.
- 가장 먼 거리인 좌표 값들을 리스트에 추가한다.
- Comparable로 원하는 조건인 좌표값을 리턴받는다.
import java.util.*;
class Solution {
static int max;
static int[][] dp;
static Queue<Point> q = new LinkedList<>();
static ArrayList<Point> list = new ArrayList<>();
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static class Point implements Comparable<Point> {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
@Override
public int compareTo(Point o) {
if(this.y==o.y) return this.x - o.x;
return this.y - o.y;
}
}
public int[] solution(int N, String[][] board) {
int[] answer = new int[2];
dp = new int[board.length][board[0].length];
for(int y=0; y<board.length; y++) {
Arrays.fill(dp[y], Integer.MAX_VALUE);
for(int x=0; x<board[y].length; x++) {
if(board[y][x].equals("G")) {
dp[y][x] = 0;
q.offer(new Point(y, x));
}
}
}
while(!q.isEmpty()) {
Point cur = q.poll();
for(int i=0; i<4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if(ny<0 || nx<0 || ny>=board.length || nx>=board[0].length) continue;
if(dp[ny][nx] > dp[cur.y][cur.x]+1) {
dp[ny][nx] = dp[cur.y][cur.x]+1;
q.offer(new Point(ny, nx));
max = Math.max(max, dp[ny][nx]);
}
}
}
for(int y=0; y<dp.length; y++) {
for(int x=0; x<dp[y].length; x++) {
if(dp[y][x]==max) {
list.add(new Point(y, x));
}
}
}
Collections.sort(list);
answer[0] = list.get(0).y;
answer[1] = list.get(0).x;
return answer;
}
}