📙[Algo] 24.08.19 알고리즘

알고리즘 문제) BOJ 17299. 오등큰수

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

문제 요약

• 크기가 N인 수열 A1, …, AN이 존재
• 수열의 각 원소 Ai에 대해 오등큰수 NGF(i)를 구하고자 한다
• 오등큰수는
  • Ai가 수열에서 등장한 횟수를 F(Ai)라 할 때
  • Ai의 오등큰수는 Ai보다 오른쪽에 있으면서, 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중 가장 왼쪽에 있는 수를 의미
    • 없다면 -1

시간 제한

• 1초

입력

• 수열 크기 N
  • 1 ≤ N ≤ 100만
• 수열의 원소 A1, … , An이 주어진다
  • 1 ≤ Ai ≤ 100만

출력

• 총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력

접근법

1 1 2 3 4 2 1

• 등장 횟수 : 3 3 2 1 1 2 3 → 카운팅 배열로 개수 기록
• 오등큰수
  • 2중 for문 완전탐색 접근 시 : 100만 * 100만으로 시간 초과
    • for문 하나로 오등큰수 구할 숫자 선택 + 내부 for문으로 나머지 수열을 순회하면서 현재 F(Ai)보다 큰 수 선택
  • 자료구조 스택 사용
    • 수열을 앞에서부터 순회하면서
    • 스택이 비어있을 경우 → 현재 가리키는 수열의 인덱스(i)를 스택에 삽입
    • 스택에 원소가 존재할 경우
      • 현재 가리키는 수열 원소의 등장 횟수(countion[arr[i]])와 스택의 상단에 있는 원소의 등장 횟수(counting[arr[statck.peek()]]) 비교
        • 현재 가리키는 수열 원소의 등장 횟수가 스택 상단에 있는 원소의 등장 횟수보다 크다면 해당 원소의 오등큰수는 현재 가리키는 수열 원소가 된다. ⇒ 이 조건을 만족할 때까지 스택의 원소를 pop하면서 정답 배열 arr에 오등큰수를 기록
      • 이후, 현재 가리키는 수열의 인덱스(i)를 스택에 삽입
    • 최종적으로 스택에는 오등큰수가 존재하지 않는 원소만 남게되므로, 남은 원소들을 pop하면서 정답 배열에 -1저장
  • 스택에 원소는 딱 한번만 push되고, pop되기 때문에 전체 시간복잡도는 O(N)으로 최적화 가능하다
    • 즉, 각 원소마다 stack을 while문에서 순회하는 연산 횟수를 합치면 N개가 된다는 뜻..
  • 왜 큐가아닌 스택을 사용한 것일까?
    • 오등큰수는 현재 원소 Ai의 오른쪽에 있는 수들의 등장 횟수가 더 큰 수를 찾아야 한다. 따라서 스택을 사용하면, 가장 최근에 추가된 원소들을 우선적으로 Ai와 비교할 수 있다.
      • 큐를 사용하게되면 FIFO구조로 가장 오래된 원소를 우선으로 비교하게 되므로, 최신 원소들은 Ai와 비교할 기회를 잃게 된다.

코드

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[] counting = new int[1_000_010];
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            counting[arr[i]]++;
        }

        int[] ans = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && counting[arr[i]] > counting[arr[stack.peek()]]) {
                ans[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(ans[i]).append(" ");
        }

        System.out.println(sb);

    }
}

 

알고리즘 문제) BOJ 1374. 강의실

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

문제 요약

• N개의 강의가 있고, 각 강의의 시작시간과 끝나는 시간이 주어진다.
• 이때, 한 강의실에서는 오직 한 강의만 진행할 수 있으며, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없을 때, 필요한 최소 강의실 수를 구하라

시간 제한

• 2초

입력

• 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)
• 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미
  • 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다
  • 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다

출력

• 첫째 줄에 필요한 최소 강의실 개수를 출력

접근법

• 우선 입력으로부터 강의별로 시작시간과 끝시간을 기록 후, 해당 배열을 시작 시간 기준 오름차순 정렬 했다.
  • 시작 시간이 빠른 강의부터 순차적으로 탐색하기 위해 정렬
• 이후, 우선순위큐를 사용해서, 진행중인 강의 중 가장 빨리 끝나는 강의를 기록하고자 했다.
  • 따라서, 해당 우선순위큐에는 강의의 종료시간을 담게 되며, 원소의 오름차순 정렬이 되도록 삽입했다.
• 가장 먼저 시작하는 강의는 무조건 강의실이 필요하므로, 강의실 갯수 변수 cnt + 1하고, 우선순위 큐에 해당 강의의 종료 시간을 삽입했다.
  • 이후, 2번째로 시작하는 강의부터 순회하면서, 우선순위 큐에서 가장 빨리 끝나는 강의의 종료 시간과 비교했을 때, 현재 강의 시작 시간이 더 작다면, 강의실이 추가로 필요하므로 cnt + 1하고, 우선순위큐에 현재 강의 종료 시간을 삽입했다.
  • 만약, 시작시간보다 빨리 끝나거나 같은 시간에 끝나는 강의가 존재하면, 해당 강의는 우선순위큐에서 제거하고, 우선순위큐에 현재 강의 종료 시간을 삽입했다.
• 즉, 우선순위 큐를 사용하여, 현재 진행중인 강의를 큐에 담으면서, 가장 빨리 끝나는 강의의 종료시간과 다음에 시작할 강의의 시작시간을 비교했다.

코드

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 n, s, e;
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()) - 1;
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            arr[n][0] = s;
            arr[n][1] = e;
        }

        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0]) return o1[1] - o2[1];
            else 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 cnt = 1;
        pq.offer(arr[0][1]);
        for (int i = 1; i < N; i++) {
            if (!pq.isEmpty()) {
                if (arr[i][0] < pq.peek()) {
                    cnt++;
                } else {
                    pq.poll();
                }
            }
            pq.offer(arr[i][1]);
        }

        System.out.println(cnt);
    }
}