Henry's Algorithm

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

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

그렇지 않으면, 중간에 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

Python2점대와 3점대가 차이가 생기는 이유: 두 버전간의 backward compatibility를 지원하지 않는 부분이 많다는 것이다.

python 2.7 버전이 2010년에 처음 세상에 나온 이후로, 연구 목적으로 사용되고 있고,

지금도 다양한 연구 목적으로 python 2점대를 사용중이다.

그러나 python2점대보다는 python3 점가 계속 발전하면서, numpy, pandas, SciPy, SymPy, IPython 등 연구목적으로 만들어진 수많은 Python 라이브러리는 Python 3점대에 호환성이 잘 되고, 계속 발전해가고 있다.

관련 영상 참고

https://youtu.be/f_6vDi7ywuA

이 외에 간단한 차이를 설명하자면,

1. xrange vs range

파이썬 2에서는 xrange를 지원하지만,

파이썬 3에서는 xrange는 아니고, range만 지원한다.

2. print

파이썬 2: print "test"

파이썬 3: print("test") <-- 괄호를 넣어주어야 한다.

3. 나눗셈

파이썬 2: 정수 / 정수 = 정수 (5/2=2)

파이썬 3: 정수 / 정수 = 실수 (5/2=2.5)

이렇게 차이가 발생하니, 파이썬의 버전을 잘 맞춰주어서 코드를 짜주어야 한다.(특히 나눗셈)

출처: https://goodtogreate.tistory.com/entry/Python-2-와-Python-3의-차이점 [GOOD to GREAT]

출처: https://tech.ssut.me/python-3-is-the-future/

# 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
    
    east_car_num = 1
    
    passing_car_num = 0
    
    # 최초 동쪽으로 가는 차 위치
    try:
    # 동쪽으로 가는 차가 없으면 에러 발생하여 passing_car가 없으므로 return 0
        east_car = A.index(0)
    except:
        return 0
        
    for i in range(east_car+1,len(A)):
        if A[i] == 1:
            passing_car_num += east_car_num
            
            if passing_car_num > 1000000000:
                return -1
        else:
            east_car_num += 1
            
            
    return passing_car_num
    
    
    pass

20%의 정답률 코드ㅠㅠ

# 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
    
    # step 1 - input array A
    # already succeed
    tmp = sum(A[0:2])/len(A[0:2])
    
    # step 2 - get the avaerage value in for loop
    A_length = len(A)
    for P in range(A_length):
        for Q in range(P+1,A_length-1):
            arr_ = A[P:Q+1]
            arr_sum = sum(arr_)
            arr_len = len(arr_)
            if tmp >= arr_sum/arr_len:
                tmp = arr_sum/arr_len
                return_value = P
                
    return return_value
    
    pass

slice가 몇개까지 쪼개질 지 그 길이를 먼저 구하고 그만큼만 돌리려고 하는 코드는 좋은 접근이었다.

# 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
    
    # step 1 - input array A
    # already succeed
    
    # step 2 - get a length of slice
    slice_len = len(A)-1
    length = len(A)
    arr = []
    
    for i in range(2,slice_len):
        for j in range(slice_len-i+1):
            arr.append(sum(A[j:j+i])/len(A[j:j+i]))
            print(j,"###",sum(A[j:j+i])/len(A[j:j+i]))
            
    
    
    return min(arr)

    

한개씩 더해가면서 최솟값을 구하려고 하는 접근도 정답률은 좋지 못했지만, 나름 괜찮은 발상이었다.

# 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) == 3:
        return 0
    
    # step 1 - input array A
    # already succeed
    
    length = len(A)-1
    
    X = A[:length-1]
    Y = A[1:length]
    C = [x+y for x,y in zip(X,Y)]
    tmp = min(C)/2
    
    print(C.index(min(C)))
    
    
    return_value_index = C.index(min(C))
    
    
    for i in range(2,length):
        print(i)
        Y = A[i:length]
        print(Y)
        C = [x+y for x,y in zip(C[:length-i],Y)]
        print(C)
        if tmp >= min(C)/i+1:
            tmp = min(C)/i+1
            return_value_index = C.index(min(C))
    
    
    return return_value_index

    

다양한 시도 끝에 결국 구글의 힘을 빌렸다.ㅠㅠ

잘 설명해주신 링크가 있어서 미리 출처를 밝힌다.

https://cheolhojung.github.io/posts/algorithm/Codility-MinAvgTwoSlice.html

핵심은 이렇다.

4개의 원소의 평균은 2개씩 나누어서, 각 (2개의 평균)의 최솟값보다 크다고 한다. 그래서 최솟값이 있는 위치(인덱스)를 구하면 되는 문제였다. 열심히 풀어보았는데 생각보다 정확도가 잘 안되서 화가난다.!!

아래는 시간복잡도 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
    
    min_value = sum(A[0:2])/2
    min_index = 0
    for i in range(len(A)):
        try:
            if min_value > (A[1+i] + A[i])/2:
                min_value = (A[1+i]+A[i])/2
                min_index = i
            
            if min_value > (A[2+i] + A[1+i] + A[i])/3:
                min_value = (A[2+i] + A[1+i] + A[i])/3
                min_index = i
        except:
            break
    
    return min_index
    
    pass