Codility - NumberOfDiscIntersections

열심히 풀려고 하였으나, 반복문 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

 

저의 강의입니다ㅋㅋㅋ