📙[Algo] 24.03.22 알고리즘

알고리즘 문제) BOJ 1946. 신입 사원

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

문제 요약

• 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
  • 즉, A의 성적이 다른 B의 성적에 비해 서류와 면접 모두 떨어지면 선발 X

시간 제한

• 2초

입력

• 테스트 케이스 개수 T
  • 1≤T≤20
• 각 테스트케이스의 첫째 줄에 지원자 수 N
  • 1≤N≤10만
• N개의 줄에 지원자의 서류, 면접 성적이 주어짐
  • 동석차 X

출력

• 선발할 수 있는 신입사원 최대 인원수 구하기

접근법

나랑 다른 지원자 모두를 비교했을 때 서류, 면접 석차가 모두 뒤에 있으면 안 됨

서류 점수 기준으로 오름차순 정렬하면

1 4

2 5

3 6

4 2

5 7

6 1

7 3

• 1등은 무조건 합격
• 2등은 1등이랑 면접 비교 ⇒ 탈락
• 3등은 1~2등이랑 면접 비교 ⇒ 탈락
• 4등은 1~3등이랑 면접 비교 ⇒ 제일 높으므로 합격
• 5등은 1~4등이랑 면접 비교 ⇒ 탈락
• 6등은 1~5등이랑 면접 비교 ⇒ 제일 높으므로 합격
• 7등은 1~6등이랑 면접 비교 ⇒ 탈락
• 즉 서류 기준 오름차순 정렬하고, 2등부터 자기 위에 있는 애들이랑 면접 등수 비교한다.
  • 이때 매번 1등부터 N등까지 비교하면 그러니까 가장 최소인 값을 매 케이스마다 갱신하고 그 최솟값이랑만 비교한다.

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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;

        int T = Integer.parseInt(br.readLine());

        int N, cnt, min;
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());

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

            Arrays.sort(arr, (o1, o2) -> {
                return o1[0] - o2[0];
            });

            cnt = 1; min = 1 << 30;
            for (int i = 1; i < N; i++) {
                min = Math.min(min, arr[i - 1][1]);

                if (min > arr[i][1]) cnt++;
            }

            sb.append(cnt + "\\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1417. 국회의원 선거

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

문제 요약

• N명의 후보가 존재
• 기호1번부터 N번을 찍으려는 사람의 수가 주어졌을 때, 최소 몇 명을 매수해야 다솜이가 당선되는 지 구하기(다솜이는 기호 1번)

시간 제한

• 2초

입력

• 후보의 수 N
  • N은 50이하 자연수
• 차례대로 기호 1번을 찍으려는 사람의 수, ~ N번을 찍으려는 사람의 수가 주어짐
  • 득표수는 10이하 자연수

출력

• 다솜이가 매수해야하는 사람의 최솟값?

접근법

• 매 순간 1등걸 끌어내린다!

코드

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

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

        /*
        * 매순간 1위인 애한테서 뺏기
        * */
        int cnt = 0, topIdx = 0, max = 0;

        while (true) {
            max = 0;
            for (int j = 0; j < N; j++) {
                if (max <= arr[j]) {
                    max = arr[j];
                    topIdx = j;
                }
            }

            if (topIdx != 0) {
                arr[0]++;
                arr[topIdx]--;
                cnt++;
            } else break;
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1931. 회의실 배정

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

문제 요약

• 회의 시간이 겹치지 않게 회의실을 사용할 수 있는 회의 최대 개수
  • 끝나는 동시에 다른 회의 시작 가능

시간 제한

• 2초

입력

• 회의 수 N
  • 1≤N≤10만
• N개의 줄에 회의시작, 회의 끝 시간이 주어짐
  • 시간은 2^31-1보다 작거나 같은 자연수 또는 0

출력

• 사용가능한 회의실 최대 개수

접근법

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

O

• 종료시작시간 기준 오름차순
  • 같다면 시작시간 기준 오름차순

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

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;

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

        // 끝나는 시간 기준 오름차순(같다면 시작시간 기준 오름차순)
        Arrays.sort(arr, (o1,o2)->{
            if (o1[1] == o2[1]) return o1[0] - o2[0];
            else return o1[1] - o2[1];});

        /*
        * 현재 회의 끝나는 시간이랑 다음 회의 시작 시간 비교
        * => 시작 가능하다면 해당 회의로 이동 하고 카운트
        * */
        int cnt = 1, curIdx = 0;
        for (int i = 1; i < N; i++) {
            if (arr[curIdx][1] <= arr[i][0]) {
                curIdx = i;
                cnt++;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2217. 로프

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

문제 요약

• N개의 로프가 주어짐
• k개의 로프를 사용하여 중량 w인 물체를 들어올릴 때, 각각 로프에는 고르게 w/k만큼 중량이 걸림
• 각 로프들에 대한 정보가 주어졌을 때, 해당 로프들을 이용하여 들어올릴 수 있는 최대 중량 구하기
  • 모든 로프 사용할 필요는 없음

시간 제한

• 2초

입력

• 정수 N
  • 10만 이하 자연수
• N개의 줄에 각 로프가 버틸 수 있는 최대 중량이 주어짐
  • 10000이하 자연수

출력

• 들어올릴 수 있는 최대 중량 출력

접근법

100 50 23 10 5

만약 a1,… aN의 로프를 고른다면

(a1+.. +aN) / N 만큼 중량이 분산된다.

결국 더해지는 애들 중 최소중량인 애가 얼마인지 중요..

N이 10만이기 때문에 for문은 하나만 가능 !

• 일단 내림차순 정렬
• 투포인터로 s→0, e→0부터 시작
  • 들을수 있는 중량의 최댓값을 계속 갱신하면서 e를 우측으로 한칸씩 이동
  • 문제 주의!! ⇒ 분산되기때문에 결국 가장 중량이 작은 친구의 무게가 중요하다. 즉 작은애의 무게 * 로프 개수만큼 들 수 있음!

코드

• 투포인터

import java.io.*;
import java.util.Arrays;
import java.util.Collections;

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

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

        **Arrays.sort(arr, Collections.reverseOrder());**

        int s = 0, e = 0, max = 0, kg = 0;
        while (e < N) {
            kg = arr[e] * (e - s + 1);
            if (max < kg) {
                max = kg;
            }
            e++;
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}