[프로그래머스] Cos Pro 1급 모의고사, 지그재그 수열

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

1. 문제
2. 풀이

---

문제

문제 설명

수열 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 해주세요.

 

예제

 

예제 설명

예제 #1
문제 예제와 같습니다.

예제 #2
[2, 1, 10, 6, 9, 7, 8]이 부분 수열 중 가장 긴 지그재그 수열입니다.

예제 #3
부분 수열중 지그재그 수열이 없습니다.

---

풀이

풀이 코드 및 해설

INC = 0
DEC = 1

# 2번째로 사용될 함수
def func_a(arr):
    length = len(arr)
    # 마킹된 리스트의 길이를 측정
    ret = [0 for _ in range(length)]
    # 마킹된 리스트의 길이와 동일한 return할 리스트 생성
    # 마킹된 리스트를 순회하면서 지그재그 배열 검열하여 ret 리스트에 저장
    ret[0] = 1
	# ret 리스트의 첫 번째 요소를 0으로 지정
    for i in range(1, length):
    	# 첫 번째 요소를 제외한 리스트의 길이만큼 반복
        if arr[i] != arr[i-1]:
			# 만약 마킹된 리스트의 요소(INC, DEC)가 서로 다르다면
            ret[i] = ret[i-1] + 1
            # 지그재그 배열인 경우 길이를 기록
            # 첫 번째 요소가 1이기 때문에 다른 경우가 1번이면 2가 저장
            # 다른 경우가 2번이면 3이 저장
        else:
            ret[i] = 2
            # 마킹된 리스트가 없을 경우 2를 기록
    return ret
    # 마킹된 리스트(arr)의 길이를 저장한 ret 리스트를 반환

# 1번째로 사용될 함수
def func_b(arr):
    global INC, DEC
    # 전역 변수를 사용하기 위해 INC, DEC 선언
    length = len(arr)
    ret = [0 for _ in range(length)]
    # arr 리스트의 길이와 동일한 ret 리스트 생성
    ret[0] = -1
    # ret 리스트의 첫 번째 요소를 -1로 지정
    for i in range(1, length):
    	# 첫 번째 요소를 제외한 리스트의 길이만큼 반복
        if arr[i] > arr[i-1]:
        # 만약 현재 배열의 요소가 전 배열의 요소보다 크다면
            ret[i] = INC
			# INC 마킹
        elif arr[i] < arr[i-1]:
        # 만약 현재 배열의 요소가 전 배열의 요소보다 작다면
            ret[i] = DEC
            # DEC 마킹
    return ret # 마킹된 ret 리스트를 반환
	# 01010101 식으로 마킹 될 것임.

# 3번째로 사용될 함수
def func_c(arr):
# 인수로 지그재그 배열의 길이를 저장하고 있는 리스트를 전달받음
    ret = max(arr)
    # 전달받은 리스트 중 제일 큰 값을 ret에 저장
    if ret == 2:
        return 0
       	# 만약 지그재그 배열의 최대 길이가 2라면 0 반환
        # 문제상에서 3 이상의 길이부터 인정한다고 기재되어있음.
    return ret
    # 아니라면 저장되어 있는 값 그대로 반환

def solution(S):
    check = func_b(S)
    dp = func_a(check)
    answer = func_c(dp)
    return answer

---