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

비기너

문제

26042번: 식당 입구 대기 줄

# 큐

https://acmicpc.net/problem/26042

풀이

식당에서 줄을 설 때 줄을 서서 대기하는 학생의 수가 최대가 되었던 순간과 이때 가장 뒤에 있는 학생의 번호를 출력하는 문제이다.

줄을 서는 것은 FIFO이므로 큐를 이용해서 구현한다.

n개의 정보가 주어지는데 1번 정보는 줄을 서는 것이고 2번 정보는 빠져나가는 것이다.

1번 정보가 주어지면 해당 학생을 큐에 넣고 큐의 사이즈와 ans1을 비교해서 큐의 사이즈가 더 크거나 같다면 ans1을 갱신하고 ans2도 조건에 따라 갱신한다.

2번 정보가 주어지면 큐에서 poll한다.

코드

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());
		Queue<Integer> q = new LinkedList<>();
		int ans1 = 0, ans2 = 0;

		while (n-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			if (x == 1) {
				int y = Integer.parseInt(st.nextToken());
				q.add(y);
				if (ans1 < q.size()) {
					ans1 = q.size();
					ans2 = y;
				} else if (ans1 == q.size() && y < ans2)
					ans2 = y;
			} else
				q.poll();
		}

		bw.write(ans1 + " " + ans2);
		bw.flush();
		bw.close();
	}
}

미들러

문제

2212번: 센서

# 그리디

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

풀이

n개의 센서를 k개의 집중국으로 커버할 때 집중국의 수신 가능 영역의 길이의 합의 최솟값을 구하는 문제이다.

우선 k가 n보다 크거나 같다면 모든 센서의 위치에 집중국을 설치하면되므로 영역의 최솟값은 0이된다.

만약 k가 n - 1이라면 n - 2개의 센서의 위치에 집중국을 설치하고 가장 거리가 가까운 두 센서가 있는 구간을 1개의 집중극으로 커버해야 한다.

k가 n - 2라면 2개의 구간을 집중국으로 커버해야한다.

즉 n - k개의 구간을 집중국으로 커버해야하는 것이다.

따라서 센서의 위치를 정렬한 뒤 두 센서사이의 구간의 길이를 구한다.

이 구간의 길이를 정렬한 뒤 작은 것부터 n -k 개를 더한 것이 수식 가능 영역의 최솟값이 된다.

코드

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 k = Integer.parseInt(br.readLine());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(a);

		int[] d = new int[n - 1];
		for (int i = 0; i < n - 1; i++)
			d[i] = a[i + 1] - a[i];
		Arrays.sort(d);

		int ans = 0;
		for (int i = 0; i < n - k; i++)
			ans += d[i];

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

챌린저

문제

상담원 인원

# 완전탐색 # 우선순위 큐

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

프로그래머스

풀이

n명의 상담원을 k개의 상담 유형 별로 분배할 때 참가자들의 상담 대기시간이 최소가 되도록 하는 문제이다.

k가 5이하이고 n이 20이하이므로 유형 별로 상담원을 분배하는 모든 경우의 수에 대해 상담 요청을 처리하였을 때 대기시간을 각각 구하여 최솟값을 구해주면 된다.

a 배열에 유형별 상담원 수를 저장한다.

go 함수는 재귀를 통해 상담원 수를 분배하는 모든 경우를 찾는다.

각각의 경우에 대해 대기 시간을 구해야 하는데 k개의 상담 유형 별로 상담이 끝나는 시간의 최솟값을 알아야 하므로 k개의 우선순위 큐를 사용하여 최솟값을 효율적으로 구한다.

코드

import java.util.*;

class Solution {
    int ans = 1000000000;
    int[] a;
    
    void go(int idx, int cnt, int k, int n, int[][] reqs) {
        if(cnt == n - k) {
            int[] b = new int[k + 1];
            for (int i = 0; i < k; i++)
                b[i + 1] = a[i];
            int sum = 0;
            PriorityQueue<Integer>[] pqs = new PriorityQueue[k + 1];
            for (int i = 0; i <= k; i++)
                pqs[i] = new PriorityQueue<>();
            
            for (int[] i : reqs) {
                if (b[i[2]] == 0) {
                    if (pqs[i[2]].peek() <= i[0]) {
                        pqs[i[2]].poll();
                        pqs[i[2]].add(i[0] + i[1]);
                    }
                    else {
                        int tmp = pqs[i[2]].poll();
                        sum += tmp - i[0];
                        pqs[i[2]].add(tmp + i[1]);
                    }
                }
                else {
                    b[i[2]]--;
                    pqs[i[2]].add(i[0] + i[1]);
                }
            }
            
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = idx; i < k; i++) {
            a[i]++;
            go(i, cnt + 1, k, n, reqs);
            a[i]--;
        }
    }
    
    public int solution(int k, int n, int[][] reqs) {
        a = new int[k];
        Arrays.fill(a, 1);
        go(0, 0, k, n, reqs);
        
        return ans;
    }
}

보너스문제

비기너

문제

다리를 지나는 트럭

# 큐

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

프로그래머스

 

풀이

트럭이 다리를 건널 때 걸리는 시간을 구하는 문제이다.

while 문을 통해 주어진 조건을 만족하면서 트럭이 다리를 지나는 과정을 시뮬레이션한다.

while 문의 반복은 1초를 의미한다.

1초마다 진행되는 사항은 다음 세 가지이다.

다리위의 트럭이 1칸씩 움직이고 시간이 1 증가한다.

트럭이 다리위에 올라갈 수 있으면 다리위에 올린다. 이때 트럭이 다리에 진입한 시각을 큐에 저장한다.

다리위의 트럭이 다리를 다 건너면 큐에서 빼주고 총 무게에서 빠져나간 트럭의 무게를 뺀다.

마지막 트럭이 다리위에 올라가면 while 문을 종료하고 마지막 트럭이 지나간 시간만 정답에 더해주면 된다.

코드

import java.util.*;

class Solution {    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> q = new LinkedList<>();
        int ans = 0;
        int sum = 0;
        int i = 0;
        
        while (i < truck_weights.length) {
            ans++;
            if (!q.isEmpty() && ans == q.peek() + bridge_length) {
                sum -= truck_weights[i - q.size()];
                q.poll();
            }
            
            if (q.size() < bridge_length && sum + truck_weights[i] <= weight) {
                q.add(ans);
                sum += truck_weights[i++];
            }
        }
        
        ans += bridge_length;
        
        return ans;
    }
}

미들러

문제

단속카메라

# 그리디

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

프로그래머스

풀이

차량의 모든 이동 경로에 카메라가 있도록 하는 카메라의 최소 수를 구하는 문제이다.

카메라 설치에 최대한 이득을 보려면 구간 중에 차량이 나가는 지점에 카메라를 설치해야 한다.

따라서  routes 배열을 나가는 지점을 기준으로 오름차순으로 정렬을 한다.

배열을 순회하면서 구간에 카메라가 없으면 나가는 지점에 카메라를 설치한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (o1, o2) -> o1[0] - o2[0]);

        int ans = 1;
        int tmp = routes[0][1];
        for (int[] i : routes) {
            if (i[0] > tmp) {
                tmp = i[1];
                ans++;
            }
            else if (i[1] < tmp)
                tmp = i[1];
        }
        
        return ans;
    }
}

챌린저

문제

행렬과 연산

# 덱

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

프로그래머스

풀이

2차원 배열에서 rotate와 shiftRow 연산을 구현하고 이를 적용한 배열을 반환하는 문제이다.

단순히 rotate와 shiftRow를 구현하는 것은 어렵지 않지만 해당 문제의 조건에서 배열의 요소가 최대 100000개이므로 두 연산을 구현할 때 단순히 배열을 복사해서 구현하면 시간초과가 발생한다.

두 연산을 효율적으로 구현하기 위해 2차원 배열을 덱으로 저장한다.

코드에 구현하진 않았지만 shift 연산이나 rotate연산이 일정 횟수 반복되면 원래 배열과 동일하기 때문에 연속된 연산의 수를 카운팅해서 이를 처리하면 더 효율적인 코드가 될 것이다.

코드

import java.util.*;

class Solution {
    int r, c;
    ArrayDeque<Integer> c1, c2;
    ArrayDeque<ArrayDeque<Integer>> rs;
    
    void rotate() {
        if(c == 2) {
            c2.addFirst(c1.pollFirst());
            c1.addLast(c2.pollLast());
            return;
        }
        rs.peekFirst().addFirst(c1.pollFirst());
        c2.addFirst(rs.peekFirst().pollLast());
        rs.peekLast().addLast(c2.pollLast());
        c1.addLast(rs.peekLast().pollFirst());
    }
    
    void shiftRow() {
        rs.addFirst(rs.pollLast());
        c1.addFirst(c1.pollLast());
        c2.addFirst(c2.pollLast());
    }
    
    public int[][] solution(int[][] rc, String[] operations) {
        r = rc.length;
        c = rc[0].length;
        
        c1 = new ArrayDeque<>();
        c2 = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            c1.addLast(rc[i][0]);
            c2.addLast(rc[i][c - 1]);
        }
        
        rs = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            ArrayDeque<Integer> tmp = new ArrayDeque<>();
            for (int j = 1; j < c - 1; j++)
                tmp.addLast(rc[i][j]);
            rs.addLast(tmp);
        }
        
        for (String s : operations) {
            if (s.equals("Rotate"))
                rotate();
            else
                shiftRow();
        }
        
        int[][] ans = new int[r][c];
        for (int i = 0; i < r; i++) {
            ans[i][0] = c1.pollFirst();
            ans[i][c - 1] = c2.pollFirst();
        }
        
        int idx = 0;
        for(ArrayDeque<Integer> i : rs) {
            for(int j = 1; j < c - 1; j++)
                ans[idx][j] = i.pollFirst();
            idx++;
        }
        
        return ans;
    }
}