[알고리즘풀이]백준 2559: 수열 JAVA

목차

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

 

 

개요

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

2559번: 수열

 

본문

1) 문제

2) 과정

이중 for문 방식으로 풀고 싶었는데 자꾸 틀렸다고 떠서 방식을 바꿔 해결한 문제입니다. 푸는데는 3시간 정도 걸렸고 체감 난이도는 꽤 높았습니다.. n일 중에 연속되는 k일의 온도 합이 가장 컸을때의 온도합구하기가 문제의 핵심이라 생각하고 문제를 풀었고, 제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

 

0) orgArr에 입력받은 수열의 값을 담으며 0~k까지의 합을 max에 미리 구한다.
1) while문을 돌며 왼쪽인덱스(left)와 오른쪽인덱스(right)를 한칸 옮겼을때의 값을 tmp에 담고
2) tmp와 max를 비교해 더 큰 값을 max에 넣어 연속된 k개의 최대합(max)을 갱신해간다.
3) 오른쪽인덱스가 끝에 도달하면 while문을 빠져나와 max를 출력하고 종료한다.

 

이번문제는 개선과정을 진행했으나 딱히 진척이 없어서 처음 푼 그대로 변화없이 끝났습니다.. 하지만 그럼에도 혹시나 에러로그와 개선과정이 궁금하시다면 맨 아래 전체코드의 깃헙링크에 들어가셔서 주석을 봐주세요!! 설명은 주석으로 최대한 달아뒀어요!! (주석을 다는 습관,, 너무 좋은 습관,,)

 

2-1) Input

    // Variable
    static BufferedReader br;
    static StringTokenizer st;
    // Method - for read input values
    private static void readLine() throws IOException{st=new StringTokenizer(br.readLine());}
    private static int nextInt() {return Integer.parseInt(st.nextToken());}
    // Main
    public static void main(String[] args) throws IOException{
        // Input
        br = new BufferedReader(new InputStreamReader(System.in));
        readLine();
        int n = nextInt(); // 온도를 측정한 전체날짜의 수
        int k = nextInt(); // 연속되는 날의 수

        readLine();
        int max=0; // n개의 수 중 연속된 k개의 합중 가장 큰 값을 담을 변수
        int[] orgArr = new int[n];
        for(int i=0;i<n;i++) {
            orgArr[i] = nextInt();
            if(i<k) max+=orgArr[i]; // 미미 수열의 값을 더해 max를 초기화한다.
        }
    }

 

 

2-2) Logic & Output

    public static void main(String[] args) throws IOException{        
        // Logic
        int left = 0; // 왼쪽 인덱스
        int right = k; // 오른쪽 인덱스
        int tmp = max; // 임시 계산된 총합값을 담을 변수
        while(right<n){ // 오른쪽인덱스가 n(끝)이 되기전까지 
            tmp+=(orgArr[right++]-orgArr[left++]);
            // tmp-=orgArr[left++]; // 이전 tmp에서 제일 왼쪽값을 빼고 왼쪽인덱스를 오른쪽으로 한칸 옮기고  
            // tmp+=orgArr[right++]; // 이전 tmp에서 세로운 오른쪽값을 더하고 오른쪽인덱스를 오른쪽으로 한칸 옮김 
            max = Math.max(tmp,max); // tmp와 기존의 값(max)를 비교해 더 큰값으로 max를 갱신해나감
        }

        // Output
        System.out.println(max);

    }

 

 

3) 전체코드

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

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

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

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