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)이 나온다.

analysis 중 하나

• 첫번째 기준점으로 나뉜 경우 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

 

 

※ 낮은 품질의 난수가 뭐지? 나중에 확인해봐야겠다.