Cos Pro 1급 - 샘플 문제 풀이 2차 5번 (배열: Index Out of Bounds피하기)

문제 지문 #5

자연수가 들어있는 배열이 있습니다. 이 배열에서, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 구하려 합니다. 단, 바로 전 숫자와 현재 숫자가 같은 경우는 증가한 것으로 보지 않습니다.

예를 들어 배열에 순서대로 [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]가 들어있는 경우, [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가한 가장 긴 구간이며, 길이는 4입니다.

자연수가 들어있는 배열 arr가 매개변수로 주어질 때, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 하도록 solution 메서드를 완성해주세요.

---

매개변수 설명

자연수가 들어있는 배열 arr가 solution 메소드의 매개변수로 주어집니다.

• arr의 길이는 2 이상 200,000 이하입니다.
• arr의 원소는 1 이상 1,000,000 이하의 자연수입니다.

---

return 값 설명

숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 해주세요.

• 길이가 2 이상인 증가하는 구간이 없다면 1을 return 해주세요.

---

예시

arr	return
[3, 1, 2, 4, 5, 1, 2, 2, 3, 4]	4

 

예시 설명

숫자 [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가하는 가장 긴 구간이며, 길이는 4입니다.

현재 숫자가 바로 이전 숫자와 같은 경우에는 증가했다고 보지 않습니다. [1, 2, 2, 3, 4]가 들어있는 구간은 [2, 2]가 연속해서 증가한 부분이 아니므로, [1, 2]가 들어있는 구간과 [2, 3, 4]가 들어있는 구간으로 나누어야 합니다.

 

혼자 풀이

메서드 전체를 완성하는 문제입니다. 난이도는 높지 않았습니다. 10분 정도 걸렸네요.
for문으로 배열의 원소를 비교할 때 첫번째 원소부터 시작하면
"ArrayIndexOutOfBoundsException: Index X out of bounds for length X" 에러를 만날 수 있는데,
이것을 피하도록 배열을 Index 0이 아니라 index 1부터 시작하면 되는 문제였습니다.

/**********************************************
         연속 증가하는 숫자의 개수 구하기
 **********************************************/
// 다음과 같이 import를 사용할 수 있습니다.

class MySolution {
    public int solution(int[] arr) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
        int tmp=1; //구간별 연속 증가 카운트 저장

        for(int i=1;i<arr.length;++i){ // 0부터 뒤로 비교하면 out of index 발생하므로 1부터 앞으로 비교
            if(arr[i-1]<arr[i]){
                tmp++; //뒤가 크면 tmp 증가
                if(answer<tmp) answer=tmp; //answer보다 tmp가 크면 tmp를 answer에 저장
            }else tmp=1; //연속 증가가 끝나면 tmp를 1로 초기화
        }
        return answer;
    }

    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        MySolution sol = new MySolution();
        int[] arr = {3, 1, 2, 4, 5, 1, 2, 2, 3, 4};
        int ret = sol.solution(arr);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
    }
}

 

정답

임시 배열인 dp를 만들고 1로 모두 초기화 한 후에 arr를 탐색하면서 연속 증가하는 경우에 dp의 값도 증가시켰습니다.
그리고 연속증가가 끝나면 dp에 저장된 값과 answer를 비교해서 가장 큰 수를 answer에 저장합니다.
좀 복잡한거 같네요.

class CorrectSolution {
    public int solution(int[] arr) {
        int dp[] = new int[arr.length];
        for(int i = 0; i < dp.length; ++i)
            dp[i] = 1;
        for(int i = 1; i < arr.length; ++i)
            if(arr[i] > arr[i-1])
                dp[i] = dp[i-1] + 1;
        int answer = 0;
        for(int i = 0; i < arr.length; ++i)
            answer = Math.max(answer, dp[i]);
        return answer;
    }
}

 

#첨부파일

프로젝트 파일 전체를 첨부합니다.
Solution 이 문제, CorrectSolution 이 정답, MySolution이 제가 푼 것입니다.
"Project from existing sources..." 메뉴에서 불러다 쓰시면 됩니다.

SecondQuestion5.zip

0.01MB

출처: https://www.ybmit.com/cos_pro/cos_pro_r_test.jsp