20200126.md

2020. 01. 26

오늘의 문제 :

정수 배열이 주어졌을 때, 오른쪽 원소가 왼쪽 원소보다 더 큰 경우 중 두 원소의 차가 최대가 되는 값을 찾으시오. Input: [2, 7, 9, 5, 1, 3, 5] Output: 7 (원소 2와 9)

풀이 :

문제의 조건대로 만약 두 원소의 차가 최대가 되는 경우는 둘중의 하나의 원소가 최소값 또는 최대값일 수밖에 없다. 따라서 최소값이 나오는 경우와 최댓값이 나오는 경우를 찾아서 차이값을 갱신해나가면서 결과적으로 최대 차이값이 결정되는 순간을 찾는다. 단 최소값이 좌측에 있어야 하므로, 새로운 최소값이 나오는 경우부터 새로 비교하면 된다.

시간복잡도 O(n)

소스코드 :

• 코틀린 풀이
• 테스트 코드