문제 설명 현대모비스에서 개발한 자율주행을 이용한 레이싱 대회가 열렸습니다. 당신은 관람객들이 레이싱 대회를 재밌게 즐길 수 있도록 레이싱 경기장을 설계하려고…
- User
문제 설명 현대모비스에서 개발한 자율주행을 이용한 레이싱 대회가 열렸습니다. 당신은 관람객들이 레이싱 대회를 재밌게 즐길 수 있도록 레이싱 경기장을 설계하려고 합니다.
레이싱 경기장은 n개의 지점으로 구성됩니다. 각 지점의 높이는 정해져 있지만, 그 순서는 자유롭게 바꿀 수 있습니다. 당신의 목표는 이웃한 지점끼리의 높이 차이의 최솟값이 최대가 되도록 높이 순서를 정하는 것입니다.
예를 들어 n이 3이고 세 지점의 높이가 각각 1, 5, 8인 경우를 생각해 봅시다.
높이를 [1, 5, 8] 순서로 배치하면 1번과 2번 지점의 높이 차이는 4, 2번과 3번 지점의 높이 차이는 3이므로 높이 차이의 최솟값은 3입니다. 높이를 [5, 1, 8] 순서로 배치하면 1번과 2번 지점의 높이 차이는 4, 2번과 3번 지점의 높이 차이는 7이므로 높이 차이의 최솟값은 4입니다. 높이 차이의 최솟값을 4보다 크게 만드는 방법은 없습니다.
지점 n개의 높이를 담은 1차원 정수 배열 heights가 매개변수로 주어집니다. 높이 차이의 최솟값이 최대가 되도록 레이싱 경기장을 설계했을 때의 높이 차이의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한사항 2 ≤ heights의 길이 = n ≤ 200,000 1 ≤ heights의 원소 ≤ 109 입출력 예 heights result [1, 8, 5] 4 [11, 6, 4, 11] 5 [9, 9, 9, 9, 30] 0 입출력 예 설명 입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
높이를 [4, 11, 6, 11] 순서로 배치하면 높이 차이의 최솟값이 5입니다. 높이 차이의 최솟값을 5보다 크게 만드는 방법은 없습니다.
따라서 5를 return 하면 됩니다.
입출력 예 #3
높이를 어떻게 배치하더라도 높이가 9인 지점 두 개가 이웃하게 됩니다. 따라서 높이 차이의 최솟값은 항상 0입니다.
따라서 0을 return 하면 됩니다. 아레 코드이 문제점을 찾아서 고쳐 def diff(n,center_index,heights): return abs(heights[n]-heights[n-center_index]) def solution(heights): heights.sort() heights_list=[] diff_list = [] if len(heights)%2==0 or len(heights)==3: heights_list=[heights] else: frst = heights.pop(0) list1,list2 = [frst],[frst] for _ in range(int((len(heights))/2)): list1.append(heights.pop(0)) list2.append(heights.pop(0)) heights_list=[list1,list2] for i in heights_list: i.sort() heights_len = len(i) center_index = int(heights_len/2) loop = center_index if heights_len % 2 == 0 else center_index+1 if heights_len%2!=0: loop -=1 for a in range(loop): diff_list.append(diff(center_index+a,center_index,i)) return min(diff_list)
- Assistant
The provided code attempts to maximize the minimum height difference between adjacent points by splitting the sorted heights into multiple lists and then calculating the minimum difference within each list. While this approach works for some test cases, it fails for others, such as when
n = 5. The primary issue lies in how thedifffunction calculates differences and how multiple lists are handled separately instead of forming a single permutation.Key Problems:
- Incorrect Difference Calculation: The
difffunction calculates the difference betweenheights[n]andheights[n - center_index], which does not represent the adjacent differences in a permutation. - Multiple Lists Handling: Splitting the heights into multiple lists and computing their differences independently fails to capture the true minimum difference in a single permutation.
Correct Approach:
To maximize the minimum adjacent difference, a common strategy is to arrange the sorted heights by alternating between the largest and smallest remaining heights. This helps in spreading out the heights to ensure larger differences between adjacent points. Here's how you can implement this:
- Sort the Heights: Begin by sorting the heights in ascending order.
- Arrange Alternately: Use two pointers to alternately select the largest and smallest remaining heights to form the permutation.
- Compute Minimum Difference: Iterate through the arranged permutation to find the minimum difference between adjacent elements.
Corrected Code:
Here's the corrected version of the code that follows the above approach:
def solution(heights): heights.sort() arranged = [] left = 0 right = len(heights) - 1 while left <= right: arranged.append(heights[right]) right -= 1 if left <= right: arranged.append(heights[left]) left += 1 min_diff = float('inf') for i in range(len(arranged) - 1): min_diff = min(min_diff, abs(arranged[i] - arranged[i + 1])) return min_diffExplanation of the Corrected Code:
- Sorting: The heights are first sorted in ascending order to facilitate the alternating selection.
- Arrangement:
- Largest First: Start by selecting the largest remaining height (
heights[right]) and append it to thearrangedlist. - Smallest Next: Then, select the smallest remaining height (
heights[left]) and append it. - Continue Alternating: Continue this process until all heights are arranged.
- Largest First: Start by selecting the largest remaining height (
- Calculating Minimum Difference: Traverse the
arrangedlist to find the smallest difference between any two adjacent elements.
Verification with Test Cases:
-
Test Case 1:
- Input:
[1, 8, 5] - Arranged:
[8, 1, 5] - Differences:
[7, 4] - Minimum Difference:
4(Correct)
- Input:
-
Test Case 2:
- Input:
[11, 6, 4, 11] - Arranged:
[11, 4, 11, 6] - Differences:
[7, 7, 5] - Minimum Difference:
5(Correct)
- Input:
-
Test Case 3:
- Input:
[9, 9, 9, 9, 30] - Arranged:
[30, 9, 9, 9, 9] - Differences:
[21, 0, 0, 0] - Minimum Difference:
0(Correct)
- Input:
Conclusion:
By arranging the heights in an alternating high-low pattern and then calculating the minimum adjacent difference, we ensure that the minimum difference is maximized as required. This approach resolves the issues present in the original code.
- Incorrect Difference Calculation: The