[200916] 모의고사 - 완전탐색(level1)

level2 카카오의 단체사진찍기 문제에서 완전탐색을 구현하는 법을 완전 잊어버렸다!!ㅠㅠ

그래서 전에 풀어봤던 완전탐색 문제들을 먼저 풀어보기로 했다.

 

1. 문제 이해

- 3명의 수포자가 일정한 규칙에 따라 문제를 찍음

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 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, ...   ▶ {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, ...   ▶ {3, 3, 1, 1, 2, 2, 4, 4, 5, 5} 반복

- answers(각 문제의 정답)이 주어졌을 때 문제를 많이 맞힌 사람을 answer에 담아 return
(단, 여러명이면 오름차순으로 작성)

 

 

2. 전략

(1) 수포자들이 찍는 방식 : arr1, arr2, arr3에 배열을 만듦

 

(2) 완전 탐색

answers와 arr1, arr2, arr3를 각각 하나씩 비교해서 정답 개수를 카운트한다!

- int getAnswer(int[] arr, int[] answers) 함수

: answers[i]와 arr[i % size]가 같다면 result++

 

(3) 결과 출력

- max값 찾기 : result 배열 for문

- max값을 가지는 목록 담기 : result 배열 for문 → ArrayList에 담기(사이즈를 모르기 때문에)

- ArrayList → int 배열 : ArrayList for문

 

 

3. 참고사항

(1) ArrayList 의 함수

- add(E e) : 요소 추가

- get(index) : index의 요소 반환

 

(2) max값 찾는 과정 : 요소가 적으므로(3개뿐) Math.max(int a, int b)도 충분히 사용 가능

int max = Math.max(getAnswer(arr1, answers), getAnswer(arr2, answers), getAnswer(arr3, answers));

(3) ArrayList를 int 배열로 바꾸는 방법 : stream을 이용할 수 있음

- stream() : 스트림 생성

- mapToInt : 스트림 중개 연산(변환)

- intValue() : Wrapper에서 base로 언박싱

- toArray() : 스트림 최종연산(배열로 변환)

return array.stream().mapToInt(i -> i.intValue()).toArray();

 

 

4. 코드

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        int[] arr1 = {1,2,3,4,5}; //5
        int[] arr2 = {2,1,2,3,2,4,2,5}; //8
        int[] arr3 = {3,3,1,1,2,2,4,4,5,5}; //10
        int[] result = {getAnswer(arr1, answers), getAnswer(arr2, answers), getAnswer(arr3, answers)};
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int r : result){
            max = max > r ? max : r;
        }
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 0; i < result.length; i++){
            if(result[i] == max)   arr.add(i+1);
        }
        answer = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++){
            answer[i] = (int)arr.get(i);
        }
        return answer;
    }
    int getAnswer(int[] arr, int[] answers){
        int size = arr.length;
        int result = 0;
        for(int i = 0; i < answers.length; i++){
            if(answers[i] == arr[i%size])   result++;
        }
        return result;
    }
}