Henry's Algorithm

안녕하세요~~!!ㅎㅎ

알고리즘을 공부하는 개발자 Henry입니다!

오늘은 프로그래머스의 "신규 아이디 추천" 이라는 문제를 풀어보았습니다!

2021 카카오 블라인드 채용 코딩테스트에 출제되었던 문제인데요,

카카오 치고는 쉬운 난이도여서 모두 어려움 없이 푸실 수 있었을 것 같습니다!

아래는 제가 문제를 푼 코드입니다.

def solution(new_id):
    import re
    answer = ''
    new_id = new_id.lower() # 1 단계
    new_id = re.sub(r"[^a-z0-9-_.]","",new_id) # 2 단계
    while new_id.replace("..",".") != new_id:
        new_id = new_id.replace("..",".") # 3 단계
    
    # 4 단계
    while len(new_id) > 0 and new_id[0] == ".": 
        new_id = new_id[1:]
    while len(new_id) > 0 and new_id[-1] == ".":
        new_id = new_id[:-1]
    
    # 5 단계
    if new_id == "":
        new_id += "a"
    # 6 단계
    if len(new_id) >= 16:
        new_id = new_id[:15]
        while new_id[-1] == ".":
            new_id = new_id[:-1]
    # 7 단계
    while len(new_id) < 3:
        new_id += new_id[-1]
           
    return new_id

문제에서 여러가지 단계를 나열해주고 있는데,

해당 단계들을 코드로만 정확하게 변환해주면 되는 쉬운 문제였습니다.

Level 1문제를 이렇게 큰 어려움 없이 풀 수 있는데,

아직 Level 2~3에는 관련 알고리즘 방법들을 빠르게 파악하는 것과,

정확한 알고리즘 원리를 이해하는 것이 선행되어야 할 것 같다는 생각을 하였습니다.

아래는 제가 문제를 설명한 영상입니다!

https://youtu.be/WlAGJjrcKkA

앞으로도 열심히 공부해야겠습니다!ㅎㅎ

다들 화이팅!

안녕하세요

알고리즘을 좋아하는 개발자 Henry입니다!ㅎㅎ

최근에 회사를 다니면서 바쁘고 피곤해서 코딩 문제를 못풀었었는데,

다시 조금씩 풀어보려고 키보드를 잡았습니다!

오늘은 프로그래머스에서 동적계획법을 사용해서 푸는 문제를 풀어보았습니다.

N으로 표현이라는 문제를 처음 접했을 때,

아래와 같이 풀었습니다.

def solution(N, number):
    answer = 0
    li = []
    dynamic(N,N,number, li, 1)
    return min(li) if len(li) != 0 else -1

def dynamic(N, cur, number, li, cnt):
    if cnt > 8:
        return
    if number == cur:
        li.append(cnt)
        return
    dynamic(N, int(str(cur)+str(N)), number, li, cnt+1) # N->N
    dynamic(N, cur+N, number, li, cnt+1) # N -> +
    dynamic(N, cur-N, number, li, cnt+1) # N -> -
    dynamic(N, cur//N, number, li, cnt+1) # N -> // 소수점은 무시하기 때문에
    dynamic(N, cur*N, number, li, cnt+1) # N -> *

그러나 위의 코드는 정확도 55점을 받았습니다.

알고보니 사칙연산에서 곱셈과 나눗셈을 먼저 계산을 해주는 로직이 빠져 있었습니다.

동적계획법을 사용해서 문제를 풀지 않아서 발생하는 이유였습니다.

여기서 잠깐!동적 계획법이란??>> 동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다.

찾아보니까 아래의 링크에서 자세하게 설명해주고 있습니다.https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

사실 동적계획법에 대해서 정확한 개념을 모르고 있었다.

큰 문제를 작게 쪼개어 작은 문제들을 풀어나가는 느낌으로만 이해하고 있었는데,위의 글을 통해서 동일한 작은 문제를 한번씩만 계산하는 원리가 숨어있다는 것을 알게 되었다.

그러나 바로 코드에 적용하는 것은 쉽지 않았다.그래서 몇번 고민한 결과 결국 구글링의 도움을 받아 아래 사이트와 동일한 방법으로 문제를 풀게 되었다.

https://gurumee92.tistory.com/164

def solution(N, number):
    answer = -1
    if number == N:
        return 1
    
    _li = [set() for i in range(8)]
    for i in range(len(_li)):
        _li[i].add(int(str(N)*(i+1)))
        
    for i in range(1,8):
        for j in range(i):
            for op1 in _li[j]:
                for op2 in _li[i-j-1]:
                    _li[i].add(op1+op2)
                    _li[i].add(op1-op2)
                    _li[i].add(op1*op2)
                    if op2 != 0:
                        _li[i].add(op1//op2)
        if number in _li[i]:
            answer = i+1
            break
    
    return answer

이번 기회를 통해서 동적계획법에 대해서 조금 더 알게 된 것 같아서 감사했다.

앞으로도 꾸준히 코딩 문제를 풀고 싶고, 알고리즘 공부를 하고 싶다.

안녕하세요~~

알고리즘을 공부하는 개발자 Henry입니다ㅎㅎ

오늘도 21년 신년을 맞이하여 프로그래머스 문제를 한번 풀어보았습니다.

오늘은 문자열을 파싱하여 푸는 문제인데요, 문제는 아래와 같습니다.

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s         result

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 풀이 방식:

문자열을 입력받았을 때,

앞에서부터 몇개의 단위로 압축을 하면 가장 압출률이 좋은지를 판단하는 문제입니다.

해당 문제는 문자열 파싱을 하는 능력과

이중 for문을 통해서 풀 수 있습니다.

정답 코드:

def solution(s):
    
    if len(s) == 1:
        return 1
    
    result = ""
    length = []
    cut = 1
    
    for i in range(1,len(s)//2+1):
        cnt = 1
        temp_str = s[:i]
        
        for j in range(i,len(s),i):
            if temp_str == s[j:j+i]:
                cnt += 1
            else:
                if cnt == 1:
                    cnt = ""
                result += str(cnt) + temp_str
                cnt = 1
                temp_str = s[j:j+i]
        if cnt == 1:
            cnt = ""
        result += str(cnt) + temp_str
        length.append(len(result))
        result = ""
    #print(length)
    return min(length)
        
        
        

문제는 푸는 방법을 잘 살펴보시면

따로 특별한 알고리즘일 있는 것이 아닌,

순차적으로 완전탐색하는 방법으로 풀어야 하는 것을 아실 수 있으실 거예여.

그래도 압축이라는 것이 전체 길이의 /2가 최대로 압축할 수 있는 가능성이 있기 때문에

그 때까지 단위를 올려가면서 압축률을 비교해보는 문제입니다.

아래는 저의 youtube 강의입니다.

혹시 푸시다가 어려우시면 언제든지 오셔서 시청해주세요~~

좋아요 구독도 눌려주세요!ㅎㅎ

www.youtube.com/watch?v=9bVloX96Dj4

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

• A[0], A[1], ..., A[K − 1],
• A[K], A[K + 1], ..., A[2K − 1],
  ...
• A[N − K], A[N − K + 1], ..., A[N − 1].

What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows:

• one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
• two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
• three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

If A cannot be divided into some number of blocks, the function should return 0.

For example, given:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000].

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Peaks 문제는 봉우리를 최소 1개씩 포함하고 있는 Block의 개수를 구하는 문제이다.

최대 블록의 개수를 Return 해주면 되는데,

그 방법을 구체적으로 어떻게 짜야되는지 다양하게 시도하다가 

결국 답지를 보고 풀었다.ㅜㅜ!!

그래도 이 방법 잘 알아두어야겠다.

정답 코드

# 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
    
    peaks = []
    
    for i in range(1, len(A)-1):
        if A[i] > A[i-1] and A[i] > A[i+1]:
            peaks.append(i)
            
    for i in range(len(peaks),0,-1):
        if len(A) % i == 0:
            block_size = len(A)//i
            block = [False]*i
            block_cnt = 0
            for j in range(len(peaks)):
                idx = peaks[j] // block_size
                if block[idx] == False:
                    block[idx] = True
                    block_cnt += 1
            
            if block_cnt == i:
                return block_cnt
        
    return 0
        
    pass

처음에 봤을 때,

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

그냥 약수 구해서 두 값 더해서 *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)의 성능이 나지 않고,

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