lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read


입출력 예시

Input-1
[1,2,3,4,5]
Output-1
[1]

Input-2
[1,3,2,4,2]
Output-2
[1,2,3]


문제 풀이

해당 문제는 완전 탐색 알고리즘으로 접근해야 한다.
먼저 완전 탐색 알고리즘이 뭔지 알아보자.

완전탐색(브루트포스)이란?

간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.
무식하게 가능한 거 다 해보겠다는 방법을 의미하며 브루트포스(Brute Force)라고도 부른다.
이 방법은 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

완전탐색의 활용법은?

  1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
  2. 가능한 모든 방법을 다 고려한다.
  3. 실제 답을 구할 수 있는지 적용한다.

하지만, 반대로 모든 수를 다 확인하는 만큼 팩토리얼이나 제곱단위로도 시간복잡도가 커질 수 있다.
해당문제가 경우의 수를 모두 따졌을 때 일정시간 이상 소요될 경우 시간초과가 될 수 있기 때문에 유의해서 사용해야 한다.

이 문제에선 완전탐색 기법을 활용해 반복/조건문을 통해 가능한 모든 경우의 수를 찾아보려 한다.

먼저 수포자 3명의 찍는 방식 배열의 길이가 모두 다르기에 주어진 정답배열의 길이만큼 늘렸다.

1
2
3

String[] arr1 = {"1","2","3","4","5"}; // length:5
String[] arr2 = {"2","1","2","3","2","4","2","5"}; // length:8 
String[] arr3 = {"3","3","1","1","2","2","4","4","5","5"}; // length:10

수포자 배열들을 그대로 사용하자니 배열의 길이를 가변적으로 조정하기 어려워 별도의 list로 옮겼다. 그리고 주어진 정답 배열의 길이만큼 순회하며 인덱스 범위를 넘어갈 경우 첫 인덱스부터 다시 반복하여 채워서 늘렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13

ArrayList<String> list1 = new ArrayList<>(Arrays.asList(arr1));
ArrayList<String> list2 = new ArrayList<>(Arrays.asList(arr2));
ArrayList<String> list3 = new ArrayList<>(Arrays.asList(arr3));

int size1 = list1.size();
int size2 = list2.size();
int size3 = list3.size();

for(int i=0; i<=answers.length; i++) {
    if(i>size1) list1.add(list1.get(i-size1-1));
    if(i>size2) list2.add(list2.get(i-size2-1));
    if(i>size3) list3.add(list3.get(i-size3-1));
}

위 코드의 반복문 내용을 보면 주어진 정답배열의 길이가 12이고 3개의 수포자 배열 모두 그에 맞춰 자기 인덱스에 맞춰 늘릴 수 있다.

1
2
3
4

answers = [1,1,1,1,1,1,1,1,1,1,1,1]
list1 = [1,2,3,4,5,1,2,3,4,5,1,2] // 1,2,3,4,5
list2 = [2,1,2,3,2,4,2,5,2,1,2,3] // 2,1,2,3,2,4,2,5
list3 = [3,3,1,1,2,2,4,4,5,5,3,3] // 3,3,1,1,2,2,4,4,5,5

이제 정답배열만큼 각 수포자 list 원소가 준비되었으니 정답 여부를 검증할 차례이다. 먼저 각 수포자 배열의 정답 카운트를 셀 변수를 선언하고 초기화하자.

1
2
3
4
5
6
7
8
9

int cnt1 = 0;
int cnt2 = 0;
int cnt3 = 0;

for(int i=0; i<answers.length; i++) {
    if(answers[i] == Integer.parseInt(list1.get(i))) cnt1++;
    if(answers[i] == Integer.parseInt(list2.get(i))) cnt2++; 
    if(answers[i] == Integer.parseInt(list3.get(i))) cnt3++;
}

그리고 위 코드와 같이 다시 정답배열을 순회하며 각 수포자 배열의 원소마다 정답여부를 확인하여 정답카운트 변수에 담았다.

여기서 놓치지 말아야 할 점은 가장 높은 점수를 받은 수포자만 반환해야 하는 것과
가장 높은 점수를 받은 수포자가 2명 이상일 경우 오름차순으로 배열에 넣어 반환해야 한다는 것이다.

나는 가장 높은 점수를 받은 수포자를 찾아 반환할 list에 넣었다. 또한 가장 높은 점수를 받은 수포자가 여럿이면 list에 오름차순으로 넣도록 작성하였다.

1
2
3
4
5
6
7
8

int max = Math.max(Math.max(cnt1,cnt2),cnt3);
ArrayList<Integer> list = new ArrayList<>();
if(cnt1 == max) list.add(1);
if(cnt2 == max) list.add(2);
if(cnt3 == max) list.add(3);

int[] answer = list.stream().mapToInt(i->i).toArray();        
return answer;

마지막으로 해당 list를 Array로 변환하여 answer에 담아 반환하였다.


작성 코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // int[] arr = {1,3,2,4,2};
        int[] arr = {1,2,3,4,5};
        long start = System.currentTimeMillis();
        solution(arr);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int[] solution(int[] answers) {
        String[] arr1 = {"1","2","3","4","5"};
        String[] arr2 = {"2","1","2","3","2","4","2","5"}; 
        String[] arr3 = {"3","3","1","1","2","2","4","4","5","5"};      
        
        ArrayList<String> list1 = new ArrayList<>(Arrays.asList(arr1));
        ArrayList<String> list2 = new ArrayList<>(Arrays.asList(arr2));
        ArrayList<String> list3 = new ArrayList<>(Arrays.asList(arr3));
        
        int size1 = list1.size();
        int size2 = list2.size();
        int size3 = list3.size();
        
        for(int i=0; i<=answers.length; i++) {
            if(i>size1) list1.add(list1.get(i-size1-1));
            if(i>size2) list2.add(list2.get(i-size2-1));
            if(i>size3) list3.add(list3.get(i-size3-1));
        }
        
        int cnt1 = 0;
        int cnt2 = 0;
        int cnt3 = 0;
        
        for(int i=0; i<answers.length; i++) {
            if(answers[i] == Integer.parseInt(list1.get(i))) cnt1++;
            if(answers[i] == Integer.parseInt(list2.get(i))) cnt2++; 
            if(answers[i] == Integer.parseInt(list3.get(i))) cnt3++;
        }
        
        int max = Math.max(Math.max(cnt1,cnt2),cnt3);
        ArrayList<Integer> list = new ArrayList<>();
        if(cnt1 == max) list.add(1);
        if(cnt2 == max) list.add(2);
        if(cnt3 == max) list.add(3);
        
        int[] answer = list.stream().mapToInt(i->i).toArray();        
        return answer;
    }
}

회고

  • 평소에 반복문을 통해 문제를 많이 푸는데 완전 탐색 알고리즘과 관련지어 생각해볼 수 있었고, 완전탐색 기법을 어떻게 활용해야 효율적일지 공부할 수 있었다.

You may also enjoy