Cos Pro 1급 - 샘플 문제 6차 8번 - 지그재그 수열 구하기

문제 지문 #8

수열 S가 주어질 때, 이 수열의 연속된 부분 수열 중 지그재그 수열 길이의 최댓값을 구하려 합니다.
지그재그 수열이란 첫 번째 원소부터 인접한 원소의 차이가 증가 → 감소 → 증가 → 감소... 혹은 감소 → 증가 → 감소 → 증가... 순으로 나타나는 수열을 말합니다. 단, 수열의 길이는 3 이상이어야 합니다.
예를 들어 수열이 [ 2, 5, 7, 3, 4, 6, 1, 8, 9]인 경우, 연속된 부분 수열 [5, 7, 3, 4]가 부분 수열 중 가장 긴 지그재그 수열이 됩니다.
부분 수열 중 가장 긴 지그재그 수열의 길이를 구하기 위해 다음과 같이 프로그램 구조를 작성했습니다.

1. 각 숫자가 바로 이전 숫자보다 증가했는지, 혹은 감소했는지 표시한 배열을 만듭니다.
  1-1. "증가"는 "INC", "감소"는 "DEC"로 표시합니다.
  1-2. 첫 번째 숫자는 증가도, 감소도 하지 않았다는 의미에서 -1로 표시합니다.

2. 1단계에서 만든 증가, 감소 배열을 이용해 각 숫자를 마지막으로 하는 지그재그 수열 중 가장 긴 것의 길이를 담은 배열을 만듭니다.
  2-1. 바로 전 숫자가 "증가"이고 현재 숫자가 "감소"이거나, 전 숫자가 "감소"이고 현재 숫자가 "증가"이면,
       현재 숫자를 마지막으로 하는 지그재그 수열 중 가장 긴 것의 길이는 (바로 전 숫자를 마지막으로 하는 지그재그 수열중 가장 긴 것의 길이 + 1)입니다.
  2-2. 그렇지 않으면 현재 숫자를 마지막으로 하는 지그재그 수열 중 가장 긴 것의 길이는 2입니다.
  2-3. 단, 첫 번째 숫자의 길이는 1로 초기화합니다.

3. 2단계에서 구한 배열에 담긴 값 중 최댓값이 부분 수열 중 가장 긴 지그재그 수열의 길이입니다.
  3-1. 만약 최댓값이 2라면 0을 return 합니다.
  3-2. 그 외에는 최댓값을 return 합니다.

수열이 담긴 배열 S가 매개변수로 주어질 때, 길이가 3 이상인 부분 수열 중 가장 긴 지그재그 수열의 길이를 return 하도록 solution 메서드를 작성하려 합니다. 위 구조를 참고하여 코드가 올바르게 동작할 수 있도록 빈칸에 주어진 func_a, func_b, func_c 메서드와 매개변수를 알맞게 채워주세요.

---

#####매개변수 설명
수열이 담긴 배열 S가 solution 메서드의 매개변수로 주어집니다.

• S의 길이는 3 이상 100 이하입니다.
• S의 원소는 1 이상 100 이하인 자연수이며, 같은 숫자가 중복해서 나타나지 않습니다.

---

#####return 값 설명
길이가 3 이상인 부분 수열 중 가장 긴 지그재그 수열의 길이를 return 해주세요.

• 만약 지그재그 수열이 없다면 0을 return 해주세요.

---

#####예제

[2, 5, 7, 3, 4, 6, 1, 8, 9]	4
[4, 3, 2, 1, 10, 6, 9, 7, 8]	7
[1, 2, 3, 4, 5]	0

#####예제 설명
예제 #1
문제 예시와 같습니다.
예제 #2
[2, 1, 10, 6, 9, 7, 8]이 부분 수열 중 가장 긴 지그재그 수열입니다.
예제 #3
부분 수열 중 지그재그 수열이 없습니다.

728x90

 

혼자 풀이

빈칸을 채우는 문제입니다. 연습 삼아 주어진 문제 지문에 따라 전체 코드를 한번 짜보았습니다.
특별한 알고리즘이 사용된 것은 아니지만, 주어진 배열의 추가 특성을 나타내기 위해 같은 크기의 배열을 사용하는 문제는 자주 나왔었습니다.

import java.util.*;

public class Main {
    //1.숫자가 증가하는지 감소하는 지를 표시한 배열 만들기
    String[] incDecCheck(int[] S) {
        String[] check = new String[S.length];

        check[0]="-1";

        for(int i=1;i<S.length;i++) {
            if(S[i-1]>S[i]) check[i]="DEC";
            else check[i]="INC";
        }		
        return check;		
    }
	
	//2.지그재그 수열의 길이를 저장하는 메서드
    int[] zigZagCnt(String[] check) {
        int[] dp = new int[check.length];
        int k=0; //dp 배열 인덱스
        int len=1; //dp 배열의 길이

        for(int i=0;i<check.length-1;i++) {			
            if(!check[i].equals(check[i+1])) {
                len++;				
            }else if(len<3) {
                continue;
            }else{
                dp[k]=len;				
                k++; //지그재그 수열의 길이를 저장하는 배열 dp의 인덱스
                len=1;
            }			
        }
        //마지막 지그재그 수열의 길이를 저장
        dp[k]=len;		
        k++;

        return  dp;
	}
	//3. 가장 긴 지그재그 수열의 길이를 반환하는 함수
	public int zigZagMax(int[] dp){
		Arrays.sort(dp); //배열을 정렬하여 최대값 찾기
		
		if(dp[dp.length-1]==2) return 0; //최대값이 2이면 0을 반환
		else return dp[dp.length-1]; //그외는 모두 최대값을 반환
	}
	
	public int solution(int[] S) {
	    //1. 각 숫자가 바로 이전 숫자보다 증가했는지, 혹은 감소했는지 표시한 배열을 만듭니다.
		String[] check = incDecCheck(S);
		//2. 1단계에서 만든 배열을 이용해 각 숫자를 마지막으로 하는 지그재그수열 중 가장 긴 것의 길이를 담은 배열을 만듭니다.
		int[] dp = zigZagCnt(check);
		//3. 2단계에서 구한 배열에 담긴 값 중 최댓값이 부분 수열 중 가장 긴 지그재그 수열의 길이이며 최대값을 return(최대값이 2일때는 0)
		int answer = zigZagMax(dp);

		return answer;
	}

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

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

        int[] S2 = {4, 3, 2, 1, 10, 6, 9, 7, 8};
        int ret2 = sol.solution(S2);

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

        int[] S3 = {1, 2, 3, 4, 5};
        int ret3 = sol.solution(S3);

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

 

정답

제가 작성한 코드와는 차이가 큽니다. 우선 INC와 DEC를 저는 지문에 주어진대로 String으로 썼는데, 정답에서는 final 변수로 선언해서 사용했습니다.

그리고,  저는 배열을 지그재그 수의 길이를 구한 뒤 담는 것만 생각했는데, 문제에서는 dp [] 배열에 바로 계산을 하였습니다. 그 외에는 전반적인 알고리즘은 유사합니다.

class Main {
    final int INC = 0;
    final int DEC = 1;
    //2. 지그재그 수열의 길이를 저장하는 메서드
    	int[] func_a(int[] arr){
        int length = arr.length;
        int[] ret = new int[length]; //지그재그 수열의 길이를 저장할 배열
        ret[0] = 1;
        for(int i = 1; i < length; i++){
            if(arr[i] != arr[i-1])
                ret[i] = ret[i-1] + 1; //지그재그가 유지되면 ret의 해당 칸에 수열의 길이를 저장
            else
                ret[i] = 2; //지그재그가 끝나면 ret[i]를 2로 초기화
        }
        return ret;
    }
    //1. 숫자가 증가하는지 감소하는 지를 표시한 배열 만들기
    int[] func_b(int[] arr){
        int length = arr.length;
        int[] ret = new int[length];
        ret[0] = -1; //첫 번째 숫자는 -1
        for(int i = 1; i < length; i++){
            if(arr[i] > arr[i-1]) //뒤가 크면 INC
                ret[i] = INC;
            else if(arr[i] < arr[i-1])  //앞이 크면 DEC
                ret[i] = DEC;
        }
        return ret;
    }
    //3. 가장 긴 지그재그 수열의 길이를 반환하는 함수
    int func_c(int[] arr){
        int length = arr.length;
        int ret = 0;
        for(int i = 0; i < length; i++) //최대값 찾기
            if(ret < arr[i])
                ret = arr[i];
        if(ret == 2)  //최대값이 2이면 0을 반환
            return 0;
        return ret;
    }
    
    public int solution(int[] S) {
        int[] check = func_b(S);
        int[] dp = func_a(check);
        int answer = func_c(dp);
        return answer;
    }

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)