(C#) 쿠키 구입

코딩테스트 연습 - 쿠키 구입 | 프로그래머스 스쿨

프로그래머스

 

보기에 굉장히 단순한 문제

우선 완전탐색으로 풀어보기로 했다.

 

 가능한 모든 부분순열 s를 첫째 아들에게 줄 [l, m] 쿠키라고 하고, s[l, m] = s[m+1, r]를 만족하는 r을 찾는다.

 [l, m] 구간을 만드는 방법은 1부터 n까지의 정수 중에서 두개를 뽑는 것이므로 O(n^2)

 s[l, m] = s[m+1, r]을 만족하는 r을 찾는 것은 O(n^2) (r을 m+1부터 마지막 요소까지 순회하면서 요소들의 합을 구해야한다)

 최종 시간복잡도는 O(n^4)이 된다

 

 O(n^4)는 시간복잡도가 너무 크기때문에 좀 더 줄여보기로 했다

 새로운 정수 배열을 만들어 [0, i]의 부분합을 미리 저장해둔다

 이렇게 하면 s[l, m]과 s[m+1, r]을 상수시간만에 구할 수 있게 되므로 시간복잡도를 O(n^3)까지 내릴 수 있다.

 

 n이 최대 2000이므로 O(n^3)은 너무 비효율적이다

 조건을 만족하는지 확인하려면 반드시 O(n)은 필요하다

 그렇다면 [l, m]과 [m+1, r] 구간을 구하는 부분에서 시간복잡도를 줄여야한다

 

 결국 순열의 임의의 요소 m을 정하고, 거기서부터 좌우로 뻗어나가는 방법으로 접근하기로 했다

 먼저 임의의 요소 m을 정하는 것은 O(n)

 m으로부터 왼쪽, 오른쪽으로 하나씩 늘려가며 조건을 만족하는지 확인하는 것은 O(n)

 최종 시간복잡도는 O(n^2)이 된다

 

  코드

using System;

public class Solution {
    public int solution(int[] cookie)
    {
        int answer = 0;

        for (int m = 0; m < cookie.Length - 1; m++)
        {
            int left = m;
            int right = m + 1;
            int lsum = cookie[left];
            int rsum = cookie[right];

            while (left >= 0 && right < cookie.Length)
            {
                if (lsum == rsum && lsum > answer)
                {
                    answer = lsum;
                }

                if (lsum <= rsum)
                {
                    left--;
                    if (left >= 0) lsum += cookie[left];
                }
                else
                {
                    right++;
                    if (right < cookie.Length) rsum += cookie[right];
                }
            }
        }

        return answer;
    }
}

결과

채점을 시작합니다.

정확성 테스트

테스트 1 〉	통과 (0.21ms, 31.5MB)
테스트 2 〉	통과 (0.21ms, 31.4MB)
테스트 3 〉	통과 (0.22ms, 31.3MB)
테스트 4 〉	통과 (0.21ms, 31.5MB)
테스트 5 〉	통과 (0.23ms, 31.4MB)
테스트 6 〉	통과 (0.66ms, 31.4MB)
테스트 7 〉	통과 (0.81ms, 31.5MB)
테스트 8 〉	통과 (1.25ms, 31.5MB)
테스트 9 〉	통과 (2.84ms, 31.3MB)
테스트 10 〉	통과 (0.21ms, 31.5MB)
테스트 11 〉	통과 (0.24ms, 31.4MB)
테스트 12 〉	통과 (0.21ms, 31.6MB)
테스트 13 〉	통과 (0.21ms, 31.3MB)
테스트 14 〉	통과 (0.22ms, 31.6MB)
테스트 15 〉	통과 (0.22ms, 31.2MB)
테스트 16 〉	통과 (0.23ms, 31.4MB)
테스트 17 〉	통과 (0.24ms, 31.5MB)
테스트 18 〉	통과 (0.23ms, 31.3MB)
테스트 19 〉	통과 (0.22ms, 31.6MB)
테스트 20 〉	통과 (0.25ms, 31.3MB)
테스트 21 〉	통과 (0.24ms, 31.2MB)
테스트 22 〉	통과 (0.23ms, 31.5MB)
테스트 23 〉	통과 (1.40ms, 31.2MB)
테스트 24 〉	통과 (0.23ms, 31.5MB)
테스트 25 〉	통과 (0.24ms, 31.2MB)
테스트 26 〉	통과 (1.40ms, 31.5MB)

효율성 테스트

테스트 1 〉	통과 (1.28ms, 31.4MB)
테스트 2 〉	통과 (1.30ms, 31.5MB)
테스트 3 〉	통과 (3.00ms, 31.4MB)
테스트 4 〉	통과 (2.83ms, 31.5MB)
테스트 5 〉	통과 (2.89ms, 31.4MB)
테스트 6 〉	통과 (5.53ms, 31.4MB)
테스트 7 〉	통과 (5.46ms, 31.5MB)
테스트 8 〉	통과 (5.37ms, 31.5MB)

채점 결과

정확성: 66.7

효율성: 33.3

합계: 100.0 / 100.0