2023.08.23 TIL - 알고리즘 문제

명예의 전당 (1)

k명의 점수를 노출시키는 명예의 전당에서 가장 낮은 점수를 일자별로 정렬한 배열을 출력하는 문제이다.

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
        PriorityQueue<Integer> arr = new PriorityQueue<>();
        int[] answer = new int[score.length];
        for (int i=0; i<score.length;i++){
            arr.add(score[i]);
            if(arr.size()>k) arr.poll();
            answer[i] = arr.peek();
        }
        return answer;
    }
}

가장 낮은 수를 반복적으로 제거해야 하기에 정렬에 이점이 있는 PriorityQueue 자료구조를 활용하는 것이 좋다. 우선순위 큐에 점수를 하나씩 넣고, 만약 크기가 k보다 클 경우 하나를 제거한다. 명예의 전당은 이들 중 가장 작은 값을 지니므로 peek 메소드를 통해 값을 저장한 뒤, 이를 반복하면 큰 무리 없이 문제를 해결할 수 있다.

 

 

2016년

2016년 1월 1일은 금요일이라는 정보를 통해 2016년의 월, 일을 입력받고, 해당 날짜의 요일을 반환하는 문제이다. 

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

각 월마다 총 몇일이 있는지를 기록해둔 배열과 월의 값을 통해 해당 월 직전까지는 총 며칠인지 구한 후, 일의 값을 더해 1월 1일부터의 총 일수를 구한다. 다만 이렇게 할 경우 1월 1일도 포함해서 계산되기에 1을 뺀 후 7로 나눈 나머지를 요일을 찾는다.

 

 

카드 뭉치

두 개의 카드 뭉치에서 순서대로 카드를 꺼내 원하는 문장을 만들 수 있는지를 판별하는 문제이다.

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int i = 0;
        int j = 0;
        for( int n = 0; n<goal.length;n++){
            if(i!=cards1.length && goal[n].equals(cards1[i])) i++;
            else if(j!=cards2.length &&goal[n].equals(cards2[j])) j++;
            else return "No";
        }
        return "Yes";
    }
}

두 카드 뭉치의 첫번째 카드들과 원하는 문장의 첫번째 단어를 비교한다. 일치하는 카드가 있다면 해당 카드가 있는 카드 뭉치는 다음 카드를 꺼내고, 없다면 불가능함을 반환한다. 이를 반복한 뒤, goal 문장이 완성될 경우 가능함을 반환하게 하면 간단히 문제를 해결할 수 있다.

 

 

과일 장수

각각의 점수가 매겨진 사과들을 포장할 때 포장된 사과의 점수는 사과 점수들 중 가장 낮은 점수 * 사과의 갯수이다. 이 때 가장 높은 점수를 반환하는 문제이다.

import java.util.*;
class Solution {
    public int solution(int k, int m, int[] score) {
        int[] tmp = Arrays.stream(score).sorted().toArray();
        int answer = 0;
        for (int i = tmp.length-1;i>=0;i--){
            if((tmp.length-1-i)%m==m-1) answer+=tmp[i];
        }
        return answer*m;
    }
}

가장 낮은 점수가 상자의 점수이기에, 배열을 역순정렬한 후 앞에서부터 포장 갯수씩 세어 해당 위치의 사과의 점수*포장 갯수를 하여 더해준 값이 가장 높은 점수가 된다. 코드에서는 점수의 합을 한 후, 반환시에 갯수를 곱해주었다.

 

 

모의고사

정답의 배열이 주어질 때, 문제를 각각의 패턴에 따라 찍는 방법 중 가장 점수가 높은 방법을 찾는 문제이다.

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
        int[] oneidiot = {1,2,3,4,5};
        int[] twoidiot = {1,3,4,5};
        int[] threeidiot = {3,1,2,4,5};
        int one = 0;
        int two = 0;
        int three = 0;
        for(int i = 0;i<answers.length;i++){
            if(answers[i]==oneidiot[i%5]) one++;
            if(answers[i]==(i%2==0?2:twoidiot[i%8/2])) two++;
            if(answers[i]==threeidiot[i/2%5]) three++;
        }
        int[] tmp = {one,two,three};
        int max = Arrays.stream(tmp).max().getAsInt();
        int index = 0;
        int[] answer = new int[3];
        for (int n = 0; n < 3; n++) {
            if (max == tmp[n])
                answer[index++] = n + 1;
        }
        int[] realanswer = Arrays.copyOf(answer, index);
        return realanswer;
    }
}
//stream 안쓰는게 훨씬 빠르긴하네

각 방법의 점수를 저장할 변수를 생성한 후, 각 패턴을 계산해 찍은 답이 정답과 일치할 경우 점수를 올려준다. 그렇게 매긴 점수들 중 최댓값을 구하고, 최댓값과 점수가 동일한 방법의 번호를 담아 출력한다. 

max 값을 구할 때 stream을 사용했었는데, 다른 사람 풀이에서 stream은 속도가 많이 느리기에 하나씩 탐색해서 푸는 것이 더 빠르다는 내용이 있어 해당 방법으로 시도해 보았다. 확실히 stream은 짧고 간결한 대신, 속도가 많이 느린 것을 확인할 수 있었다.

 

 

소수 만들기

배열에서 세 수를 더해 만든 숫자가 소수인지를 판별하는 문제이다.

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        for(int i = 0; i<nums.length-2;i++){
            for(int j = i+1;j<nums.length-1;j++){
                for(int k = j+1;k<nums.length;k++){
                    int num = nums[i]+nums[j]+nums[k];
                    boolean check = true;   
                    for(int t = 2;t<=Math.sqrt(num);t++){
                        if (num%t==0) {
                            check = false;
                            break;
                        }
                    }
                    if (check) answer++;
                }
            }
        }
        return answer;
    }
}

배열에서 중복되지 않은 세 수를 더해 수를 만든다. 이 수가 소수인지 판별한 후, 소수라면 정답 변수에 1을 더한다. 이를 모든 경우의 수를 확인할 때까지 반복하면 문제를 해결할 수 있다.

 

 

덧칠하기

칠해야 하는 위치가 배열로 주어질 때, 길이가 m인 롤러로 모두 칠할 수 있는 방법 중 가장 적은 횟수를 구하는 문제이다.

class Solution {
    public int solution(int n, int m, int[] section) {
        int check = section[0];
        int answer = 1;
        for(int i = 0;i<section.length;i++)
            if(section[i]>check+m-1){
                check = section[i];
                answer++;
            }
        return answer;
    }
}

칠해야 하는 위치가 최소 1군데 이상이기에 정답은 1부터 시작한다. 롤러의 가장 왼쪽 위치를 저장한 후, 칠할 위치를 탐색하는데 롤러의 가장 오른쪽 위치보다 탐색한 값이 클 경우 탐색한 값을 롤러의 가장 왼쪽 위치에 저장한 뒤 정답 변수에 1을 더한다. 이를 모든 위치를 탐색할 때까지 반복한 후, 정답을 반환한다.

벽의 길이를 한정하는 n 값은 있으나, 벽의 길이가 어떻든 칠할 위치는 변하지 않기에 문제 해결에 사용하는 수치는 아니었다.