📙[Algo] 24.08.21 알고리즘

알고리즘 문제) BOJ 2374. 같은 수로 만들기

• 링크 : https://www.acmicpc.net/problem/17178

문제 요약

• n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다
• 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가
  • 이때, A[i]의 좌우로 인접한 같은 수의 그룹도 한번에 1씩 증가
• 이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다
• 소 회수로 Add연산을 사용하는 방법을 찾아라

시간 제한

• 1초

입력

• 첫째 줄에 정수 n
• 다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]
  • 든 입력은 1,000,000,000을 넘지 않는다

출력

• 첫째 줄에 최소의 Add연산 사용 회수를 출력
  • 값은 10^25를 넘지 않음

접근법

• 아래처럼 예시가 주어졌을 때
  • 1 1 1 5 2 2 1 6
  • 해당 숫자를 각각 건물의 높이라 생각해서 그림으로 나타내면 아래와 같다.
    

    

  • 이때, 모든 건물의 높이를 같게 하기 위해
    • 주변 건물보다 가장 낮은 건물 높이의 차만큼 탑을 쌓을 수 있다.
      

      

    • 즉, 낮은 건물의 높이는 주변의 큰 건물 높이에 맞춰 쌓아올리는ㄴ 과정을 반복하면서, 최종적으로 모든 건물의 높이를 같게 만들어야 한다.
    • 따라서 최소 연산 횟수는, 4 + 4 + 1로 9가 될 것이다.

• 위 로직을 코드로 구현한다면,
  • max는 지금까지 만난 값 중 가장 큰 값, prv는 이전에 만난 값을 의미한다.
  • 수열을 담은 배열 arr을 순차적으로 탐색하면서,
    • 현재 가리키는 값이 이전 값prv보다 작거나 같다면 두 값의 차이만큼 정답에 더해준다 ⇒ 주변의 더 큰 값으로 동일하게 맞추기
    • 현재 가리키는 값이 더 크다면, 지금까지 나왔던 최대값 max와 비교한다.
      • 이때, 현재 가리키는 값이 더 클 경우에만 max와의 차이만큼 정답에 더해준다. ⇒ 지금까지 쌓아올린 값들을 더 큰 값인 현재 값으로 맞추기
  • 또한, 매순간 max와 prv를 갱신한다.
• 시간복잡도 : O(N)
• 만약 스택을 사용하게 된다면,
  • 좌측에서 우측으로 탐색하면서, 작은 값 → 큰 값이 되는 구간만큼 차이를 더해주고, 마지막으로 탐색한 높이와 max값 비교해서 차이만큼 더해준다.
  • 스택에는 이전까지 탐색한 값을 담으면서, 스택의 상단값(이전 탐색한 값)보다 현재 가리키는 값이 더 큰 경우에만 차이만큼 정답에 더해준다.
  • 또한, 매순간 최대 값 max를 갱신
  • 이후, 최종적으로 스택에 남겨진 값(가장 마지막으로 탐색한 값) max값의 차이만큼 정답에 더해준다..

코드

• 스택 사용 X

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        long answer = 0;
        int max = arr[0];
        int prv = arr[0];
        for (int i = 1; i < N; i++) {
             if (prv >= arr[i]) {
                answer += prv - arr[i];
             } else {
                if (max < arr[i]) answer += arr[i] - max;
             }
            prv = arr[i];
            max = Math.max(max, arr[i]);
        }
        System.out.println(answer);
    }
}

• 스택 사용

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        long answer = 0;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {

            if (!stack.isEmpty()) {
                if (stack.peek() < arr[i]) answer += arr[i] - stack.peek();
                stack.pop();
            }

            max = Math.max(max, arr[i]);
            stack.push(arr[i]);
        }

        answer += max - stack.pop();

        System.out.println(answer);
    }
}

 

알고리즘 문제) BOJ 24492. Cow Frisbee 

• 링크 : https://www.acmicpc.net/problem/24492

문제 요약

• 소 N마리는 각각 높이를 가지고 있다
  • 이때, 높이는 1, …. N중 하나
• 만약 두 소 위치 i와 j가 있을 때, 그들 사이 모든 소의 높이가 min(h1,hj)보다 작으면 프리스비를 성공적으로 주고받을 수 있다
• 이때, 가능한 모든 쌍에 대해 그 거리를 게산해라
  • 위치 i와 j사이 거리는 j - i + 1이다

시간 제한

• 1초

입력

• 정수 N
  • N ≤ 30만
• 각 소들의 높이 h1, … , hn

출력

• 프리스비를 성공적으로 주고받을 수 있는 모든 소의 쌍에 대한 거리의 합을 출력

접근법

• N이 30만이므로 O(N)안에 마쳐야 한다
• 프리스비를 주고받을 수 있는 구간은, 두 소사이의 높이가 두 소 중 더 작은 소보다 모두 작아야한다.
  • 이를 완전탐색으로 모든 쌍들을 일일이 비교하면 N*N으로 시간초과가 뜬다. → 따라서 O(N)안에 탐색할 수 있도록 해야함
• 최적화를 위해 모노톤 스택을 사용해서 접근했다.
  • 왼쪽 → 오른쪽 탐색
    • 현재 가리키는 소보다 작거나 같은 소들은 스택에서 제거하면서, 거리를 합산했다. (즉, 스택에는 현재 소보다 큰 소들만 남게 되며, 단조 감소 형태가 된다.)
  • 오른쪽 → 왼쪽 탐색
    • 현재 가리키는 소보다 작은 소들은 스택에서 제거하면서, 거리를 합산했다. (스택에는 현재 소보다 크거나 같은 소들만 남게 되, 단조 감소 형태가 된다.)
• 시간복잡도 : O(2N) → O(N)

코드

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

public class Main {

    static class Cow {
        int h;
        int idx;

        Cow(int h, int idx) {
            this.h = h;
            this.idx = idx;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long answer= 0;

        // 좌측에서 우측으로 탐색
        // 이전 높이보다 크거나 같은 경우만 체크
        Stack<Cow> leftToRight = new Stack<>();
        for (int i = 1; i <= N; i++) {
            while (!leftToRight.isEmpty() && arr[i] >= leftToRight.peek().h) {
                answer += Math.abs(i - leftToRight.pop().idx) + 1;
            }
            leftToRight.push(new Cow(arr[i], i));
        }

        // 우측에서 좌측으로 탐색
        // 이전 높이보다 큰 경우만 체크
        Stack<Cow> rightToLeft = new Stack<>();
        for (int i = N; i >= 1; i--) {
            while (!rightToLeft.isEmpty() && arr[i] > rightToLeft.peek().h) {
                answer += Math.abs(i - rightToLeft.pop().idx) + 1;
            }
            rightToLeft.push(new Cow(arr[i], i));
        }

        System.out.println(answer);
    }
}

 

알고리즘 문제) BOJ 19598. 최소 회의실 개수

• 링크 : https://www.acmicpc.net/problem/19598

문제 요약

• N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션
  • 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다
  • 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다

시간 제한

• 2초

입력

• 배열의 크기 N(1 ≤ N ≤ 100,000)
• N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간
  • 시작 시간과 끝나는 시간은 2^31−1보다 작거나 같은 자연수 또는 0

출력

• 첫째 줄에 최소 회의실 개수를 출력

접근법

• 강의 시간을 담은 배열을 강의 시작시작을 기준으로 오름차순 정렬
• 강의 종료 시간을 담고, 오름차순 정렬되는 우선순위 큐 생성
• 이후, 배열을 순회하면서 우선순위큐가 비어있지 않은 경우, 가장 빨리 끝나는 강의 시간과 현재 강의 시작시간을 비교 → 강의실을 쓸 수 있다면 종료된 강의는 큐에서 제거하고, 현재 강의 종료시간 삽입
  • 비어있지 않거나, 쓸 수 있는 강의실이 없다면 강의실 개수 하나 늘리고, 큐에 현재 강의 종료시간 삽입

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int s, e;
        int[][] timeline = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            timeline[i][0] = s;
            timeline[i][1] = e;
        }

        Arrays.sort(timeline, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        int answer = 0;
        for (int i = 0; i < N; i++) {
            if (!pq.isEmpty() && pq.peek() <= timeline[i][0]) {
                pq.poll();
                pq.offer(timeline[i][1]);
            } else {
                pq.offer(timeline[i][1]);
                answer++;
            }
        }

        System.out.println(answer);
    }
}