21.08.06 preEdu

기초알고리즘 Part2

9. 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
처음엔 ArrayList 두개로 해결하려했다
-> 정확성테스트는 맞았는데 효율성 테스트에서 0점맞음..

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> t1 = new ArrayList<String>();
        List<String> t2 = new ArrayList<String>();

        for(int i = 0; i < participant.length; i++){
            t1.add(participant[i]);
        }
        for(int j = 0; j < completion.length; j++){
            t2.add(completion[j]);
        }

        Collections.sort(t1);
        Collections.sort(t2);

        ArrayList<String> temparr = new ArrayList<>();
        temparr.addAll(t1);
        for (String r : t2){
            if(t1.contains(r) == true){
                temparr.remove(r);
            }
        }
        answer += temparr.get(0);
        return answer;
    }
}

사실 map이나 ArrayList같은거 안써도 정렬만으로도 풀수있는 간단한 문제였다..

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
     
        for (i = 0; i < completion.length; i++){
            if (!participant[i].equals(completion[i])){

                return participant[i];
            }
        }
        return participant[i];
    }
}

정렬을하고 삭제한다는 개념은 같았는데 나는 더 메모리를 많이 잡아먹는구린코드였던것..

10. 2016년

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

class Solution {
    public String solution(int a, int b) {
        String answer = "";
        int[] t =  {31,29,31,30,31,30,31,31,30,31,30,31};
        String[] day = {"FRI","SAT","SUN","MON","TUE","WED","THU"}; 
        int index = b-1;
        if (a == 1){
            index = b-1;
        } else{
           for (int i = 0; i < a-1; i++){
                index += t[i];
           }
        } 
        index %= 7;
        answer = day[index];
        return answer;
    }
}

좋은 방법은 아닌거 같지만 2016년의 일을 배열로 만들고 날짜를 계산후 1월1일을 기준으로 요일 배열을 만들어 나머지 연산자로 index값을 만들어 return 시켯다.

11. 소수찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.
첫코드는 이렇게 짰다. 이렇게짜니까 효율성이 좀 별로인지 효율성테스트에서 떨어졌다.

class Solution {
    public static boolean isPrime(int num){
        for (int i = 2; i < num; i++){
             if(num % i == 0) return false;
        }
        return true;
    }

    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++){
            if(isPrime(i) == true){
                answer++;
            }            
        }
        return answer;
    }
}

소수판별 공식을 찾아보니 n의 루트값까지만 확인하는방법이 있엇다

class Solution {
    public static boolean isPrime(int num){
        for (int i = 2; i*i <= num; i++){
             if(num % i == 0) return false;
        }
        return true;
    }

    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++){
            if(isPrime(i) == true){
                answer++;
            }            
        }
        return answer;
    }
}

12. 예산

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항
d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.
정렬하면 간단할거같아서 정렬후 for문으로 체크

import java.util.*;
class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        Arrays.sort(d);
        for(int r : d){
            if( (budget -= r) <= -1){
                break;
            }else {
                answer++;
            }
        }
        return answer;
    }
}

13. 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        answer -= (lost.length);
        Arrays.sort(lost);
        Arrays.sort(reserve);
        List<Integer> l = new ArrayList<>();
        List<Integer> r = new ArrayList<>();

        for(int x : lost){
            l.add(x);
        }
        for(int y : reserve){
            r.add(y);
        }

        ArrayList<Integer> temp = new ArrayList<>();
        temp.addAll(l);
        for (int k : temp){
            if(r.contains(k)){
                answer++;
                l.remove(l.indexOf(k));
                r.remove(r.indexOf(k));
            }
        }
        for(int t : l){
            if(r.contains(t - 1) == true){
                answer++;
                r.remove(r.indexOf(t-1));
                continue;
            } else if((r.contains(t + 1) == true)){
                answer++;
                r.remove(r.indexOf(t+1));
                continue;
            }
        }
        return answer;
    }
}

온갖 삽질을 통해서만들어졌다
다른사람 풀이를 확인해보니까 이렇게 리스트만들면서 할필요 없고 배열로도 가능하고 해쉬맵으로도 가능하다 이게 괜히 엄청 긴코드..