인프런 커뮤니티 질문&답변

이재윤님의 프로필 이미지
이재윤

작성한 질문수

입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]

[문제 2번] 두 수의 차 - 정확성테스트 : O(n^2)

두수의 차 문제

작성

·

214

0

저는 이문제는 이렇게 해봤는데

영상에서는 포문이 두개 들어가더라구요

이 방식도 맞는지 한번 봐주실수 있을까요?

def solution(nums):
    sortArr = sorted(nums)
    minVal = 1000
    result = []

    for i in range(len(sortArr)-1):
        subVal = sortArr[i + 1] - sortArr[i]
        minVal = min(subVal, minVal)

        list = [sortArr[i], sortArr[i+1]]

        if minVal == subVal:
            result.append(list)

    return result

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

반례 : [1, 5, 8, 10, 11]

답이 [[1, 5], [5, 8], [8, 10], [10, 11]] 이렇게 나올 겁니다. 답은 [[10, 11]] 하나만 나와야 합니다.

입력된 수열의 minVal 가 정해지고 나서 다시 for문을 돌면서 result에 인접한 두 수의 차가 minVal인 쌍만 추가해야 합니다. 다음 영상이 위와 같은 방식으로 시간복잡도를 줄이는 영상입니다. 참고해보세요.

이재윤님의 프로필 이미지
이재윤

작성한 질문수

질문하기