프로그래머스 모의고사 카드 뭉치 (99클럽 코딩테스트 22일차 TIL)

목표

오늘 같은 문제들이 나왔을때 빠르게 푸는게 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

수포자는 삼인방은 모의고사에 수학 문제를 전부 찍으려 한다.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5
1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 
가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성

내가 이 문제를 보고 생각해본 부분

수포자들이 찍는 방식을 배열로 정의해준다.
answers 배열의 값과 수포자들이 찍는 방식의 배열을 비교해서 맞힌 문제 수를 counting 해준다.
가장 많이 맞힌 사람을 찾는다.
맞힌 문제 수가 가장 높은 사람이 여러 명일 경우 오름차순으로 정렬해서 return 한다.

코드로 구현

import java.util.ArrayList;

class Solution {
    public int[] solution(int[] answers) {
        int[] person1 = {1, 2, 3, 4, 5}; 
        int[] person2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] person3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        int[] score = new int[3];
        
        for(int i=0; i<answers.length; i++) {
            if(answers[i] == person1[i%person1.length]) {
                score[0]++;
            }
            if(answers[i] == person2[i%person2.length]) {
                score[1]++;
            }
            if(answers[i] == person3[i%person3.length]) {
                score[2]++;
            }
        }
        
        int maxScore = Math.max(score[0], Math.max(score[1], score[2])); 
        ArrayList<Integer> list = new ArrayList<>();
        
        if(maxScore == score[0]) list.add(1);
        if(maxScore == score[1]) list.add(2); 
        if(maxScore == score[2]) list.add(3);
        
        int[] answer = new int[list.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    } 
}

시간복잡도 O(n)

장점
입력 데이터의 크기가 커져도 선형적으로 증가하기 때문에 효율적이다.
대규모 입력데이터에도 비교적 빠르게 실행된다.

단점
더 효율적인 알고리즘(O(logn), O(1))이 존재할 수 있다.
입력 데이터가 매우 커지면 여전히 느려질 수 있다.

내가 생각했을때 문제에서 원하는부분

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 
코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.
원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

내가 이 문제를 보고 생각해본 부분

cards1과 cards2의 문자열 배열을 하나의 리스트에 병합한다.

goal 배열을 순회하면서 각 문자열이 병합된 리스트에 존재하는지 확인한다.
존재하지 않는다면 바로 "No"를 리턴한다.

병합 리스트에서 현재 인덱스의 문자열을 제거하고 다음 인덱스의 문자열을 확인한다.
모든 인덱스를 확인했는데 "No"가 리턴되지 않았다면 "Yes"를 리턴한다.

코드로 구현

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        List<String> cardList = new ArrayList<>();

        for(String card : cards1) {
            cardList.add(card);    
        }
        
        for(String card : cards2) {
            cardList.add(card);
        }
        
        int index1 = 0;
        int index2 = 0;

        for(String word : goal) {
            if(index1 < cards1.length && cards1[index1].equals(word)) {
                index1++;
                continue;
            }

            if(index2 < cards2.length && cards2[index2].equals(word)) {
                index2++;
                continue;
            }

            return "No";
        }
        return "Yes";
    }
}

시간복잡도 O(N+M+K)

장점
입력 데이터가 정렬되어 있다는 점을 이용해 인덱스로 순서를 효율적으로 확인할 수 있다.

단점
contains 연산의 시간 복잡도가 O(N+M)이기 때문에 입력 데이터 Scale이 커지면 성능 저하가 발생할 수 있다.

마무리

오늘 이렇게 긴 문제를 풀어봤는데 생각하기 어려운 문제였다. 다음에 또 와서 풀어보면 못풀 수도 있을것같다. 많이 풀어보는게 답인것같다.