[백준] #13300 방 배정, #1919 애너그램 만들기

✏️ 방 배정 

사용 언어 : Java
레벨 : 브론즈 2
📎방 배정

 

🔎 문제 설명

정보 초등학교에서는 단체로 2박 3일 수학여행을 가기로 했다. 여러 학년이 같은 장소로 수학여행을 가려고 하는데 1학년부터 6학년까지 학생들이 묵을 방을 배정해야 한다. 남학생은 남학생끼리, 여학생은 여학생끼리 방을 배정해야 한다. 또한 한 방에는 같은 학년의 학생들을 배정해야 한다. 물론 한 방에 한 명만 배정하는 것도 가능하다.

한 방에 배정할 수 있는 최대 인원 수 K가 주어졌을 때, 조건에 맞게 모든 학생을 배정하기 위해 필요한 방의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, 수학여행을 가는 학생이 다음과 같고 K = 2일 때 12개의 방이 필요하다. 왜냐하면 3학년 남학생을 배정하기 위해 방 두 개가 필요하고 4학년 여학생에는 방을 배정하지 않아도 되기 때문이다.

📌 입력과 출력 

입력 : 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 주어진다. 다음 N 개의 각 줄에는 학생의 성별 S와 학년 Y(1 ≤ Y ≤ 6)가 공백으로 분리되어 주어진다. 성별 S는 0, 1중 하나로서 여학생인 경우에 0, 남학생인 경우에 1로 나타낸다. 

 

출력 : 표준 출력으로 학생들을 모두 배정하기 위해 필요한 최소한의 방의 수를 출력한다.

 

⭐ 서브태스크

⚒️ 풀이

바킹독 알고리즘 문제집 - 배열에 있던 문제인데 나는 2차원 배열을 선언해서 [학년][성별] 값으로 한명씩 들어가게 했고, 이 배열이라는 방에 첫번째로 들어오는 사람이거나, 방에 k 명이 초과되는 순간에 result 값을 하나씩 증가시켰고, k 명 + 1 명이 되는 순간 다시 그 방을 1로 초기화 시켜서 필요한 방의 개수를 구하도록 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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 k = Integer.parseInt(st.nextToken());
        int[][] student = new int[6][2];
        int result = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int gender = Integer.parseInt(st.nextToken());
            int grade = Integer.parseInt(st.nextToken()) - 1;
            student[grade][gender]++;

            if(student[grade][gender] == 1 || student[grade][gender] == k + 1) {
                result++;
                student[grade][gender] = 1;
            }
        }

        System.out.println(result);
    }
}

백준에서 서브태스크가 있는 문제를 굉장히 오랜만에 풀어봐서 맞았습니다!! 가 아닌 100점 이게 왜이렇게 반갑고 기부니가 좋은지.. 

 

✏️ 애너그램 만들기 

사용 언어 : Java
레벨 : 브론즈 2
📎애너그램 만들기

 

🔎 문제 설명

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.

한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.

두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거할 수 있다.

📌 입력과 출력 

입력 : 첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어진다. 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어진다.

 

출력 : 첫째 줄에 답을 출력한다.

 

⚒️ 풀이

애너그램이 될라면 두 영단어의 알파벳 비율이 같아야 하고 같아지려면 서로 다른 알파벳들을 지워줘야 한다는 점을 이용해서 풀어봤다. 우선 첫번째 영단어를 각 자리별로 쪼개서 alp 배열에 등장할 때마다 하나씩 증가를 시켜놓고, 두번째 영단어를 계산할 때 alp 배열에 0이 아닌 값이 들어있으면 첫번째 영단어에서 이미 등장했던 알파벳이니까 증가가 아닌 감소를 시켜주고, alp 배열이 0이면 새로 등장한 알파벳이거나 이미 등장했어도 더 많은 개수가 들어온거니까 증가를 시킨 뒤 마지막에 배열에 담겨져 있는 모든 alp 개수를 구하면 되는데, 나는 그냥 alp 배열을 증가, 감소할 때 바로 result 에 증가 감소를 시켜줘서 마지막에 또 for 문을 돌지 않아도 되도록 풀어봤다!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] str1 = sc.nextLine().toCharArray();
        char[] str2 = sc.nextLine().toCharArray();
        int[] alp = new int[26];

        for (int i = 0; i < str1.length; i++) {
            alp[str1[i] - 'a']++;
        }

        int result = str1.length;

        for (int i = 0; i < str2.length; i++) {
            if (alp[str2[i] - 'a'] == 0) {
                result++;
            } else {
                alp[str2[i] - 'a']--;
                result--;
            }
        }

        System.out.println(result);
    }
}