Codility - Flags 문제풀이

 

맨 아래 코드에 정답 나와있습니다.

 

 

==============아래 코드들은 성공하기까지의 과정 =============

처음 봤을때, 문제가 이해가 잘 안되는 것이 가장 큰 문제!

 

그래도 해석해서 처음 푼 풀이방법

정확도: 40%ㅜㅜ

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    #print(A)
    
    if len(A) <= 2:
        return 0
    
    pre_peak_idx = 0
    current_peak_num = 0
    result_peak_num = 0
    peak_idx_arr = []
    
    for i in range(1,len(A)-1):
        #print(peak_idx_arr)
        # 만약 피크라면
        if A[i-1] < A[i] and A[i+1] < A[i]:
            # 최초 피크라면
            if current_peak_num == 0:
                current_peak_num += 1
                peak_idx_arr.append(i)
            # 피크가 2개 이상이라면
            else:
                # 조건에 부합하는지
                peak_idx_arr.append(i)
                for j in range(len(peak_idx_arr)-1,0,-1):
                    if abs(peak_idx_arr[j]-peak_idx_arr[j-1]) < (current_peak_num+1):
                        del peak_idx_arr[j-1]
                        break
                        
                if len(peak_idx_arr) == current_peak_num:
                    continue
                else:
                    current_peak_num += 1
                    
            
    #print(peak_idx_arr)
    
    
    return len(peak_idx_arr)
                    
            
            
    pass

 

다시 풀어봐야겠다..!! 화이팅!

 

 

다시 풀어보았다

 

정확도: 66% (peak의 개수가 많아지는 상태에서는 다수의 Timeout 에러 발생)

 

- 코드 -

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) < 2:
        return 0
    
    peak_arr = []
    
    for i in range(1,len(A)-1):
        # 피크라면
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_arr.append(i)
            
    #print(peak_arr)
    
    length_peak_arr = len(peak_arr)
    
    if len(peak_arr) == 0:
        return 0
    
    for j in range(len(peak_arr),0,-1):
        current_index = 0
        num_of_peak = 1
        
        for i in range(1,len(peak_arr)):
            if abs(peak_arr[i] - peak_arr[current_index]) < j:
                continue
            else:
                num_of_peak += 1
                current_index = i
            
            if num_of_peak == j:
                return j
            
            
    return num_of_peak
    
    
    pass

 

 

이중 for문은 역시 안좋다

 

대충 감을 잡은 거 같다.

다시 풀어봐야겠다!!

 

 

 

임시 저장 코드

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) < 2:
        return 0
    
    num_peaks = 0
    peak_arr = []
    
    for i in range(1, len(A)-1):
        # 피크인 경우
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peak_arr.append(i)
    
    print(peak_arr)
    
    if len(peak_arr) == 0:
        return 0
    
    if len(peak_arr) == 1:
        return 1
    
    peak_cnt_ = 1
    peak_num_ = 1
    
    for j in range(len(peak_arr),1,-1):
        
        for i in range(len(peak_arr)):
            
            if peak_arr[i] >= peak_j*j:
                peak_num_ += 1
                peak_cnt_ += 1
            
            if peak_arr[i] >= peak_arr[0]+j*peak_cnt_:
                peak_num_ += 1
                peak_cnt_ += 1
            if peak_num_ == j:
                return peak_num_
           
    
    pass

 

 

7월6일 재도전

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    if len(A) <= 2:
        return 0
    
    peaks = []
    
    for i in range(1,len(A)-1):
        if A[i-1] < A[i] and A[i+1] < A[i]:
            peaks.append(i+1)
            
    if len(peaks) == 1:
        return 1
        
    if len(peaks) == 0:
        return 0
    

    num = len(peaks)
    
    try:
        for i in range(1,num):
            j = 1
            if len(peaks) < i+1:
                break
            while j < i+1:
                if peaks[j] >= peaks[j-1]+(i+1):
                    j += 1
                else:
                    del peaks[j]
    except:
        return len(peaks)
        
    return len(peaks)
            
            
    
            
            
            
            
            

 

 

====================================================================================

 

잠깐 코딩을 쉬었다가 다시 시작한다.

8.12일

 

 

 

66%의 코드(다수의 Time error 발생)

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    peak_arr = []
    
    for i in range(1,len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_arr.append(i)
            
    print(peak_arr)
    
    result_peak_num = 0
    
    if len(peak_arr) == 1:
        return 1
    else:
        start_peak_num = 1
        while start_peak_num < len(peak_arr):
            # 몇개의 봉우리를 찾아야하는지
            start_peak_num += 1
            # 기본 1로 시작함(이미 하나 찾은거로 가정)
            current_peak_num = 1
            s = peak_arr[0]
            # 1개 찾고, 2개 찾고 ..
            for i in range(1,len(peak_arr)):
                e = peak_arr[i]
                
                if abs(e-s) >= start_peak_num:
                    # 여기가 다시 시작이 된다
                    s = e
                    current_peak_num += 1
                    
                    if current_peak_num == start_peak_num:
                        result_peak_num = max(result_peak_num,start_peak_num)
            
    #print(result_peak_num)
    
    return result_peak_num
    
    pass

 

==============아래는 성공한 코드 =============

 

8월 21일 코드

 

드디어 풀었다!!

 

물론 구글링을 조금 하긴 했지만, 

어느정도 혼자 힘으로 풀 수 있었다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    
    # peak가 있는 인덱스만 모아놓은 리스트 초기화
    peak_arr_list = []
            
    
    # peak가 있는 인덱스만 모아놓은 리스트 값 채워넣기
    for i in range(1,len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_arr_list.append(i)
    
    # 만약 peak가 0개라면 return 0
    if len(peak_arr_list) == 0:
        return 0
    
	# 만약 peak가 1개라면 return 1
    if len(peak_arr_list) == 1:
        return 1       
        
    # peak_arr_list 출력 테스트
    #print(peak_arr_list)
    
    # peak_arr 라는 리스트 초기화
    peak_arr = [0]*len(A)
    peak_arr[0] = -1
    peak_arr[-1] = -1
    peak_idx = -1
    
    # peak_arr 값 채워넣기
    for i in range(len(A)-2,0,-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peak_idx = i
            
        peak_arr[i] = peak_idx
    
	# peak_arr 출력 테스트
    #print(peak_arr)
    
    max_num_flag = -1
    
    # 1에서 len(A)까지 반복 -> 최대 peak 개수는 len(A)가 될 수 있음
    for i in range(1,len(peak_arr_list)+1):
    
    	# index는 매 loop마다 1값으로 초기화
        index = 1
        
        # num_flag는 매 loop마다 peak 조건을 만족하면 +1씩 해줌
        num_flag = 0
        
        # num_flag가 loop보다 작으면 반복 -> 같아지면 해당 num_flag는 가능한 개수이다.
        while num_flag < i:
            try:
                if peak_arr[index] != -1:
                    num_flag += 1
                    index = peak_arr[index] + i
                else:
                    return max_num_flag
            except:
                return max_num_flag
        
        # 만약 이전 loop의 peak 개수보다 크면 max_num_flag 초기화
        max_num_flag = max(num_flag,max_num_flag)
                
    # for 끝나면 가장 최대 peak 개수를 의미하는 max_num_flag 반환
    return max_num_flag
                
    pass

 

 

해당 내용을 풀이해주는 영상을 만들었습니다.

 

어려우신 분들은 보시면 도움이 될 것 같습니다!!(하단 링크 참조)

 

https://www.youtube.com/watch?v=8DvYb9lVcRM&feature=youtu.be