티스토리 뷰

프로그래머스 로고

 

 

프로그래머스 완전 탐색 문제이다.

 

 

 

문제 설명

 

3명의 사람이 있는데 문제를 1번 부터 마지막 문제까지 다음과 같은 순서로 찍는다고한다.

  • 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 함수를 작성해라

 

문제 설명

 

 

 

 

 

제한 조건

 

제한 조건

 

 

 

 

 

 

입 출력 예시 

 

입 출력 예시

 

 

 

 

 

 

Solution 1)

 

찍는 순서를 Queue에 담아서 poll() 하고 add()로 계속 넣어주면서 확인하는 방식이다.

한명, 한명 각자 따로 계산하게 되었고 생각보다 효율이 더 안좋았다..

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] solution(int[] answers) {
        int a = 0;
        int b = 0;
        int c = 0;
        int count = 0;

        Queue<Integer> method1 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        Queue<Integer> method2 = new LinkedList<>(Arrays.asList(2, 1, 2, 3, 2, 4, 2, 5));
        Queue<Integer> method3 = new LinkedList<>(Arrays.asList(3, 3, 1, 1, 2, 2, 4, 4, 5, 5));

        for(int i = 0; i < answers.length; i++){
            int num = answers[i];

            int int1 = method1.poll();
            int int2 = method2.poll();
            int int3 = method3.poll();

            if(int1 == num) a++;
            if(int2 == num) b++;
            if(int3 == num) c++;

            method1.add(int1);
            method2.add(int2);
            method3.add(int3);
        }
        int max = Math.max(a, Math.max(b, c));
        if(a == max) count++;
        if(b == max) count++;
        if(c == max) count++;

        int index = 0;
        int[] answer = new int[count];
        if(a == max) answer[index++] = 1;
        if(b == max) answer[index++] = 2;
        if(c == max) answer[index++] = 3;
        return answer;
    }
}

 

성능 결과

 

 

 

 

Solution 2)

 

Solution 1)에서 봤을 때는 뭔가 하드코딩의 느낌이 강하게 느껴졌다.

다른 사람의 풀이를 보니 되게 좋은 부분이 많아서 해당 코드를 가져오게 되었다.

 

  • 찍는 패턴을 2차원 배열로 선언하여 사용
  • 문제가 많을 수도 있는데 찍는 순서는 반복이니 % 를 사용
  • List 사용

 

이건 당연한게 아니야? 라고 생각할 수 있는데 문제를 풀 때 위 3개를 사용해야 겠다고 떠올리는 사람은 몇이나 될까?

 

코드 설명은 아래 주석과 함께 남기겠습니다.

import java.util.*;

class Solution {
    public 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}
        };

		// 각각 의 사람 문제 찍어서 맞힌 문제 +1
        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;
    }
}

테스트 결과

 

 

 

 

감사합니다.

 

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함