알고리즘 재활 5일차 - 백준 27648, 26043, 2817번

ㅋㅋ 아 신난다

 

 

증가 배열 만들기

 

 

1,1 에서 시작해서 우측이나 아래쪽으로 쭉 오름차순 패턴을 띄는 배열을 만들면 된다.

간단하게 i,j 로 생각해서 값을 넣어주었다.

 

1,1 1,2 1,3

2,1 2,2 2,3

3,1 3,2 3,3 이게 이미 증가 배열이잖아.

i-j -1 값을 넣어주었다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S5 증가 배열 만들기
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        int[][] arr = new int[N][M];
        String answer = "YES";
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j] = (i + 1) + (j + 1) - 1;
                if (arr[i][j] > K) {
                    answer = "NO";
                    break;
                }
            }
        }
        System.out.println(answer);
        if(answer.equals("YES")) {
            for (int[] s : arr) {
                for (int k : s) {
                    sb.append(k).append(" ");
                }
                sb.append("\n");
            }
            System.out.println(sb);
        }
    }
}
 

 

---

식당 메뉴

 

 

문제가 이해가 잘안가서 또 적으면서 풀었다.

N이 주어지고,
커맨드로 1 or 2가 들어옴.

커맨드가 1인경우 -----------------
1 A B 가 들어오면
A는 학생번호, B는 원하는 메뉴다.

커맨드가 2인 경우 ----------------
2 B 가 들어오면 
2유형은 B메뉴가 준비되었음을 뜻함.

원하는 메뉴를 먹은경우 첫번째 리스트에
원하는 메뉴를 못먹은경우 두번째 리스트
음식을 먹지 못했다면 세번째 리스트에 담아 출력
음식은 순서대로 먹어야하고, 리스트가 비었다면 "None"

 

출력은 "오름차순"

문제를 잘 읽자

 

import java.io.*;
import java.util.*;
 
public class Main { // S4 식당 메뉴
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
 
        Queue<int []> stuQue = new ArrayDeque<>();
        Queue<Integer> menuQue = new ArrayDeque<>();
 
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            if(cmd == 1){
                int stuNum = Integer.parseInt(st.nextToken());
                int wannaMenuNum = Integer.parseInt(st.nextToken());
                stuQue.offer(new int[]{stuNum, wannaMenuNum});
            }else if(cmd == 2){
                int menuNum = Integer.parseInt(st.nextToken());
                menuQue.offer(menuNum);
            }
        }
 
        List<Integer> happyStu = new ArrayList<>();
        List<Integer> unhappyStu = new ArrayList<>();
        List<Integer> hungry = new ArrayList<>();
 
        while(!stuQue.isEmpty()){
            if(menuQue.isEmpty()){
                // 메뉴를 못 먹을때
                while(!stuQue.isEmpty()){
                    int [] stu = stuQue.poll();
                    hungry.add(stu[0]);
                }
                break;
            }
            int [] stu = stuQue.poll();
            int menuNum = menuQue.poll();
 
            if(stu[1] == menuNum){
                happyStu.add(stu[0]);
            }else{
                unhappyStu.add(stu[0]);
            }
        }
 
        if(happyStu.isEmpty()){
            sb.append("None").append("\n");
        } else {
            Collections.sort(happyStu);
            for(int student : happyStu){
                sb.append(student).append(" ");
            }
            sb.append("\n");
        }
 
        if(unhappyStu.isEmpty()){
            sb.append("None").append("\n");
        } else {
            Collections.sort(unhappyStu);
            for(int student : unhappyStu){
                sb.append(student).append(" ");
            }
            sb.append("\n");
        }
 
        if(hungry.isEmpty()){
            sb.append("None").append("\n");
        } else {
            Collections.sort(hungry);
            for(int student : hungry){
                sb.append(student).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
 

---

ALPS식 투표

 

 

문제 이해가 참.. 오래 걸렸다

스태프들에게 점수를 부여하는 알고리즘을 짜는것이 목적이다.

참가자의 5% 미만의 투표를 받은 스태프는 제외.

스태프는 투표수를 1부터 14로 나누어 점수 집단을 갖게 된다.

이후 모든 스태프의 점수 집단을 모아 상위 14위 숫자까지 칩을 제공한다.

 

이런식으로 정렬해서 상위 14권의 점수 스태프에게 칩을 준다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S3 ALPS식 투표
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        int X = Integer.parseInt(br.readLine()); // 전체 수
        int N = Integer.parseInt(br.readLine()); // 스태프 수
 
        List<Player> playersList = new ArrayList<>();
 
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int votes = Integer.parseInt(st.nextToken());
            //5% 미만처리
            if(votes < X * 0.05){
                continue;
            }
            int [] scores = new int[14];
            for(int j = 1; j<= 14; j++){
                scores[j-1] = votes/j;
            }
            playersList.add(new Player(name, votes, scores, 0));
        }
 
        // 상위 14개의 점수를 가진 플레이어에게 chips +1
        List<Score> scoreList = new ArrayList<>();
        for (Player player : playersList) {
            for (int score : player.scores) {
                scoreList.add(new Score(player, score));
            }
        }
 
        // 점수 리스트를 내림차순 정렬
        Collections.sort(scoreList, (a, b) -> b.score - a.score);
 
        // 상위 14개의 점수에 해당하는 플레이어들에게 chips +1
        for (int i = 0; i < 14 && i < scoreList.size(); i++) {
            scoreList.get(i).player.chips++;
        }
 
        // 이름순으로 정렬
        Player[] players = playersList.toArray(new Player[0]);
        Arrays.sort(players, Comparator.comparing(p -> p.name));
 
        // 결과 출력
        for (Player player : players) {
            sb.append(player.name).append(" ").append(player.chips).append("\n");
        }
 
        System.out.print(sb);
    }
 
    public static class Player {
        String name;
        int votes;
        int[] scores;
        int chips;
 
        public Player(String name, int votes, int[] scores, int chips) {
            this.name = name;
            this.votes = votes;
            this.scores = scores;
            this.chips = chips;
        }
    }
 
    public static class Score {
        Player player;
        int score;
 
        public Score(Player player, int score) {
            this.player = player;
            this.score = score;
        }
    }
}