[do it 알고리즘] 백준 2018 (투 포인터)

문제 설명

 

풀기 전 생각

• 자연수 1부터 시작이니 start와 end라는 투 포인터를 1로 지정
• end가 N이 되면 자기 자신도 합으로 나타나지므로 N+1까지 반복
• (sum > N)이면 start 빼고, (sum < N)이면 end 더하고 포인터 옮기기
• (sum ==  N)이면 cnt++;  sum에서 start 빼고 start 포인터 옮기기

import java.util.Scanner;
public class Baek2018 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int sum = 0;
        int start = 1;
        int end = 1;
        int cnt = 0;

        while(end < N + 1 ){
            if(sum > N){
                sum = sum - start;
            }else if(sum < N){
                sum = sum + end;
                end++;
            }else{
                cnt++;
                sum = sum - start;
                start++;
            }
        }
        System.out.println(cnt);
    }
}

오류 및 개선

• 결과는 제대로 나오지만 시간초과로 실패
• 첫 번째, sum = 1로 초기화하고  sum < N이면 end++하고 sum에 더하기
• 두 번째, cnt = 1로 초기화(자기 자신)하고 end 포인터가 N이 되면 반복 탈출
• 세 번째, sum > N일 때 start 포인터 움직이기

최종

import java.util.Scanner;
public class Baek2018 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int sum = 1;
        int start = 1;
        int end = 1;
        int cnt = 1;

        while(end != N ){
            if(sum > N){
                sum = sum - start;
                start++;
            }else if(sum < N){
                end++;
                sum = sum + end;
            }else{
                sum = sum - start;
                start++;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

참고

(sum == N) 일 때는 (sum > N)에서 하는 동작이나 (sum < N)에서 하는 동작 중 선택.
cnt++는 필수!!

시간복잡도 줄이쟈!