[2월 1주차] 택배 배달과 수거하기 2023 KAKAO BLIND RECRUITMENT

[eunbc]

필수 문제

택배 배달과 수거하기

코드 💻

자율 문제

문제1

코드 💻

문제2

코드 💻

[KarmaPol]

필수 문제

택배 배달과 수거하기

코드 💻

자율 문제

문제1

코드 💻

문제2

코드 💻

class Solution {
    static int[][] directions = new int[][] {{0,1}, {1,0}, {-1,0}, {0,-1}};
    
    public int solution(String[][] board, int h, int w) {
        int answer = 0;
        
        for(int i = 0 ; i < 4; i++){
            String current = board[h][w];
            int nexty = h + directions[i][0];
            int nextx = w + directions[i][1];
            
            if(nexty < 0 || nexty >= board.length || nextx < 0 || nextx >= board[0].length) continue;
            
            if(board[nexty][nextx].equals(current))
                answer++;
        }
        
        return answer;
    }
}

[eunbc]

필수 문제

택배 배달과 수거하기

코드 💻

class Solution {
    
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        int d = 0;
        int p = 0;
        for(int i=n-1; i>=0; i--) {
            d += deliveries[i];
            p += pickups[i];
            
            while(d>0 || p>0) {
                d -= cap;
                p -= cap;
                answer += 2*(i+1);
            }
        }
        
        return answer;
    }
}

• 그리디

자율 문제

백준 14501 퇴사

코드 💻

백트래킹

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int N,ans;
    static int[] T = new int[15];
    static int[] P = new int[15];
    static int[] dp = new int[16];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }    
        dfs(0,0);  
        System.out.println(ans);
    }

    static void dfs(int cur, int sum) {
        if(cur==N) {
            ans = Math.max(ans,sum);
            return;
        }
        if(cur+T[cur]<=N) {
            dfs(cur+T[cur], sum + P[cur]);
        }
        dfs(cur+1, sum);
    }

}

DP

mport java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int N,ans;
    static int[] T = new int[15];
    static int[] P = new int[15];
    static int[] dp = new int[16];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }    
        
        for(int i=N-1; i>=0; i--) {
            // dp[i]
            if(i+T[i]<=N) {
                dp[i] = Math.max(dp[i+1], dp[i+T[i]] + P[i]);
            } else {
                dp[i] = dp[i+1];
            }
        }

        System.out.println(dp[0]);
    }

}

• 백트래킹 / DP

백준 15988 1,2,3 더하기 3

코드 💻

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int T, n;
    static long[] dp = new long [1000001];
    static StringBuilder sb = new StringBuilder();
    static int div = 1000000009;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<dp.length; i++) {
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%div;
        }

        while(T-->0) {
            n = sc.nextInt();
            sb.append(dp[n]);
            sb.append('\n');
        }

        System.out.println(sb.toString());
    }

}

• DP
• int 오버플로우에 유의

[park0jae]

필수 문제

택배 배달과 수거하기

코드 💻

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        int deliveryCount = 0;
        int pickupCount = 0;
        
        for(int i=n-1; i>=0; i--) {
            
            if(deliveries[i] != 0 || pickups[i] != 0) {
                int count = 0;
                
                while(deliveryCount < deliveries[i] || pickupCount < pickups[i]) {
                    count++;
                    deliveryCount += cap;
                    pickupCount += cap ;
                }
                
                answer += (i + 1) * 2 * count;
                
                deliveryCount -= deliveries[i];
                pickupCount -= pickups[i];
            }
        }
        
        return answer;
    }
}

• 문제가 잘 안풀려서, 구글링해보고 참고해서 풀었습니당

자율 문제

계란으로 계란치기

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static List<Egg> eggs = new ArrayList<>();
    static int count = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        
        // 계란: 내구도 & 무게로 이루어짐 => 내구도는 상대 계란의 무게만큼 깎이고 0이되면 깨진다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int hp = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            eggs.add(new Egg(hp, weight)); 
        }
        breakEggs(0, 0);
        System.out.println(count);
    }

    static void breakEggs(int depth, int breakEggsCount) {
        if(depth == N) {
            count = Math.max(count, breakEggsCount);
            return ;
        }

        if(eggs.get(depth).hp <= 0 || breakEggsCount == N-1) {
            breakEggs(depth + 1, breakEggsCount);
            return ;
        }

        int tmp = breakEggsCount;
        for(int i=0; i<N; i++) {
            // 두개 부딪혔을 때 깨지지 않거나, 깨지는 경우
            if(i == depth || eggs.get(i).hp <= 0) continue;
            eggs.get(depth).hp -= eggs.get(i).weight;
            eggs.get(i).hp -= eggs.get(depth).weight;
            if(eggs.get(depth).hp <= 0) breakEggsCount++;
            if(eggs.get(i).hp <= 0) breakEggsCount++;
            breakEggs(depth + 1, breakEggsCount);
            eggs.get(depth).hp += eggs.get(i).weight;
            eggs.get(i).hp += eggs.get(depth).weight;
            breakEggsCount = tmp;
        }
    }

    static class Egg {
        int hp;
        int weight;
        
        public Egg(int hp, int weight) {
            this.hp = hp;
            this.weight = weight;
        }
    }
}

• 백트래킹

검문

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        
        // 근처에 보이는 숫자 N개를 종이에 적음 
        // 그 다음 종이에 적은 수를 M으로 나눔 , 나머지가 모두 같게 되는 M을 찾으려고 함 

        // N 개의 수가 주어졌을때 가능한 M을 모두 찾는 프로그램을 짜라.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuffer sb = new StringBuffer();
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int num = arr[1] - arr[0];

        for(int i=1; i<n; i++){
            num = gcd(num , arr[i] - arr[i-1]);
        }

        for(int i=2; i<=num; i++){
            if(num % i == 0){
                sb.append(i).append(" ");
            }
        }
        System.out.println(sb);
    }

    public static int gcd(int a, int b){
        if(b == 0) return a;
        else return gcd(b , a%b);
    }
}

• 유클리드 호제법

[byulcode]

필수 문제

택배 배달과 수거하기

코드 💻

class Solution {
	public long solution(int cap, int n, int[] deliveries, int[] pickups) {
		int d = 0;
		int p = 0;
		long ans = 0;

		for (int i = n - 1; i >= 0; i--) {
			d -= deliveries[i];
			p -= pickups[i];
			int cnt = 0;

			while (d < 0 || p < 0) {
				d += cap;
				p += cap;
				cnt++;
			}
			ans += (i + 1) * 2L * cnt;
		}
		return ans;
	}
}

• greedy

자율 문제

석유 시추

코드 💻

import java.util.*;

class Solution {
	int[][] land, oil;
	int n, m, ans;
	boolean[][] visited;
	int[] dx = {0, 0, 1, -1};
	int[] dy = {1, -1, 0, 0};

	public int solution(int[][] land) {
		this.land = land;
		n = land.length;
		m = land[0].length;
		visited = new boolean[n][m];
		oil = new int[n][m];
		Map<Integer, Integer> oilCounts = new HashMap<>();

		// 각 구간당 크기 저장
		int oilLevel = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (land[i][j] == 1 && !visited[i][j]) {
					int sum = bfs(i, j, oilLevel);
					oilCounts.put(oilLevel, sum);
					oilLevel++;
				}
			}
		}

		for (int j = 0; j < m; j++) {
			Set<Integer> oilSet = new HashSet<>();
			int sum = 0;
			for (int i = 0; i < n; i++) {
				if (oil[i][j]>0) {
					oilSet.add(oil[i][j]);
				}
			}
			for (int key : oilSet) {
				sum += oilCounts.get(key);
			}
			ans = Math.max(ans, sum);
		}
		return ans;
	}

	int bfs(int x, int y, int oilLevel) {
		int cnt = 1;
		Queue<int[]> queue = new LinkedList<>();
		visited[x][y] = true;
		queue.offer(new int[] {x, y});
		oil[x][y] = oilLevel;

		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			x = p[0];
			y = p[1];
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < n && nx >= 0 && ny >= 0 && ny < m && !visited[nx][ny] && land[nx][ny] == 1) {
					queue.offer(new int[] {nx, ny});
					cnt++;
					visited[nx][ny] = true;
					oil[nx][ny] = oilLevel;
				}
			}
		}
		return cnt;
	}
}

• bfs

창고 다각형

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int n, start, end, sum, maxHeightIdx, maxHeight;
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[1001];
		start = Integer.MAX_VALUE;

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());
			arr[l] = h;
			start = Math.min(start, l);
			end = Math.max(end, l);
			if (maxHeight < h) {
				maxHeight = h;
				maxHeightIdx = l;
			}
		}

		int temp = arr[start];
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		for (int i = start + 1; i <= maxHeightIdx; i++) {

			if (temp > arr[i]) {
				stack.push(i);
			} else {
				while (!stack.isEmpty()) {
					int x = stack.pop();
					arr[x] = temp;
				}
				temp = arr[i];
			}
		}

		temp = arr[end];
		stack.push(end);
		for (int i = end - 1; i >= maxHeightIdx; i--) {
			if (temp > arr[i]) {
				stack.push(i);
			} else {
				while (!stack.isEmpty()) {
					int x = stack.pop();
					arr[x] = temp;
				}
				temp = arr[i];
			}
		}

		for (int i = start; i <= end; i++) {
			sum += arr[i];
		}
		System.out.println(sum);
	}
}

• stack

[annahxxl]

필수 문제

택배 배달과 수거하기

코드 💻

class Solution {
	public long solution(int cap, int n, int[] deliveries, int[] pickups) {
		long answer = 0;
		int d = 0;
		int p = 0;

		for (int i = n - 1; i >= 0; i--) {
			d += deliveries[i];
			p += pickups[i];

			while (d > 0 || p > 0) {
				d -= cap;
				p -= cap;
				answer += (i + 1) * 2;
			}
		}

		return answer;
	}
}

자율 문제

가장 많이 사용된 회의실

코드 💻

import java.util.*;

class Solution {
    public int solution(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        TreeSet<Integer> rooms = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            rooms.add(i);
        }

        Queue<int[]> uses = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int[] useCnts = new int[n];

        for (int[] meeting : meetings) {
            while (!uses.isEmpty() && uses.peek()[0] <= meeting[0]) {
                rooms.add(uses.poll()[1]);
            }

            if (rooms.isEmpty()) {
                int[] use = uses.poll();
                useCnts[use[1]]++;
                uses.add(new int[]{use[0] + (meeting[1] - meeting[0]), use[1]});
            } else {
                int room = rooms.pollFirst();
                useCnts[room]++;
                uses.add(new int[]{meeting[1], room});
            }
        }

        int answer = 0;
        int maxIdx = 0;

        for (int i = 0; i < n; i++) {
            if (useCnts[i] > maxIdx) {
                maxIdx = useCnts[i];
                answer = i;
            }
        }

        return answer;
    }
}

최소 회의실 개수

코드 💻

import java.util.*;

class Solution {

    public int solution(int[][] meetings) {

        List<int[]> list = new ArrayList<>();

        for (int meeting[] : meetings) {
            list.add(new int[]{meeting[0], 1}); // 시작 시간, 시작 여부
            list.add(new int[]{meeting[1], 0}); // 종료 시간, 시작 여부
        }

        Collections.sort(list, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int answer = 0;
        int cnt = 0;

        for (int[] meeting : list) {
            if (meeting[1] == 1) {
                cnt++;
            } else {
                cnt--;
            }

            answer = Math.max(answer, cnt);
        }

        return answer;
    }
}

[kimday0326]

필수 문제

택배 배달과 수거하기

코드 💻

자율 문제

구간 합 구하기 4

코드 💻

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] arr = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());}
		
    StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int startIdx = Integer.parseInt(st.nextToken());
			int endIdx = Integer.parseInt(st.nextToken());
		
			int sum = arr[endIdx] - arr[startIdx-1];
			sb.append(sum);
			sb.append("\n");
		}
        System.out.println(sb);
	}

}

RGB거리

코드 💻

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n, i, j;
		int[][] dp, cost;
		
		n = Integer.parseInt(br.readLine());
		cost = new int[n][3];
		for (i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			cost[i][0] = Integer.parseInt(st.nextToken());
			cost[i][1] = Integer.parseInt(st.nextToken());
			cost[i][2] = Integer.parseInt(st.nextToken());
		}
		dp = new int[n][3];
		dp[0] = cost[0];
		for (i = 1; i < n; i++) {
			for (j = 0; j < 3; j++) {
				dp[i][j] = Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + cost[i][j];
			}
		}
		System.out.print(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
	}
}