[알고리즘풀이]백준 1806 : 부분합 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1806번 부분합을  풀었습니다. 이를 정리해보고자 합니다.

1806번: 부분합

 

본문

1) 문제

 

2) 과정

처음 풀어본 투포인트 문제였습니다.. 푸는데는 3시간 정도의 시간이 걸렸고 이전에 풀었던 문제같아서 오래걸린게 좀 속상했던 문제입니다.

 

제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

0) 배열(orgArr)에 입력받은 수열의 값을 인덱스에 따라 넣어준다.
1) Logic에서 l~r까지의 합을 구해나가되, sum이 s(목표값)을 넘으면 l을 오른쪽으로 이동시키고 그 외에는 r을 오른쪽으로 이동시켜 범위를 늘려나간다.
2) 그러다 r이 n이되어(끝에 도달하여) 모든 값을 포함하게되었다면 while문을 종료시킨다. 
3) 1)~2)를 통해 sum이 s를 넘는 경우의 부분집합의 최소크기가 담긴 ans를 값이 변화되었다면 ans, 아니라면 0을 출력하며 종료한다.

 

시간초과, 메모리초과, 틀렸습니다 다 겪어봤는데... 해당 링크에 반례가 있다해서 다 돌려봤지만...? 채점만 하면 틀렸다고 나오는 절망을 선사한 문제였습니다... (각 에러로그에 대한 게 궁금하다면 맨 아래 깃헙 링크에서 확인해주세요... )

 

풀고나서 개선하려고 전역변수로 저장하던 값들을 지역변수로 바꿨더니 431등에서 31등까지 등수가 완전 올랐어요...

 

근데 왜 지금 적을 때 확인하니 50등까지 내려온걸까요....

무튼 이번에 풀어본 문제들을 input, logic, output에 맞춰 나눠 보여드리고 빨리 마무리 짓겠습니다.. 설명은 주석으로 최대한 달아뒀어요!! (주석을 다는 습관,, 너무 좋은 습관,,)

흑흑... 이렇게 쉽게 밀리는 거였구나....

 

2-1) Input

// Variable
    static BufferedReader br;
    static StringTokenizer st;
    // Read Method 
    private static void readLine() throws IOException {st = new StringTokenizer(br.readLine()); }
    private static int nextInt() {return Integer.parseInt(st.nextToken());}
    
    public static void main(String[] args) throws IOException {
        // Input
        br = new BufferedReader(new InputStreamReader(System.in));
        readLine();
        int n = nextInt(); // 수열의 길이
        int s = nextInt(); // 원하는 부분합의 최소 값

        readLine();
        int[] orgArr = new int[n]; // 인덱스에 따른 수열의 값을 저장할 배열
        for(int i=0;i<n;i++) orgArr[i] = nextInt();
    }

 

 

2-2) Logic & Output

   public static void main(String[] args) throws IOException {
        // Logic
        // initialize
        int l=0; // 왼쪽인덱스
        int r=0; // 오른쪽인덱스
        int sum=0; // 총합을 담는 변수 
        int ans=Integer.MAX_VALUE; // 가장 짧은 연속길이를 담는 변수
        // searching
        while(true){
            if(sum>=s){ // l부터 r까지의 합이 s를 넘으면
                ans = Math.min(ans, r-l); // 최단연속길이(ans) 갱신
                sum-=orgArr[l++]; // sum에 더했던 왼쪽의 값을 빼내고 왼쪽인덱스(l)를 늘림.
            }else if (r==n) break;
            else sum+=orgArr[r++]; // l부터 r까지의 합이 s를 아직 못넘으면 오른쪽인덱스(r)을 늘리며 합계를 늘림.
        }
        // Output
        // 초기값과 달라진게 없다면 0, 아니라면 ans값을 출력 
        System.out.println(ans!=Integer.MAX_VALUE?ans:0);
    }

 

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

앞서 말씀드렸듯이 소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/two_pointers/BOJ1806.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비