Henry's Algorithm

처음에 봤을 때,

문제를 이해하는데는 그렇게 어렵지 않았다.

그냥 약수 구해서 두 값 더해서 *2 해주면 되는데,

그 중 최소값을 찾는 문제구나 라는 생각만 하였고 접근했다.

첫 시도했을 때는 아래의 코드와 같다.

그런데 80%의 정확도만 나왔다.

그 원인을 살펴보니 큰 수에 대해서는 for문에서 i 가 일일히 +1씩 되면서 진행되는 부분이

성능이 좋지 않음을 알 수 있었다.(Timeout Error 발생ㅜㅜ)

그래서 for i in range(2,int(i/2)): 처럼 나누기 2를 해보기도 하고 그랬는데,

역시나 마찬가지였다.

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

def solution(N):
    # write your code in Python 3.6
    
    check = N
    max_perimeter = 2*(1+(N))
    
    for i in range(1,N+1):
        
        # 반복되는 값이 가장 최근의 몫의 값보다 커지면 그만
        if i >= check:
            break
        
        # 0으로 나눠지면 약수
        if N%i == 0:
            max_perimeter = min(max_perimeter,2*(i+(N/i)))
            check = N/i
    
    return int(max_perimeter)
    
    pass

잠깐 들었던 생각이

이전에 풀었던 Codility 문제 중에 CounterFactors라는 문제에서도 약수를 구하는 문제였는데,

조금 다르게 접근했던 것 같은 기억이 있어서 찾아보았다.

https://datacodingschool.tistory.com/69

그리고 그 결과 같은 방법으로 For 문을 돌리고 100% 정확도를 얻을 수 있었다.

약수를 구하는 문제에는 이제 i*i 라는 방식을 사용해주어야겠다.

두번째 시도했을 때 코드

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

def solution(N):
    # write your code in Python 3.6
    
    max_perimeter = 2*(1+(N))
    number_iter = 1
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            max_perimeter = min(max_perimeter,2*(number_iter+(N/number_iter)))
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        max_perimeter = min(max_perimeter,4*number_iter)
    
    return int(max_perimeter)
    
    pass
   

이번주 토요일에 이베이 코딩테스트,

다음주 토요일에 LG U+ 코딩테스트가 있는데,

매일 꾸준히 3문제씩 공부해야겠다.

오늘의 목표

프로그래머스 문제 3문제 정도 풀어보기!

프로그래머스 - 완주하지 못한 선수 문제풀이 를 풀어보았다.

set이라는 자료형을 사용하면 차집합을 낼 수 있기 때문에

결과 = list(set(input1) - set(input2))

* 형태로 풀어주려고 했다가 동명이인일 경우 set에서 하나만 남기고 제거해버리기 때문에

동명이인인 경우를 다시 생각해주었다.

다 풀고 나서 알게된 사실은

위의 *동명이인의 경우에는 Counter 자료형을 통해 풀어줄 수 있다고 한다.(Set 대신 Counter 사용)

def solution(participant, completion):
    
    # 미완주자가 동명이인이 아닐 경우, 차집합으로 생각하기
    complement = list(set(participant) - set(completion))
    
    if len(complement) != 0:
        return complement[0]
    
    # 동명이인일 경우, 정렬하여 다른 시점에서 반환해주기(미완주자 1명이므로)
    participant = sorted(participant)
    completion = sorted(completion)
    
    for i in range(len(participant)):
        if participant[i] != completion[i]:
            return participant[i]
    
    answer = ''
    return answer

나와 같은 방법으로 푸는 사람들도 많이 있었고,

Counter와, zip 이라는 클래스, 명령어를 사용해서 푸는 사람들도 있었다.(하단의 링크 참조)

https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=python3

P.S 혹시 코딩테스트 준비가 어려우신 분들은 저의 알고리즘 강의를 참고해주시기 바랍니다!!ㅎㅎ

https://www.youtube.com/channel/UCYYao-BSPaetw7N2GFFJ-Yw?view_as=subscriber

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

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

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

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

정확도: 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

나의 코드

시간 복잡도: O(sqrt(N)) or O(N)

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

def solution(N):
    # write your code in Python 3.6
    
    if N == 1:
        return 1
    
    cnt = 0
    
    for i in range(int(N/2)):
        # 약수이면
        i = i+1
        if N/i%1 == 0:
            if N//i < i:
                break
            if N//i == i:
                cnt += 1
            else:
                cnt += 2
                
    return cnt        
    pass
    

누군가의 코드

시간복잡도: O(sqrt(N))

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

def solution(N):
    # write your code in Python 3.6
    
    number_iter = 1
    factor_cnt = 0
    
    while number_iter*number_iter < N:
        # 약수이면
        if N/number_iter%1 == 0:
            factor_cnt += 2
            
        number_iter += 1
        
    if number_iter*number_iter == N:
        factor_cnt += 1
        
    return factor_cnt
    pass

약수의 경우 이렇게 풀면 꼭 O(N)의 성능이 나지 않고,

조금 더 빠른 추출이 가능하다. 참고!

2019 카카오 겨울 인턴십을 위한 코딩테스트이다.

프로그래머스가 선정한 쉬운 1단계 문제라고 해서 풀었더니

생각보다 쉽게 정답을 구할 수 있었다.

def solution(board, moves):
    answer = 0
    
    stack_bag = []
    height_arr = []
    
    for i in range(len(board)):
        height = len(board)
        for j in range(len(board)):
            if board[j][i] == 0:
                height -= 1
            else:
                height_arr.append(height)
                break
    
    
    for i in range(len(moves)):
        if height_arr[moves[i]-1] > 0:
            stack_bag.append(board[len(board)-height_arr[moves[i]-1]][moves[i]-1])
            height_arr[moves[i]-1] -= 1
            if len(stack_bag) >= 2 and stack_bag[-1] == stack_bag[-2]:
                
                answer += 1
                del stack_bag[-1]
                del stack_bag[-1]
                
    
    return answer*2

아래 링크를 통해 문제를 풀 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/64061

아래는 나의 알고리즘 강의이다~~~><

https://www.youtube.com/channel/UCYYao-BSPaetw7N2GFFJ-Yw?view_as=subscriber

이건 그냥 조건문으로 푼거같긴 한데, 그래도 구글링 안하고 풀긴 풀었다. 오예!

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    #A
    #[3][2][-6][4][0]
    
    if len(A) == 1:
        return A[0]
    
    front_sum = [0]*len(A)
    back_sum = [0]*len(A)
    current_sum = 0
    
    for i in range(len(A)):
        if A[i] + current_sum > 0:
            front_sum[i] = A[i] + current_sum
            current_sum = A[i] + current_sum
        else:
            front_sum[i] = A[i] + current_sum
            current_sum = 0
    
    current_sum = 0
    
    for i in range(len(A)-1,-1,-1):
        if A[i] + current_sum > 0:
            back_sum[i] = A[i] + current_sum
            current_sum = A[i] + current_sum
        else:
            back_sum[i] = A[i] + current_sum
            current_sum = 0
    
    max_sum = max(A)
    
    for i in range(len(A)-1):
        if front_sum[i] + back_sum[i+1] > max_sum:
            max_sum = front_sum[i] + back_sum[i+1]
            
    return max_sum
        
    
    pass

차분하게 이해하려고 노력하니 풀린다!!

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    
    #A
    #23171 21011 21123 21366 21013 21367
    
    #A = [21011,23423,24333,14235,40293,23102]
    
    if len(A) < 2:
        return 0
        
    
    max_sorted_arr = [0]*len(A)
    min_sorted_arr = [0]*len(A)
    
    min_value = A[0]
    max_value = A[-1]
    
    for i in range(len(A)-1):
        if min_value > A[i]:
            min_value = A[i]
        min_sorted_arr[i] = min_value
        
    for i in range(len(A)-1,0,-1):
        if max_value < A[i]:
            max_value = A[i]
        max_sorted_arr[i] = max_value
        
    
    max_profit = 0
    
    for i in range(len(A)-1):
        if max_profit < max_sorted_arr[i+1] - min_sorted_arr[i]:
            max_profit = max_sorted_arr[i+1] - min_sorted_arr[i]
            
    return max_profit
        
        
            
    
        
    pass


def df(x):
    return x[1]

생각이 잘 안나서,

구글링 했다.

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    l_max_slice_sum = [0]*len(A)
    r_max_slice_sum = [0]*len(A)
    
    for i in range(1,len(A)-2):
        l_max_slice_sum[i] = max(l_max_slice_sum[i-1]+A[i],0)
    
    for i in range(len(A)-2,1,-1):
        r_max_slice_sum[i] = max(r_max_slice_sum[i+1]+A[i],0)
            
    max_slice_sum = l_max_slice_sum[0] + r_max_slice_sum[2]
    
    for i in range(1,len(A)-1):
        max_slice_sum = max(max_slice_sum,l_max_slice_sum[i-1]+r_max_slice_sum[i+1])
    
    return max_slice_sum
    pass

아래는 위 코드 참고해서 내가 짠 코드!!

# 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
    
    
    #A
    #[0][1][2][3][4][5][6][7]
    # 3  2  6 -1  4  5 -1  2
    
    #A = [6, 1, 5, 6, 4, 2, 9, 4]
    
    front_sum = [0]*len(A)
    back_sum = [0]*len(A)
     
    for i in range(1,len(A)-2):
        if front_sum[i-1]+A[i] > 0:
            front_sum[i] = front_sum[i-1]+A[i]
            
            
            
        
    for i in range(len(A)-2,1,-1):
        if back_sum[i+1]+A[i] > 0:
            back_sum[i] = back_sum[i+1]+A[i]
            
    
    max_sum = 0
    
    for i in range(0,len(A)-2):
        if front_sum[i] + back_sum[i+2] > max_sum:
            max_sum = front_sum[i] + back_sum[i+2]
    
    
    return max_sum
    
    pass

첫번째 코드는 아래의 사이트 참고했다.

https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/