Henry's Algorithm

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

시간 복잡도: 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/

시간 복잡도: 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
    
    right_map = {}
    left_map = {}
    
    for i in A:
        try:
            right_map[i] += 1
        except:
            right_map[i] = 1
    
    count = 0
    left_leader = 0
    left_length = 0
    right_length = len(A)
    left_leader_count = 0
   
    for i in range(len(A)):
        right_map[A[i]] -= 1
        right_length -= 1
        
        try:
            left_map[A[i]] += 1
        except:
            left_map[A[i]] = 1
            
        left_length += 1
        
        # get left leader
        if left_map[A[i]] > left_leader_count:
            left_leader = A[i]
            left_leader_count = left_map[A[i]]
        
        # get equi leader
        if right_map[left_leader] > right_length//2 and left_leader_count > left_length//2: 
            count += 1
        
    
    return count
        
    
    pass

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

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

def solution(H):
    # write your code in Python 3.6
    
    block_cnt = 0
    stack_arr = []
    
    for i in range(len(H)):
        while len(stack_arr) > 0 and stack_arr[-1] > H[i]:
            stack_arr.pop()
        
        if len(stack_arr) == 0 or stack_arr[-1] < H[i]:
            block_cnt += 1
            stack_arr.append(H[i])
            
    return block_cnt
            
    pass

내가 풀고 싶었는데, 너무 안풀려서 구글링을 통해 정답 보고

접근 방법에 대해서 알 수 있었다.ㅜㅜ

이렇게 실력이 느는거겠지 뭐..!!

화이팅 Henry야~~

뒤늦게 다시 한번 풀어봤다!!

그랬더니 이전 풀이가 어느정도 익숙해져서인지

100 점 나왔다! 오예~~~커퓌~~

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

def solution(H):
    # write your code in Python 3.6
    
    if len(H) == 1:
        return 1
    
    block_cnt = 1
    
    stack_arr = []
    stack_arr.append(H[0])
    
    for i in range(1, len(H)):
        if stack_arr[-1] < H[i]:
            stack_arr.append(H[i])
            block_cnt += 1
            
        elif stack_arr[-1] == H[i]:
            continue
        
        else:
            while True:
                stack_arr.pop()
                if len(stack_arr) == 0:
                    stack_arr.append(H[i])
                    block_cnt += 1
                    break
            
                if stack_arr[-1] < H[i]:
                    stack_arr.append(H[i])
                    block_cnt += 1
                    break
                    
                elif stack_arr[-1] > H[i]:
                    continue
                else:
                    break
    
    return block_cnt     
    pass

관련 유튜브 강의도 있습니다~~ㅎㅎ

https://www.youtube.com/watch?v=0rRakwhbgqU

저의 강의입니다~~ㅋㅋㅋ

아래는 시간복잡도 O(N)의 100% 정답코드다

한번에 100%의 정답을 맞칠 수 있어서, 

너무 기분이 좋다~~~!!

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

def solution(S):
    # write your code in Python 3.6
    
    arr = []
    
    for i in range(len(S)):
        if S[i] == '(':
            arr.append(S[i])
        else:
            if len(arr) != 0 and arr[-1] == '(':
                del arr[-1]
            else:
                arr.append(S[i])
            
    
    if len(arr) == 0:
        return 1
    else:
        return 0
    
    pass

파이썬 알고리즘 온라인 강의도 진행중이니

알고리즘 및 IT 관련해서 도움이 필요하신 분들은 언제든지 댓글로 남겨주세요~~><

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

물고기가 위 또는 아래 방향으로 헤엄치고 있는데, 

물고기의 사이즈에 따라서 크기가 큰 물고기가 작은 물고기와 충돌할때,

잡아먹게 되면!! 총 몇마리의 물고기가 남는지를 물어보는 문제다

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

def solution(A, B):
    # write your code in Python 3.6
    
    if len(A) == 1:
        return 1
    
    arr = []
    
    for i in range(len(A)):
        arr.append((A[i],B[i]))
        
    arr_ = []
    arr_.append(arr[0])

    for i in range(1,len(arr)):
        
        # 충돌하면
        while(True):
            if arr[i][1] == 0 and arr_[len(arr_)-1][1] == 1:
                # 기존 물고기가 더 쎄면
                if arr[i][0] < arr_[len(arr_)-1][0]:
                    break
                # 새로운 물고기가 더 쎄면
                else:
                    del arr_[len(arr_)-1]
            else:
                arr_.append(arr[i])
                break
            
    return len(arr_)
            
    pass

처음으로 시도했을때, 정확도는 --> 75%가 나왔다ㅠㅠㅠ

어디서 에러가 발생했는지 확인해보니

모두 한방향으로 가고, 하나의 물고기가 다른 방향으로 갈 때,

Runtime Error가 발생하고 있었다.

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

def solution(A, B):
    # write your code in Python 3.6
    
    if len(A) == 1:
        return 1
    
    arr = []
    
    for i in range(len(A)):
        arr.append((A[i],B[i]))
        
    arr_ = []
    arr_.append(arr[0])

    for i in range(1,len(arr)):
        
        # 충돌하면
        while(True):
            if arr[i][1] == 0 and arr_[len(arr_)-1][1] == 1:
                # 기존 물고기가 더 쎄면
                if arr[i][0] < arr_[len(arr_)-1][0]:
                    break
                # 새로운 물고기가 더 쎄면
                else:
                    del arr_[len(arr_)-1]
                    if len(arr_) == 0:
                        arr_.append(arr[i])
                        break
            else:
                arr_.append(arr[i])
                break
            
    return len(arr_)
            
    pass

생각해보니 del 이라는 예약어를 사용할 때,

더이상 기존에 물고기가 존재하지 않을 수도 있는 예외처리를 진행해주어야 했다.

그래서 

del 이라는 코드 아래에 아래와 같이 조건문을 넣어주어 해결하였다.

if len(arr_) == 0:
	arr_.append(arr[i])
    	break

반복문 하나만 사용하여 문제를 풀었다.

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

관련 유튜브 강의도 있습니다~~!

https://www.youtube.com/watch?v=pPk-qrvBNO8

저의 강의입니다ㅋㅋㅋ

이 문제는 잘만 풀면 한큐에 끝낼 수 있는 문제이다.

그러나 조건에 다양한 예외처리를 신경써주어야 한다.

그렇지 않으면, 중간에 Runtime Error가 발생한다ㅜㅜㅜ

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

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

def solution(S):
    # write your code in Python 3.6
    
    
    if len(S) == 0:
        return 1
    
    arr = []
    
    for i in S:
        if i == "{":
            arr.append(3)
        elif i == "[":
            arr.append(2)
        elif i == "(":
            arr.append(1)
        elif i == ")":
            arr.append(-1)
        elif i == "]":
            arr.append(-2)
        elif i == "}":
            arr.append(-3)
           
    
    arr_ = []
    arr_.append(arr[0])
    
    for i in range(1,len(arr)):
        if len(arr_) != 0 and arr[i] < 0 and arr[i] == -1 * arr_[len(arr_)-1]:
            del arr_[len(arr_)-1]
        else:
            arr_.append(arr[i])
        
    if len(arr_) == 0:
        return 1
    else:
        return 0
        
    
    pass

관련 유튜브 강의도 있습니다~~

https://www.youtube.com/watch?v=4Lzl1yOsyRM

저의 강의입니다ㅋㅋㅋ