[JAVA] 모의고사 - DFS

찍을 때는 답안지 번호의 비율을 세어 봅시다 (Photo by Arthur Krijgsman)

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

코딩테스트 연습 - 모의고사

 

생각과정

- 3가지 패턴별로 답안을 작성한다

- DFS 함수를 만들어 완전탐색 알고리즘을 재사용한다

- 재귀를 사용해 문제가 많을수록 시간이 오래 걸리는 단점이 있다.

=> 채점할 때 효율성 검사를 안하는걸 보니 상관없는듯?

 

구현

import java.util.ArrayList;
class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        
        ArrayList arr = new ArrayList();
        
        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 max = 0;
        int sum = 0;
        for(int i=0;i<3;i++){
            sum = cal(answers, patterns[i], 0, 0);
            if(max<sum){
                //최댓값 갱신
                max = sum;
                arr = new ArrayList();
                arr.add(i+1);
            }
            else if(max == sum){
                //추가
                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;
    }
    
    public int cal(int[] answers, int[] pattern, int index, int sum){
        if(index >= answers.length){
            //채점 종료
            return sum;
        }
        int num;
        //비교할 패턴값을 정해준다.
        if(index < pattern.length){
        	//패턴을 처음 순회할 때 패턴 인덱스는 정답 인덱스와 동일함.
            num = index;
        }
        else{
        	//인덱스를 패턴의 길이로 나눈 나머지는 비교할 패턴의 인덱스가 된다.
            num = index%pattern.length;
        }
        if(answers[index] == pattern[num]){
            //정답
            return cal(answers, pattern, index+1, sum+1);
        }
        else{
            //오답
            return cal(answers, pattern, index+1, sum);
        }
    
    }
}

DFS를 사용해 완전탐색 구조를 만들었다. ArrayList를 만든 이유는 answers의 개수에 영향을 받지 않기 때문.

 

ArrayList to Array

처음에는 ArrayList의 toArray 메소드를 사용하려고 했지만 int와 Integer의 형변환 충돌 때문에 for문으로 대신했다. 

toArray는 ArrayList를 Array로 만들어 주는 메소드인데, 인자로 아무것도 넣지 않으면 Object Array가 반환되고, 특정 자료형의 배열이 넘어가면 그 배열에 내용을 저장한다. 이때 ArrayList에 자료형을 선언했을 경우 주의해서 인자를 넘겨야 한다.

ArrayList는 Integer로 선언하고, Array는 int로 선언하면 Array에 ArrayList를 담을 때 primitive인 int와 객체인 Integer가 충돌하기 때문에 에러가 발생한다. 참고로, primitive 자료형은 객체가 아니다. 대신 ArrayList를 int로 선언해 보았는데, int는 generic의 인자로 사용할 수 없어서 실패했다. 답으로 넘겨야 할 리턴값이 int Array라 for문에 ArrayList.get()을 넣어 저장하는 방식을 사용했다. ArrayList는 오랜만이라 이 부분에서 많이 헤멨던 것 같다.

 

결과

통과! 메모리가 어마무시하다.

참고

https://stackoverflow.com/questions/960431/how-to-convert-listinteger-to-int-in-java

How to convert List to int[] in Java?