[프로그래머스] Day12 2의 영역 자바

문제 

 

 

풀이 

class Solution {
    public int[] solution(int[] arr) {
        int[] answer = {};
        int start_index=-1;
        int end_index=-1;
        
        // start_index값 찾기
        for(int i=0;i<arr.length;i++){
            if(arr[i]==2) {
                start_index=i;
                end_index=start_index; // 2가 배열에 하나인 경우를 고려
                break;
            }
        }
        
        // 빈 배열인지 확인
        if(start_index==-1) return new int[] {-1};
        
        
        // end_index값 찾기
        for(int i=start_index+1;i<arr.length;i++){
            if(arr[i]==2){
                end_index=i;
            }
        }
        
        // answer 배열 생성
        int answer_length = end_index - start_index + 1;
        answer = new int[answer_length];
        
        for(int i=start_index;i<=end_index;i++){
            int begin=i-start_index;
            answer[begin]=arr[i]; 
        }
        
        return answer;
    }
}

 

처음 이 문제를 봤을때 생각했던건 처음 2가 나온 인덱스를 체크하고, 마지막으로 2가  나오는 인덱스를 체크하여 두 인덱스 값에 해당하는 원소값들을 정답 배열에 넣으면 되겠다고 생각했다. 

그래서 처음 2가 나온 곳을 가리기는 포인터와 마지막으로 2가 나온 곳을 가리키는 포인터 두개가 있으면 문제가 쉽게 풀리겠다고 생각하여 투 포인터로 풀어야 겠다고 생각했다. 

---

참고 코드 

 

방법1 

import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        int[] answer = {};
        int start = -1;
        int end = -1;

        for(int i=0;i<arr.length;i++){
            if(arr[i]==2){
                if(start==-1){
                    start = i;
                }
                end = i;
            }
        }

        if(start==-1){
            answer = new int[]{-1};
        }else{

            answer = Arrays.copyOfRange(arr,start,end+1);
        }



        return answer;
    }
}

 

 

방법2

import java.util.*;
class Solution {
    public ArrayList<Integer> solution(int[] arr) {
        ArrayList<Integer> answer = new ArrayList<Integer>();
        int start = -1;
        int end = -1;
        for(int i = 0; i<arr.length; i++){
            if(arr[i]==2){
                start = i;
                break;
            }
        }
        for(int i = arr.length-1; i>=0; i--){
            if(arr[i]==2){
                end = i;
                break;
            }
        }
        if(start==-1 && end==-1){
            answer.add(-1);
        } else{
            for(int i = start; i<=end; i++){
                answer.add(arr[i]);
            }
        }

        return answer;
    }
}

 

 

처음에 나오는 2를 가리키는 인덱스를 어떻게 고정해야할지에 대한 고민이 있었는데 방법1의 코드를 보면 start==-1 라는 조건을 설정하여 처음 2가 나온 인덱스의 위치를 저장하고, 이후에 원소값이 2인 인덱스의 경우에는 start의 값이 -1 이 아니므로 end 값에 저장된다. 

계속해서 배열의 크기 만큼 반복문을 수행하면서 end의 값이 새롭게 갱신되어 반복문이 종료된 시점에 end에는 마지막에 나온 2의 인덱스 위치가 저장되게 된다. 

 

물론 방법2의 코드 처럼 start와 end의 값을 서로 다른 for문을 이용해서 각각 구해도 시간 복잡도는 동일하겠지만, 위의 조건식 하나로 하나의 for문에서 두 값을 결정할 수 있어서 해당 풀이가 좋다고 생각했다. 

 

또한 나의 경우 end 지점을 결정할때 (처음 2가 나온 인덱스 다음 부터 ~ 배열의 끝 까지) 라고 범위를 설정하고 end값을 구했었는데, end의 의미를 생각해보면  end 는 가장 마지막에 나오는 2의 인덱스 값을 저장하면 된다. 

그렇기 때문에 앞에서 부터 값을 찾는것이 아닌 배열의 끝 부터 시작하여 하나씩 값을 내려오는게 더 빨리 end값을 찾는 길이다. 

그래서 두번째 코드에서 이러한 부분을 담고 있어서 배울점이 있는 코드라 넣어봤다.