Lesson 3 - TapeEquilibrium
문제
input : 배열 A
output : 차이의 minimum 값
배열 A는 [-1000,,1000]범위 안의 숫자를 포함하고 2~100,000크기를 가진다. A를 각 기준점으로 자르고 기준점의 왼편의 숫자들의 합, 오른편의 숫자들의 합의 차이의 절댓값들 중 가장 작은 값을 return해라.
기준점은 0<P<N, 결괏값의 후보들 중 하나는 |(A[0] + A[1] + ,,, + A[P-1]) - (A[P] + A[P+1] + ,,, + A[N-1])| 이다.
풀이
기준점 하면 pivot이라 해서 퀵 정렬이 생각났는데 전혀 관련 없는 문제인 것 같다.
A안에 들어가는 숫자가 순차적인 수가 아니기 때문에 첫 번째 경우에 해당하는 값들만 for문을 이용해 구하고, 남은 경우를 for문을 돌면서 첫번째 경우에 구한 값에서 갱신하는 식으로 해결하면 시간복잡도가 O(N)이 나온다.

- 첫번째 기준점으로 나뉜 경우 left = 왼편 숫자들의 합, right = 오른편 숫자들의 합을 구한다.
- 최대로 나올만한 answer값은 100,000 X 1000이므로 answer을 처음에 100,000,000 + 1로 선언한다.
- <cstdlib>와 <algorithm>에서의 abs(), min()함수를 이용해서 각 left와 right 차이의 절댓값의 가장 작은 값을 갱신한다. (1)
- 남은 경우는 오른편에 있던 숫자가 왼편으로 하나씩 이동하는 경우들이고 그 동안 (1)를 계속 반복한다.
코드
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
//숫자가 정해져 있지 않아서 우선 처음으로 나뉘는 부분은 계산하자.
int left = A[0];
int right = 0;
for(int i = 1; i<A.size(); i++){
right += A[i];
}
int answer = 100000001;
answer = min(abs(left - right), answer);
for(int i = 1; i<A.size()-1; i++){
left += A[i];
right -= A[i];
answer = min(abs(left - right), answer);
}
return answer;
}
★ <cstdlib> 라이브러리가 생각나지 않아서 검색했다.
<cstdlib> (우선 많이 익숙한 함수들을 표기했다)
(1) 메모리 할당 함수 : malloc, free, realloc, calloc
(2) 숫자 문자열 변환 : atoi
(3) 멀티 바이트 / 와이드 문자열 및 문자 변환 함수
(4) 알고리즘 함수
(5) 낮은 품질의 난수 생성 함수
(6) 절댓값 : abs() [int, long int, long long, float, double, long double, long int, long long int]
(7) 정수 나누기
https://docs.microsoft.com/ko-kr/cpp/standard-library/cstdlib?view=msvc-160
자세히 알아보기: < b>
docs.microsoft.com
※ 낮은 품질의 난수가 뭐지? 나중에 확인해봐야겠다.