Java - 명예의 전당(1), 카드 뭉치, 과일 장수

Java

명예의 전당(1)

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/138477
• 매일 1명의 가수가 노래를 부르고 시청자들의 문자 투표수로 가수에게 점수를 부여함
• 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올림
• 프로그램 시작 이후 초기 k일까지는 출연 가수의 모든 점수가 명예의 전당에 오르게 되고 k일 다음부터는 출연 가수의 점수가 기존 명예의 전당 목록 k번째 순위의 점수보다 더 높으면 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됨
• k가 3이고 7일 동안 진행된 가수의 점수가 10, 100, 20, 150, 1, 100, 200이라면 명예의 전당의 최 하위 점수는 10, 10, 10, 20, 20, 100, 100이 됨
• 명에의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때 매일 발표된 명예의 전당의 최하위 점수를 반환하는 함수를 완성

제한조건

• 3 <= k <= 100
• 7 <= score의 길이 <= 1,000
• 0 <= score[i] <= 2,000

입출력 예시

나의 풀이

순수 배열 활용

import java.util.Arrays;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] rank = new int[k];

        for (int i = 0; i < score.length; i++) {

            if (i < k) {    
                rank[i] = score[i];
            } else {
                int minIndex = 0;
                int min = rank[0];
                for (int j = 0; j < k; j++) {
                    if (rank[j] < min) {
                        min = rank[j];
                        minIndex = j;
                    }
                }
                if (score[i] > min) {
                    rank[minIndex] = score[i];
                }
            }

            int loop = Math.min(i + 1, k);
            int min = rank[0];
            for (int j = 1; j < loop; j++) {
                if (rank[j] < min) {
                    min = rank[j];
                }
            }
            answer[i] = min;
        }

        return answer;
    }
}

• 명예의 전당의 최하위 점수를 반환할 answer 배열의 길이를 score.length만큼 지정하고, 명예의 전당의 점수를 반영할 rank 배열의 길이를 k만큼 지정하여 생성했다.
• 먼저 반복문을 통해서 i가 k - 1보다 작을 때에는 아무런 조건 없이 명예의 전당에 등록될 수 있도록 rank 배열에 score의 값을 i < k조건으로 저장한다.
• rank배열에 값이 다 찼다면 명예의 전당의 점수와 비교하여 score[i]값과 명예의 전당인 rank 배열의 가장 작은 값을 비교해서 score[i]이 크면 교체하는 작업을 진행했다.
  • 먼저 rank배열의 값 중 가장 작은 값을 비교하기 위해 min 변수에 rank[0]의 값을 하나 꺼내놓고, 명예의 전당의 가장 작은 값을 가지고 있는 index의 값을 저장하기 위한 변수도 하나 선언했다.
  • 문제에서는 내림차순 정렬로 명예의 전당에 정렬이 되어서 마지막 인덱스의 값을 꺼내는 방식으로 문제풀이를 진행했는데 정작 문제를 풀 당시에는 그런 생각을 하지 못했었고 코드 회고를 적으면서 알게 됐다
  • 우선은 내 방식대로 하게되면 rank배열의 값을 하나씩 꺼내서 min 값과 비교를 하는데 꺼낸 값이 min값보다 작다면 min의 값을 rank[j]의 값으로 교체하고 minIndex 변수에 해당 배열의 index 위치를 저장한다.
  • 모든 반복이 끝나면 min값에는 명예의 전당의 가장 작은 값이 들어있으므로 score[i] 값과 min값을 비교하여 score[i]의 값이 더 크다면 rank[minIndex]의 위치에 score[i]의 값을 저장하여 명예의 전당을 교체한다.
• 이렇게 명예의 전당에 점수를 입력하는 알고리즘을 완성하면 이제 매일 명예의 전당의 최하위 값을 발표하는 answer 배열에 값을 채워야한다.
• 반복 회수를 명예의 전당에 값이 전부 찼다면 k번만큼, 그게 아니라면 i + 1번만큼 (최소 1번 반복) 반복하기 위해 Math.min(i+1, k)를 사용하여 반복횟수를 정하고 마찬가지로 명예의 전당의 최소값을 구하기 위해 rank[0]의 값을 min 변수에 저장해둔다.
• 그다음 반복을 통해서 rank배열의 요소가 min보다 작다면 min을 교체하고 반복이 모두 끝나면 min에는 rank 배열의 요소 중 가장 작은 값이 담기게 되고 이 값을 answer[i]에 담아서 반환하여 문제를 해결했다.

다른 풀이

ArrayList활용

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        
        ArrayList<Integer> list = new ArrayList<>();
		
        for (int i = 0; i < score.length; i++) {
            list.add(score[i]);
            Collections.sort(list);
            if (list.size() > k) {
                list.remove(0);
            }
            answer[i] = list.get(0);
        }
        return answer;
    }
}

• 명예의 전당을 관리하는 자료구조로 ArrayList<Integer>를 선택한 풀이이다
• 반복문을 통해 score[i]의 값을 꺼내서 저장하고 컬렉션이므로 Collections.sort(list)를 통해서 오름 차순 정렬하여 가장 작은 값이 0번째 인덱스에 오도록한다.
• 이때 list.size()가 k보다 크게 된다면 list.remove(0)의 값을 제거하여 가장 작은 명예의 전당의 값을 삭제한다.
• 먼저 score[i]의 값을 저장하여 오름차순을 정렬하기 때문에 기존의 명예의 전당의 값과 score[i]의 값이 함께 정렬되어 이 중 가장 작은 값을 제거하기 때문에 이 로직이 정상적으로 통과가 되는데 이것이 가변 리스트를 사용한 ArrayList의 매우 큰 장점이다.
• 그 이후 남아있는 명에의 전당의 가장 작은 값인 list.get(0)를 꺼내서 answer[i]에 저장하여 반환하면 문제를 해결할 수 있다
• 만약 내림차순으로 정렬하고 k번째의 값을 꺼내고 싶다면 반복문의 로직을 아래처럼 작성하면 된다

for (int i = 0; i < score.length; i++) {
    list.add(score[i]);
    Collections.sort(list, Comparator.reverseOrder());
    if (list.size() > k) {
        list.remove(k);
    }
    answer[i] = list.get(list.size() - 1);
}

 

Queue자료구조 활용

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for(int i = 0; i < score.length; i++) {

            priorityQueue.add(score[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

            answer[i] = priorityQueue.peek();
        }

        return answer;
    }
}

• Queue 자료구조중 PriorityQueue 자료구조를 사용한 풀이가 인상깊어서 가져왔다.
• PriorityQueu는 최소 힙 구조로 동작하여 항상 가장 작은 값이 큐의 맨 앞에 위치하는 자료구조라고 한다.
• 아이디어는 똑같이 자료구조에 점수를 입력하고 자료구조의 사이즈가 k보다 크면 가장 앞에있는 요소를 poll()로 제거하는데 PriorityQueue 자료구조이기 때문에 항상 작은값이 제거되어 상위 k개의 점수만 유지할 수 있게 된다.
• 그 다음 자료구조에 남아있는 값중 작은값을 answer[i]에 저장할 때는 peek()을 사용하여 자료구조의 요소를 제거하지 않고 반환하여 문제를 해결한다.

---

카드 뭉치

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/159994
• 영어 단어가 적힌 카드 뭉치 두 개를 아래와 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만드는 문제
  • 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용함
  • 한 번 사용한 카드는 다시 사용할 수 없음
  • 카드를 사용하지 않고 다음 카드로 넘어갈 수 없음
  • 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없음
• 예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있음
• 문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 수 있다면 "Yes" 만들 수 없다면 "No"를 return하는 solution 함수 만들기

제한조건

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 존재함
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있음
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있음

입출력 예시

나의 풀이

플래그, 스트링빌더, index 활용

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "";

        StringBuilder addGoal = new StringBuilder();
        StringBuilder equalsStr = new StringBuilder();

        int card1Count = 0;
        int card2Count = 0;

        boolean card1Flag = false;
        boolean card2Flag = false;

        for (String getGoalStr : goal) {
            addGoal.append(getGoalStr);


            if (!card1Flag && cards1[card1Count].equals(getGoalStr)) {
                card1Count++;
                equalsStr.append(getGoalStr);

                if (card1Count > cards1.length -1) {
                    card1Flag = true;
                }

            }

            if (!card2Flag && cards2[card2Count].equals(getGoalStr)) {
                card2Count++;
                equalsStr.append(getGoalStr);

                if (card2Count > cards2.length -1) {
                    card2Flag = true;
                }
            }

        }

        if (addGoal.toString().contentEquals(equalsStr)) {
            answer = "Yes";
        } else {
            answer = "No";
        }
        return answer;
    }
}

• 이번에도 나는 원초적으로 접근했는데, 먼저 완성된 단어의 배열인 goal의 단어를 하나씩 꺼내서 cards1과 cards2의 단어들과 비교해야하기 때문에 반복문을 사용했다.
• 그 다음 두개의 StringBuilder를 사용했는데, 하나는 문자열 배열 goal의 각 요소를 하나의 문장으로 만들기 위한 StringBuilder이고, 또 다른 하나는 여러 비교 과정을 거쳐서 완성된 문장을 담는 StringBuilder이며 최종적으로 이 둘을 비교하여 같으면 Yes, 다르면 No를 반환하도록 했다
• 여기서의 핵심 로직은 반복문으로 꺼내는 goal의 단어를 cards1과 card2의 요소와 비교하여, 둘 중 하나의 카드와 같다면 다음으로 넘어가고, 다음 goal배열의 단어를 비교할 때는 이미 비교한 카드 뭉치에서는 넘어가야 한다는 것이였다.
• 나는 이 부분을 각 카드 뭉치들이 배열이라는 것을 활용하여 먼저 정수형 변수를 2개를 생성하고 이를 카드 뭉치의 요소를 꺼내는 인덱스로 사용했다.
• 각각의 카드뭉치의 요소와 goal 배열에서 꺼낸 요소가 같을 때마다 해당 변수의 값을 증가시키면 다음 goal 요소를 꺼내서 카드 뭉치를 비교하게 될 때 인덱스의 값이 증가되어있으므로 이미 비교한 요소는 넘어갈 수 있게 된다.
• 또 하나의 검증로직이 필요한데, 각 카드뭉치의 길이가 다르기 때문에 goal의 단어를 비교할 때 마다 각 카드 뭉치를 확인하면 인덱스 범위가 벗어나서 에러가 발생할 수 있기 때문에 boolean 타입 변수를 활용하여 이를 검증했다.
• 즉, 각 카드 뭉치의 길이 -1 (배열의 개수)보다 카드 배열의 인덱스를 뜻하는 정수값이 커지게 되면 각각 선언해둔 boolean 타입 변수를 true로 변환시켜서 boolean 타입 변수가 true이면 해당 카드뭉치는 모두 사용했으므로 더이상 해당 카드 뭉치에서는 goal 배열의 요소와 비교할 수 없게 된다
• 최종적으로 완성된 addGoal을 String으로 변환하여 조건을 거쳐 완성된 문장인 equalsStr을 비교하여 같다면 Yes 다르다면 No를 반환화게 하여 문제를 해결했다

다른 풀이

조건을 최적화

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

• AI가 나의 풀이의 불필요한 StringBuilder사용과 boolean 변수를 사용한 부분을 제거하여 간결하게 최적화 해주었다....
• 먼저 goal배열의 각 단어에 대해 접근할 인덱스가 필요한 것은 맞으므로 두 개의 정수를 선언해준다.
• 그다음 조건을 boolean으로 하는 것이 아니라 각 카드 뭉치의 인덱스가 배열의 길이보다 작은지 확인을 먼저 한 후, 해당 조건이 통과하면 단어를 비교 진행하도록 조건문을 작성했다.
• 완성된 문장을 비교하는 것이아니라 이 비교하는 과정에서 완성할 문장을 찾지 못한다면 그 즉시 "No"를 반환하여 불필요한 반복 횟수를 줄일 수 있도록 하고 모든 단어를 순서대로 매칭할 수 있다면 "Yes"를 반환한다.
• 완성된 문장을 비교하는 것이 아니라 애초에 비교할 때 문장을 완성할 수 없는 조건을 중간에라도 만난다면 즉시 No를 리턴하여 반복 횟수를 줄이는 로직을 적용하지 못했는데, 이렇게 조건을 잘 작성하면 간단하게 해결할 수 있다는 것을 알게 되었다.

List 자료구조 사용

import java.util

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        List<String> card1Ary = new ArrayList<>(Arrays.asList(cards1));
        List<String> card2Ary = new ArrayList<>(Arrays.asList(cards2));

        String answer = "Yes";
        for(String str:goal) {
            if(!card1Ary.isEmpty() && card1Ary.get(0).equals(str)) {
                card1Ary.remove(0);
            } else if(!card2Ary.isEmpty() && card2Ary.get(0).equals(str)) {
                card2Ary.remove(0);
            } else {
                answer = "No";
                break;
            }
        }
        return answer;
    }
}

• 아이디어는 동일한데, 카드 뭉치를 ArrayList로 만들어서 인덱스를 증가시키면서 비교하는 것이 아니라 항상 카드 뭉치의 가장 첫 번째의 요소를 항상 비교하도록 get(0)을 꺼내서 조건이 통과하면 remove(0)으로 해당 값을 제거하는 방식도 좋은 것 같아서 가져왔다.
• 다만 remove(0)은 내부적으로 O(n)의 시간이 소요되기 때문에 입력크기가 크다면 성능에서 차이가 있을 것이기 때문에 이런 경우 LinkedList나 Queue 자료구조를 쓰는것이 더 적절해 보인다

---

과일 장수

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/135808
• 사과의 상태는 1점부터 k점까지의 점수로 분류하고 k점이 최상품이며 1점이 최하품임
• 사과 한 상자의 가격은 아래과 같이 결정됨
  • 한 상자에 사과 m개씩 담아 포장
  • 상자에 담긴 사과 중 가장 낮은 점수가 p (1 <= p <= k)점인 경우 사과 한 상자의 가격은 p * m임
• 가능한 많은 사과를 팔았을 때 얻을 수 있는 최대 이익을 계산해야하며 사과는 상자 단위로만 판매하고 남는 사과는 버림
• k = 4, m = 3, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있음
  • 최저 사과 점수 x 한 상자에 담긴 사과 개수 x 상자의 개수 = 2 x 4 x 1 = 8
• 사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m , 사과들의 점수 score가 주어졌을 때 과일 장수가 얻을 수 있는 최대 이익을 return 하는 solution 함수를 완성

제한조건

• 3 <= k <= 9
• 3 <= m <= 10
• 7 <= score의 길이 <= 1,000,000
• 1 <= score[i] <= k
• 이익이 발생하지 않는 경우에는 0을 return

입출력 예시

나의 풀이

2중 반복문 활용

class Solution {
    public int solution(int k, int m, int[] score) {

        int answer = 0;
        int count = 0;

        for(int i = k; i > 0; i--) {

            for (int value : score) {
                if (value == i) {
                    count++;
                }
            }

            answer += i * m * (count / m);
            count %= m;

        }
        return answer;
    }
}

• 우선 k가 상품의 등급이고 그 상품의 등급별로 score 배열에 상품이 담겨있으므로 k 값을 하나씩 줄여가면서 score의 요소를 비교하면서 각 상품의 개수를 구해야 겠다는 생각을 하게 되었다.
• 먼저 상품의 등급이 높은것 부터 구해야 남은 상품을 다음 등급의 상품과 엮을 수 있으므로 처음 반복문을 k를 i에 담아 k부터 1까지 반복하도록 구성했다
• 그 다음 반복문에서 score 배열에서 요소를 하나씩 꺼내서 i와 비교하여 같다면 count를 세어 score 배열에 k등급의 상품이 몇개 담아있는지 구했다
• 반복이 끝나면 구해진 k등급의 개수를 m개로 나누어 k등급의 상품을 몇박스로 구할 수 있는지 구하고 등급을 곱하여 최대 판매할 개수를 answer에 누적한다.
• 여기서 count를 나눌 때 나머지가 남아있을 수 있으므로 나머지는 다음 상품과 함께 다시 포장해야하므로 count에 나머지를 저장시킨다.
• 위 로직을 i가 1이 될 때까지 반복하여 문제를 해결할 수 있다

다른 풀이

그리디 활용

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        Arrays.sort(score);

        for(int i = score.length; i >= m; i -= m){
            answer += score[i - m] * m;
        }

        return answer;
    }
}

• 나의 풀이는 score 배열을 매 등급마다 순회하여 최악의 경우 O(k * n)의 시간복잡도를 가지면서 매우 비효율적이다.
• 그래서 이런거는 정렬 기반의 풀이를 하는 것이 좋으므로 정렬하고 뒤에서부터 m개씩 묶는 풀이가 더 깔끔하다고 한다 -> 그리디(탐욕적) 방식 풀이
  • 그리디 알고리즘이란 매 순간 최선의 선택을 하면 전체적으로도 최적의 해가 된다고 믿는 전략이라고 한다
  • 지금 당장 좋아 보이는 선택을 반복해서 쌓아가는 방식이며 대표적으로는 아래의 예시가 있다고 한다
    • 거스름돈 문제: 큰 동전부터 최대한 많이 사용
    • 회의실 배정 문제: 가장 빨리 끝나는 회의부터 선택
    • 배낭 문제(단순): 무게 대비 가치가 높은 아이템부터 담기
    • 사과 상자 문제: 점수가 높은 사과부터 m개씩 묶기
  • 항상 정답을 보장하지 않으므로 그리디로 풀어도 최적의 해가 보장되는 문제인지 확인하는것이 중요하다고 한다.
• 먼저 score를 정렬하여 score의 요소를 높은 요소부터 바가스로 묶을 수 있는 만큼 반복한다.
• score[i - m]은 해당 박스에서 가장 낮은 점수이므로 * m을 곱하여 박스 하나의 가격을 구한 후 answer에 누적시키면 깔끔하게 문제를 해결할 수 있다.

---

SQL

문제

문제 및 테이블 예시

• 프로그래머스 - <https://school.programmers.co.kr/learn/courses/30/lessons/59411>
• d

입출력 예시

나의 풀이