📙[Algo] 24.08.30 알고리즘

알고리즘 문제) BOJ 3015. 오아시스 재결합

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

문제 요약

• N명이 한 줄로 서서 기다리고 있다
• 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다
• 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성

시간 제한

• 1초

입력

• 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
• 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다
  • 모두 2^31보다 작다
• 사람들이 서 있는 순서대로 입력이 주어진다.

출력

• 서로 볼 수 있는 쌍의 수를 출력한다.

접근법

• N이 50만 까지 가능하므로 O(N)안에 연산을 마쳐야 한다.
• 두 건물이 서로 볼 수 있으려면, 두 건물 사이에 min(건물1 높이, 건물2높이)보다 큰 건물이 있으면 안된다.
• 즉, 이전 건물에 현재 건물보다 큰 건물이 있다면 해당 건물 기준으로 앞에 있는 건물들은 전부 볼 수 없다.
  

  

• 이 점을 고려해본다면, 빌딩을 N번 순회하면서
  • 스택에는 이전 빌딩 정보를 담아둔다.
  • 이때, 스택에서 peek한 빌딩의 높이가 현재 빌딩보다 작다면 해당 빌딩들은 모두 pop한다. ⇒ 현재 건물 다음 건물들은 이 건물을 볼 수 없기 때문에 비교할 필요가 없다.
  • 여기서 주의할 점은 같을 경우이다.
    • 두 건물 사이에 존재하는 건물들이 두 건물의 높이와 같아도 볼 수 있기때문에, 같은 높이를 갖는 건물 개수를 따로 기록해 둬야 한다.
    • 따라서, 높이와 같은 건물 개수를 저장하는 객체를 하나 생성했다.
    • 만약, stack에서 peek한 건물의 높이가 현재 건물과 같다면, peek한 건물의 같은 건물 개수(sameCnt)를 누적해서 현재 건물에 더해주고, 또한 정답 변수를 카운트 할 때도 sameCnt만큼 더해줘야한다. ⇒ 따라서 따로 같은 건물 개수를 저장할 cnt변수를 추가했다.

• 정리하자면, 스택의 원소는 내림차순 형태가 유지되도록 해준다(LIFO시 오름차순 형태)
  • 스택에서 peek한 건물의 높이가
    • 현재 건물보다 큰 건물이라면
      • 정답 변수 + 1
    • 현재 건물보다 작은 건물이라면
      • 정답 변수 + 이전 건물의 sameCnt
      • 이전 건물 pop
    • 현재 건물과 같은 건물이라면
      • cnt(현재 건물과 높이가 같은 이전 건물 개수) + 이전 건물의 sameCnt
      • 정답 변수 + 이전 건물의 sameCnt
      • 이전 건물 pop
  • 마지막으로 stack에는 현재 건물 객체를 push한다.

코드

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

public class Main {

    static class Node {
        int height;
        long sameCnt;

        Node(int height, long sameCnt) {
            this.height = height;
            this.sameCnt = sameCnt;
        }
    }

    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());
        }

        // 내림차순 형태로 유지(LIFO시 오름차순 형태로 출력)
        Stack<Node> stack = new Stack<>();
        // 동일한 거 담을 임시 stack
        Stack<Integer> tmp = new Stack<>();
        // 정답변수
        long ans = 0, cnt;
        for (int i = 0; i < N; i++) {
            cnt = 1;
            if (!stack.isEmpty()) {
                // 동일한 높이를 만나 거나 낮은 높이를 만난 경우
                while (!stack.isEmpty() && (stack.peek().height <= arr[i])) {
                    // 같은 높이를 만났다면, 같은 높이 만큼 cnt에 더해주기
                    if (stack.peek().height == arr[i]) cnt += stack.peek().sameCnt;
                    // 이전에 동일한 크기만큼 정답 변수에 더해주기
                    ans += stack.peek().sameCnt;
                    stack.pop();
                }

                // 더 높은 높이를 만난 경우
                if (!stack.isEmpty() && stack.peek().height > arr[i]) {
                    ans++;
                }
            }

            stack.push(new Node(arr[i], cnt));
        }

        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 1027. 고층 건물

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

문제 요약

• N개의 빌딩이 존재
• 빌딩 A에서 다른 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩이 지나거나 접하면 안 된다.
• 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 그때 보이는 빌딩의 수를 출력해라

시간 제한

• 2초

입력

• 빌딩의 수 N
  • 1 ≤ N ≤ 50
• 각 빌딩의 높이가 N개 주어진다.
  • 1 ≤ 높이 ≤ 10억

출력

• 정답 출력

접근법

• 두 빌딩이 서로 보이기 위해서, 두 빌딩 사이에 지붕을 잇는 선분에 겹치거나 지나면 안되므로, 두 빌딩을 이어주는 직선 그래프를 구했다.
  • 기울기와 절편을 구한 뒤, 각 빌딩의 높이 좌표(i, arr[i])의 x좌표를 해당 그래프에 대입했을 때 결과값이 arr[i]보다 큰 경우만 있는 경우 서로 빌딩이 보인다 판단해서 카운트 + 1 했다.
• 이때 N이 50까지이므로 O(N^3)까지 가능하므로 완전탐색으로 진행했다.

코드

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

        int ansCnt = 0, cnt, x1, x2, y1, y2, x3, y3;
        double a, b;
        boolean flag;
        for (int i = 1; i <= N; i++) {
            x1 = i;
            y1 = arr[i];
            cnt = 0;

            for (int j = 1; j <= N; j++) {
                if (i == j) continue;

                flag = true;
                x2 = j;
                y2 = arr[j];
                // 기울기
                a = (double) (y1 - y2) / (x1 - x2);
                // 절편
                b = -a * x1 + y1;

                for (int k = Math.min(i, j) + 1; k < Math.max(i, j); k++) {
                    x3 = k;
                    y3 = arr[k];
                    if (a*x3 + b <= y3) flag = false;
                }

                if (flag) cnt++;
            }

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

        System.out.println(ansCnt);
    }
}