문제 구성 📖

코딩테스트 사이트 : 프로그래머스
난이도 : 1단계
풀이 날짜 : 2022.06.29
사용한 풀이 방법 : 완전탐색

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42840

풀이법

• 세명의 수포자를 일일이 확인한다.
• 세명중 정답 맞힌 최댓값을 구하고
• 최댓값과 동일한 만큼 배열(오름차순)에 추가 해주면 된다.

첫번째 제출

• 세가지 패턴만 존재하기에, 직접 만들어 주고
• 각각의 정답 갯수를 구해, 최대 값을 구하고
• 최대값과 비교하여, 동일하면 answer에 추가해주는 방식으로 코드를 짰다.
• 코드는 아래와 같다.

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
       
        int[] one = {1,2,3,4,5};
        int[] two = {2,1,2,3,2,4,2,5};
        int[] three = {3,3,1,1,2,2,4,4,5,5};
        int oneIndex = 0;
        int twoIndex = 0 ;
        int threeIndex = 0;
        
        int oneCount= 0;
        int twoCount =0;
        int threeCount=0 ;
        
        int max = 0;
        for(int i =0 ; i< answers.length; i++){
            oneIndex = i % one.length;
            twoIndex = i % two.length;
            threeIndex = i % three.length;
            
            if(answers[i] == one[oneIndex]){
                oneCount++;
            }
            if(answers[i] == two[twoIndex]){
                twoCount++;
            }
            if(answers[i] == three[threeIndex]){
                threeCount++;
            }
            
        }
        max = Math.max(Math.max(oneCount, twoCount),threeCount);
        List<Integer> list = new ArrayList<>();
        if(max == oneCount){
            list.add(1);
        }
        if(max == twoCount){
            list.add(2);
        }
        if(max == threeCount){
            list.add(3);
        }
       
        
       
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

결과

두번째 제출

• 첫번째 제출한 뒤에, 코드가 너무 길어 보였다.
• 물론 필요에 의해 코드가 길어지는 것은 어쩔수 없으나, 반복되는 부분으로 인해 길어지는 것이라면, 반복문으로 처리할 수 있어 보였다.
• 그래서, index와, Count를 묶어서 int[]로 만들었고,
  - 같이 수포자 3명의 패턴도 2차 배열을 만들어 넣어줬다.
• 그랬더니 확실히 코드가 짧아졌다.

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
		int[][] select = {{1,2,3,4,5},{2,1,2,3,2,4,2,5},{3,3,1,1,2,2,4,4,5,5}};
        int[] index = {0,0,0};
        int[] count = {0,0,0};

        
        int max = 0;
        for(int i =0 ; i< answers.length; i++){
            for(int j = 0 ; j< 3; j++){
                index[j] = i % select[j].length;
                
                if(answers[i] == select[j][index[j]]){
                    count[j]++;
                }
            }
     
        }
        max = Arrays.stream(count).max().getAsInt();
        
        List<Integer> list = new ArrayList<>();
        for(int j = 0 ; j< 3; j++){
            if(max == count[j]){
                list.add(j+1);
            }
        }
        
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

수정한 코드 채점 결과

• 코드는 짧아졌지만, 전체적으로 풀이시간은 올라갔다.
• 몇가지 풀이시간이 증가한 가설을 들어보자
  1. 2차배열 사용
  2. 이중 for문 사용
  3. Max 구할때 Stream 사용 유무 등등

오래걸린 이유찾기

Steam() 연산 제거

먼저 가장 빨리 수정할 수 있는 Stream() 연산부터 건들렸다.

• max = Arrays.stream(count).max().getAsInt(); 코드를
  max = Math.max(Math.max(count[0], count[1]),count[2]);으로 수정하고 실행해주었더니,
  

• 확실히 2차제출보다는 시간이 빨라졌다.

• 오히려 1차 제출했을때 보다, 빠른 부분도 생겨났다. (앞쪽 테스트는 빨라졌으나, 뒤쪽 테스트는 느리다.)

다른 사람 풀이 참고

• 먼저 다른사람이 푼것 중에 빠른 코드를 찾아 보았다.

  

• 죄다 1초도 안되는 상태로 테스트를 통과하였다.(감탄쓰..)

• 그래서 코드를 보니 아래와 같다.

import java.util.*;

class Solution {
    public static int[] solution(int[] answers) {
        int[][] patterns = {  //이중 배열
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };

        int[] hit = new int[3];
        for(int i = 0; i < hit.length; i++) {
            for(int j = 0; j < answers.length; j++) {
                if(patterns[i][j % patterns[i].length] == answers[j]) hit[i]++;
            }
        }

        int max = Math.max(hit[0], Math.max(hit[1], hit[2]));
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < hit.length; i++)
            if(max == hit[i]) list.add(i + 1);

        int[] answer = new int[list.size()];
        int cnt = 0;
        for(int num : list)
            answer[cnt++] = num;
        return answer;  //Stream 연산을 안함.
    }
}

수포자 3명을 2차배열에 넣어줬고, 정답을 맞은 갯수도 배열로 선언해줬으나, index같은 경우는 그냥 그때그때 배열에서 계산한 값을 넣어주는 모습이 보인다.
게다가 최대값에서 동점자를 파악하는 부분은 List를 통해 추가해주며,
그 List의 길이에 맞춰 배열을 생성해주고 값을 넣어,
List -> int[] 변환 작업을 반복문으로 해버린다.

결론 정리

• 2차배열과 이중 for문과는 상관없다. (완전탐색한에서)
• Stream()연산이 시간에 영향이 크다.