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

비기너

문제

2075번: N번째 큰 수

# 우선순위 큐

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

풀이

우선순위 큐를 사용해서 max heap을 구현하고 주어진 수를 모두 담은 뒤 n번째로 나온 수를 출력하면 된다.

코드

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());
        
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++)
				pq.add(Integer.parseInt(st.nextToken()));
		}

		for (int i = 0; i < n - 1; i++)
			pq.poll();

		bw.write(pq.peek() + "");
		bw.flush();
		bw.close();
	}
}

미들러

문제

모의고사

# 완전탐색

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

프로그래머스

풀이

각 수포자가 찍는 방식을 배열에 담아 answers 배열을 순회하며 각 수포자가 맞은 문제의 개수를 센다.

문제를 가장 많이 맞힌 사람의 번호를 배열에 담아 리턴한다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[][] a = { { 1, 2, 3, 4, 5 }, 
                      { 2, 1, 2, 3, 2, 4, 2, 5 }, 
                      { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 } 
                    };

        int[] cnt = new int[3];
        for (int i = 0; i < 3; i++) {
            int idx = 0;
            for (int j : answers) {
                if (idx == a[i].length)
                    idx = 0;
                if (j == a[i][idx++])
                    cnt[i]++;
            }
        }
        
        ArrayList<Integer> al = new ArrayList<>();
        int mx = 0;
        for (int i : cnt)
            mx = Math.max(i, mx);
        for (int i = 0; i < 3; i++) {
            if (cnt[i] == mx)
                al.add(i + 1);
        }
        
        int idx = 0;
        int[] ans = new int[al.size()];
        for (int i : al)
            ans[idx++] = i;
        return ans;
    }
}

챌린저

문제

1083번: 소트

# 그리디

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

풀이

배열을 정렬할 때 s번 교환해서 가장 사전순으로 뒤서는 배열을 만드는 문제이다.

배열의 현재 위치에서 s이내의 범위에서 가장 큰 요소를 찾아 해당 위치로 오게 교환해 주면 된다.

현재 위치가 i이고 교환 위치가 j라면 j - i의 교환이 발생하고 s를 해당 수만큼 줄여가며 계속한다.

s가 0이되거나 정렬이 완료되면 배열을 출력한다.

코드

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

		for (int i = 0; i < n && s > 0; i++) {
			int mx_idx = i;
			for (int j = i + 1; j < n && j - i <= s; j++) {
				if (a[j] > a[mx_idx])
					mx_idx = j;
			}

			s -= mx_idx - i;

			for (int j = mx_idx; j > i; j--) {
				int tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
			}
		}

		for (int i : a)
			bw.write(i + " ");
		bw.flush();
		bw.close();
	}
}