Henry's Algorithm

아래는 시간복잡도 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

안녕하세요

알고리즘 공부하는 개발자 Henry Joo 입니다~~~~><

오늘은 요기요, 배민, 배달통의 기업으로 알려지는 

Delivery Hero Korea의 코딩테스트를 보았습니다.

코딩테스트의 시작은 이렇습니다

제가 최근에 알고리즘 공부를 하고 있는데,
비전공자 친구들에게 파이썬으로 알고리즘 푸는 방법을
알려주고 있습니다~~

그런데 최근에 그 중 한 친구가

다음과 같은 Python 공고가 올라왔다고 단톡방에 올려주었습니다.

확인해보니

Python으로 백엔드쪽을 개발하는 조직에서

Python 인력을 대규모 채용한다는 내용이었습니다.

때마침 Python을 공부하고 있었던 찰나에,

그동안에 쌓은 실력을 가늠해볼 수 있는 좋은 시간이겠다 싶어서 바로 접수했습니다!!!ㅋㅋㅋ

모바일로도 간편하게 접수할 수 있었습니다!!

(접수 링크: https://boards.greenhouse.io/deliveryherokoreatech/jobs/4713964002?gh_src=efc568952us)

별다른 서류전형없이

지원자의 이름과 메일주소, 그리고 연락처만 기입하면

누구에게나 코딩테스트를 시켜주는 그런 채용방식이었습니다(심플해서 좋았습니다ㅋㅋㅋ)

신청을 완료하고,

Gmail에 "띠링~~!" 하고

바로 안내메일이 도착했습니다~~~

본 메일 수신 후,
온라인 코딩테스트를 볼 수 있는 사이트를

24시간 안에 링크로 보내준다는 내용이었습니다.

지원을 완료하고
설레는 마음으로 하루를 보내고

다음날!! 메일이 도착해있었습니다~~

본 메일 수신 후 7일 이내에
링크에 들어가서 코딩테스트를 진행하라고
나와있었습니다~~~~!

(코딩테스트는 Codility 라는 웹사이트를 통해서 진행이 되었습니다)

원래 저는 Python에 대해서 쫌 더 공부를 하고 보려고 하였으나,

코딩테스트 문제가 너무 궁금해서 바로 들어가서 풀어보았습니다~~!!

실제로 문제 풀면서

알고리즘 뿐만 아니라
다양한 지식이 필요했습니다~~!!ㅎㅎ

문제를 푸는 내내 어려웠지만 

알고리즘 푸는 거 자체가 그냥 재밌었습니다

문제의 내용을 말씀드릴 수 없지만,

100분 안에 2문제 풀기를 도전하였고!

결과는 한문제 대충 맞추고,

한문제 거의 감도 못잡았습니다.ㅜㅜ

그래도 생각보다 알고리즘 푸는 시간이 너무 재밌어서

아쉬움보다는 즐거움이 더 많이 남았습니다~!!ㅎㅎㅎ

문제를 풀고 나서 1분 남겨두고 

바로 제출~~~~~!!ㅎㅎㅎ

Tip: 모든 문제를 다 Python으로 풀어야되서
Python의 전체적인 문법에 대해서

공부하고 보시면 좋을 것 같습니다~!!

문제 풀고 제출하면,

짧게 Survey 같은거를 시키는데,

생각보다 Delivery Hero Korea라는 회사가 

코드에 대한 정성과 피드백을 소중히 여기고 있다는 느낌이 물씬 들었습니다.!!

아래는 Delivery Tech 블로그라고 해서,

다양한 개발 경험에 대해서 나누고,

Posting 하는 분위기인것 같아서 공유드립니다~!!ㅎㅎ

https://medium.com/deliverytechkorea

ps. Delivery Hero Korea 코딩테스트는 Codility 라는 사이트에서 진행됩니다.

혹시 Delivery Hero Korea 코딩테스트를 준비중이시라면, 아래 링크를 통해서

하루에 1문제씩 풀어보시는 것도 추천드립니다!

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

저의 강의입니다ㅋㅋㅋ

Codility Lesson 6의 마지막 문제다.

Triangle 이라는 문젠데, 배열 안에 3개의 수가 아래의 조건을 만족하는 지의 여부를 묻는 문제다.

A[i] + A[j] > A[k]

A[j] + A[k] > A[i]

A[i] + A[k] > A[j]

(단, 0< i,j,k < N)

최대한 for 문을 안쓰고 싶은데, 어떻게 해야할까..

for 문 3개 쓰니깐, 마지막 3문제는 Timeout Error가 발생했다.ㅜㅜ

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

# 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 = sorted(A)
    
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            for k in range(j+1,len(A)):
                if A[i] + A[j] <= A[k]:
                    break
                else:
                    if is_triangular(A[i],A[j],A[k]) == 1:
                        return 1
            
    return 0
    pass


def is_triangular(a,b,c):
    if a+b > c and a+c > b and b+c > a:
        return 1
    else:
        return 0

크기에 따라서 오름차순으로 정렬하고,

for문 하나로 문제를 푸니 풀렸다!!

ex) 1,2,5,8,10,20 로 정렬을 하면,

a < b < c이렇게 정렬이 될때,

일단 a + c > b 는 당연한 사실 c가 b 보다 크기 때문에.

그리고 c + b > a도 당연한 사실 c,b가 a보다 크기 때문에,

그러므로 a + b > c 인지만 확인하면 됨.

시간 복잡도: O(N*log(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 = sorted(A)
    
    for i in range(len(A)-2):
        if A[i] + A[i+1] > A[i+2]:
            return 1
    
    return 0
    pass

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

https://www.youtube.com/watch?v=IxLlq9RGFI8

저의 강의입니다ㅋㅋㅋ

열심히 풀려고 하였으나, 반복문 2번 돌리는 거 외에는 생각이 잘 안났다.ㅜㅜ

결국 정답을 보고 이해하였지만, 앞으로도 열심히 해야겠다.

내 코드: 시간 복잡도: O(N ** 2) --> 53%의 정답률

# 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
    
    count = 0
    
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            tmp = i+A[i] 
            tmp2 = j-A[j]
            if tmp2 <= tmp:
                count += 1
                
    return count
                
            
    
    pass

구글링한 코드: 시간 복잡도: O(N*log(N)) or 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
    
    arr = []
    
    for i,v in enumerate(A):
        arr.append((i+v,1))
        arr.append((i-v,-1))
        
    arr.sort()
    
    
    intersect = 0
    intervals = 0
    
    for i,v in enumerate(arr):
        if v[1] == 1:
            intervals -= 1
        if v[1] == -1:
            intersect += intervals
            intervals += 1
    
    if intersect > 10000000:
        return -1
    
    return intersect
    pass

ㅜㅜ 열심히 풀려고 해보았지만, 생각보다 다른 접근 방법이 생각이 나지 않아 골머리를 앓았다.

코드는 다음의 블로그를 참고했다.

https://m.blog.naver.com/PostView.nhn?blogId=evanecen&logNo=221359303451&proxyReferer=https:%2F%2Fwww.google.com%2F

다들 화이팅

코로나 19 다함께 이겨냅시다!

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

https://www.youtube.com/watch?v=Ell5C1yoBRQ

저의 강의입니다ㅋㅋㅋ

시간 복잡도: O(N * log(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 = sorted(A, reverse=True)
    
    if A[0]*A[1]*A[2] > A[0]*A[-1]*A[-2]:
        return A[0]*A[1]*A[2]
    else:
        return A[0]*A[-1]*A[-2]
    
    pass

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

https://www.youtube.com/watch?v=gFpzBTytLPY

저의 강의입니다ㅋㅋㅋ

# 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) == 0:
        return 0
    
    B = set(A)
    
    return len(B)
    
    pass