22년도 네이버 코테 후기

3번 문제가 데이터 길이 100만인걸 봐서 최적화를 어떻게 해야 하지 하다가...

O(n^2)되는 문제 풀이도 제출을 못했다.

문제를 다시 생각해보니 연속전인 부분만 구하는거 같은데 실마리를 찾았다 생각해서

급하게 풀어버렸다...

물론 지금도 O(n^2)이상의 최적화 풀이는 떠오르지가 않는다. 다만, 풀긴 풀었으니까 올려보고자 한다.

 

* 문제를 제대로 이해하지 못한 상태로 문제를 푼 코드

def solution(a, k):
    # write your code in Python 3.6
    a.sort()
    left = 0
    right = len(a) - 1
    while True:
        chk = a[right] - a[left]
        realBreak = False
        if chk > k:
            l = a[left + 1] - a[left]
            r = a[right] - a[right - 1]
            if l > r:
                left += 1
            else:
                right -= 1

        else:
            break


    print(a[left: right + 1])

    maxValue = max(a[left: right + 1])
    minValue = min(a[left: right + 1])
    answer = maxValue - minValue
    return answer


# ex3. ([3, 5, 1, 3, 9, 8], 4) 답= [9, 8]
print(solution([5, 3, 6, 1, 3], 2))  # [3, 3, 5]

 

* 맞을듯 하지만 시간초과 날거 같은 코드

 

def solution(a, k):
    # write your code in Python 3.6
    n = len(a)
    answer = []
    for i in range(-1, n):
        candi = [a[i % n]]
        for j in range(i + 1, n):
            chk = abs(a[i % n] - a[j % n])
            if k >= chk:
                maxV = max(candi)
                minV = min(candi)
                if k >= abs(maxV - a[j % n]) and k >= abs(minV - a[j % n]):
                    candi.append(a[j % n])
                else:
                    break
            else:
                break
        if len(candi) > 1:
            answer.append(candi)

    answer.sort(key=lambda x: ((max(x) - min(x)), -len(x)))
    print(answer)
    maxValue = max(answer[0])
    minValue = min(answer[0])
    ans = maxValue - minValue
    return ans


# ex3. ([3, 5, 1, 3, 9, 8], 4) 답 = [9, 8]
print(solution([3, 5, 1, 3, 9, 8], 4))
# ([5, 3, 6, 1, 3], 2)  [3, 3, 5]

 

1번은 문제가 바로 안와닿아서 넘겼고, 4번을 풀었고, 3번은 말했다시피 이상태고

2번은 div태그를 알맞은 시맨틱 태그로 바꾸는 문제 같은데,,, 오류가 많이 나온다...

div태그 자체를 지우지는 말라고 나온거 같은데..? 어떻게 풀어야 됬던걸까..

 

영어로 문제가 나와서 영 이해가 빠르게 잘안된게 큰거같다..음...아무래도 아쉬운 하루가 될듯하다.

이상 끝!!