99클럽 코테 스터디 25일차 TIL

비기너

문제

더 맵게

# 우선순위 큐

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

풀이

음식의 스코빌 지수가 주어졌을 때 가장 맵지 않은 두 음식을 섞는 시행을 여러 번 반복하여 스코빌 지수를 k 이상 되도록 만들 때 섞는 최소 횟수를 구하는 문제이다.

매 시행마다 스코빌 지수가 가장 작은 요소를 뽑아내야 하므로 우선순위 큐로 최소힙을 구현하여 음식들을 큐에 넣는다.

매 시행마다 우선순위 큐에서 두 음식을 꺼내서 스코빌 지수를 합한 뒤 다시 우선순위 큐에 넣는다.

스코빌 지수가  k 이상이라면 정답을 리턴하고 우선순위 큐가 비었다면 k인 음식을 만들지 못한 것이므로 -1을 리턴한다. 

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i : scoville)
            pq.add(i);
        
        while (true) {
            int tmp1 = pq.poll();
            if (tmp1 >= K)
                break;
            if (pq.isEmpty())
                return -1;
            int tmp2 = pq.poll();
            pq.add(tmp1 + tmp2 * 2);
            ans++;
        }
        return ans;     
    }
}

미들러

문제

2116번: 주사위 쌓기

# 완전탐색

https://www.acmicpc.net/problem/2116

풀이

n개의 주사위를 쌓을 때 옆면의 숫자의 합의 최댓값을 구하는 문제이다.

주사위를 쌓는 모든 방법에 대해 옆면의 합의 최댓값을 구하고 그 중 최댓값을 출력한다.

주사위를 쌓을 때 아래 주사위의 윗면과 위 주사위의 아랫면이 같아야 하므로 첫번째 주사위의 윗면에 따라 주사위를 쌓는 방법이 정해진다.

주사위의 윗면과 아랫면을 제외한 4개의 옆면중의 최대인 수가 다 같은 면에 오도록 주사위를 쌓으면 최대가 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int a[][] = new int[n][6];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 6; j++)
				a[i][j] = Integer.parseInt(st.nextToken());
		}

		int ans = 0;
		int[] b = { 5, 3, 4, 1, 2, 0 };
		for (int i = 0; i < 6; i++) {
			int sum = 0;
			int tmp = a[0][b[i]];
			for (int j = 0; j < 6; j++) {
				if (j != i && j != b[i])
					sum = Math.max(sum, a[0][j]);
			}

			for (int j = 1; j < n; j++) {
				for (int k = 0; k < 6; k++) {
					if (tmp == a[j][k]) {
						tmp = a[j][b[k]];
						int mx = 0;
						for (int l = 0; l < 6; l++) {
							if (l != k && l != b[k])
								mx = Math.max(mx, a[j][l]);
						}
						sum += mx;
						break;
					}
				}
			}
			ans = Math.max(ans, sum);
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

2169번: 로봇 조종하기

# 동적계획법

https://www.acmicpc.net/problem/2169

풀이

로봇이 맵을 이동하면서 탐사를 진행할 때 탐사한 지역들의 가치의 합의 최댓값을 구하는 문제이다.

처음에는 dfs나 bfs를 생각했으나 맵이 너무 커서 완전탐색을 진행하면 시간초과가 발생한다.

로봇의 이동 방향이 좌우 아래 뿐이므로 (a, b) 지점의 가치의 합은 (a-1, b), (a, b-1), (a, b+1) 지점의 가치의 합에 의해 결정된다.

따라서 dp를 이용해서 전 단계의 가치의 합 최댓값을 통해 가치의 합을 구한다.

좌로 갔다가 우로 가는 경우는 발생하면 안되기 때문에 좌로 이동하는 경우의 값과 우로 이동하는 경우의 값을 각기 다른 배열에 저장하고 이 둘을 비교한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] a = new int[n][m];
		int[][] d = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++)
				a[i][j] = Integer.parseInt(st.nextToken());
		}

		d[0][0] = a[0][0];
		for (int i = 1; i < m; i++)
			d[0][i] = d[0][i - 1] + a[0][i];

		for (int i = 1; i < n; i++) {
			int[][] tmp = new int[2][m];
			tmp[0][0] = d[i - 1][0] + a[i][0];
			for (int j = 1; j < m; j++)
				tmp[0][j] = Math.max(tmp[0][j - 1], d[i - 1][j]) + a[i][j];

			tmp[1][m - 1] = d[i - 1][m - 1] + a[i][m - 1];
			for (int j = m - 2; j >= 0; j--)
				tmp[1][j] = Math.max(tmp[1][j + 1], d[i - 1][j]) + a[i][j];

			for (int j = 0; j < m; j++)
				d[i][j] = Math.max(tmp[0][j], tmp[1][j]);
		}

		bw.write(d[n - 1][m - 1] + "");
		bw.flush();
		bw.close();
	}
}

보너스문제

비기너

문제

이중우선순위큐

# 우선순위 큐 # 맵

https://school.programmers.co.kr/learn/courses/30/lessons/42628

풀이

최댓값과 최솟값을 빠르게 찾을 수 있는 이중 우선순위 큐를 구현하는 문제이다.

맥스힙, 민힙을 구현한 우선순위 큐 두 개를 이용하여 이중 우선순위 큐를 구현한다.

우선순위 큐에 삽입된 요소를 해시맵으로 관리하여 두 우선순위 큐 중 어느 한 쪽에서 삭제되면 맵에서 개수를 하나 줄인다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> mnh = new PriorityQueue<>();
        PriorityQueue<Integer> mxh = new PriorityQueue<>(Collections.reverseOrder());
        HashMap<Integer, Integer> mp = new HashMap<>();
        
        for (String s : operations) {
            char c = s.charAt(0);
            int n = Integer.parseInt(s.substring(2));
            if (c == 'I') {
                mnh.add(n);
                mxh.add(n);
                if (mp.containsKey(n))
                    mp.put(n, mp.get(n) + 1);
                else
                    mp.put(n, 1);
            }
            else if (n == 1) {
                while (!mxh.isEmpty() && mp.get(mxh.peek()) == 0) 
                    mxh.poll();
                if (!mxh.isEmpty()) {
                    int x = mxh.poll();
                    mp.put(x, mp.get(x) - 1);        
                }
            }
            else {
                while (!mnh.isEmpty() && mp.get(mnh.peek()) == 0) 
                    mnh.poll();
                if (!mnh.isEmpty()) {
                    int x = mnh.poll();
                    mp.put(x, mp.get(x) - 1);
                }
            }
        }
        
        int[] ans = new int[2];
        while (!mxh.isEmpty() && mp.get(mxh.peek()) == 0) 
            mxh.poll();
        if (!mxh.isEmpty()) 
            ans[0] = mxh.poll();
                
        while (!mnh.isEmpty() && mp.get(mnh.peek()) == 0) 
            mnh.poll();
        if (!mnh.isEmpty()) 
            ans[1] = mnh.poll();
        
        return ans;
    }
}