코딩 테스트 문제 소스 코드

최근 *회사 코딩 테스트에서 출제된 문제 풀이 (C++)

​

Q ) int 형식 배열에서 한 기점을 중심으로 왼쪽 원소들의 합과 오른쪽 원소들의 합의 차를 구할 때, 이 값의 크기가 최소가 되는 기점 위치를 리턴하시오.

​

* 위치는 0부터 시작(왼쪽 원소 개수 0, 오른쪽이 배열 전체인 경우)

* 최소가 되는 기점 위치가 여러 개일 경우, 가장 왼쪽의 기점 위치 리턴

​

EX ) -2, 3, 0, 4, -6, 7, -9 벡터가 주어질 경우

기점 위치가 1일때

(-2) - (3 + 0 + 4 -6 + 7 -9) = -1 로 가장 차이 값의 크기가 최소가 됨

​

생각할 점

- 왼쪽 원소들의 합과 오른쪽 원소들의 합의 차를 구할 때, 크기를 비교하기 위해서는 절대값으로 계산 필요

#include <string>
#include <vector>
#include <cstdlib>

using namespace std;

int solution(int n, vector<int> v) {
    int count{ 0 };
    int LeftSum{ 0 };
    int RightSum{ 0 };

    for (int i = 0; i < n; i++)
        RightSum = RightSum + v[i];

    int MinDiff = abs(RightSum);

    for (int j = 0; j < n; j++) {
        LeftSum = LeftSum + v[j];
        RightSum = RightSum - v[j];
        if (abs(LeftSum - RightSum) < MinDiff) {
            MinDiff = abs(LeftSum - RightSum);
            count = j + 1;
        }       
    }
    return count;
}

 

정확성 100.00% / 효율성 100.00% 달성!