[백준] 2018 : 수들의 합 5 - JAVA

투포인터 이용! O(N)

시간복잡도

N이 10,000,000으로 꽤 크다.
시간제한은 2초이므로, O(NlogN)까지만가도 2초가 넘는다.
따라서 O(N)으로 해결해야하며, 투포인터는 이에 해당한다.

슈도코드

N 입력받기

start = 0
end = 0
sum = 0
answer = 0
1~N까지 수가 차례대로 나열 된 배열 A

sum = A[start] + A[end]
if(N > sum) {
	end ++
    sum += A[end]
}

if( N < sum ) {
	start --
    sum -= A[start]
}

if( N == sum ) {
	answer++
	end ++
    sum += A[end]
}

answer 출력

Troubleshooting 1

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int start = 1;
		int end = 1;
		int sum = 0;
		int answer = 0;

		for(; end<N+1; end++) {
			sum = start + end;
			if(N > sum) {
				end ++;
			    sum += end;
			}

			if( N < sum ) {
				start --;
			    sum -= start;
			}

			if( N == sum ) {
				answer++;
				end ++;
			    sum += end;
			}
		}
		System.out.println(answer);
	}
}

문제점

IDE에서 돌리고 예제(15)를 입력했을 때 결과가 0으로 나왔다.

원인

1. 우선 for문의 증감식에 end++을 하면 안된다. 조건에따라 end++ 혹은 start++를 하기 때문이다.
2. 초기 sum값은 2가 아니다.
3. 초기 answer 값은 0이 아니다.
4. sum이 N보다 클 경우, start를 하나 앞으로 당기는 것은 start--이 아니다.
5. 한 번 for문을 돌 때, 세 조건 중 한 가지에만 해당되어서 한 과정만 수행해야하는데, 디버깅을 해보니 셋 다 if문으로 짜서 한 번 for문을 돌 때마다 셋 다 무조건 검사한다.
   즉 첫번째 if문이 T이면, 해당 과정을 수행하고 다음 for문으로 넘어가야하는데 두번째 if문을 검사하고, 또 세번째 if문을 검사한다. 이런경우 한 번의 for문에서 2~3개의 과정이 동시에 일어날수 있다.
6. start를 이동시키고, sum에서 start를 뺐다.
   end, start 이동과 sum에 연산하는 과정의 순서를 중요하게 생각하지않았다.

해결

1. for문에서 초기식, 조건식, 증감식 모두 생략가능하다. -> 증감식을 지운다.
2. start와 end 모두 1에 있지만, 1+1 이 아닌 1만 선택하는것이기때문에 sum=1로 초기화한다.
3. start와 end가 N이라서 N하나만 뽑는 경우의 수를 미리 넣고 초기화해야하기때문에, answer = 1로 초기화.
4. start만큼 뺀다는 말이 헷갈려서 start-- 를 했다. start++를 해야한다!
5. if-if-if -> if- else if- else if로 수정한다.
6. sum<N 이라서 end를 한 칸 늘리고, 해당 값을 더할때는 순서가 end++ -> sum + end
   이지만, sum>N 이라서 start를 한 칸 늘리고, 해당 값을 뺄때는 순서가 sum - start -> start++이다.
   순서가 중요하다!!

Troubleshooting 2

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int start = 1;
		int end = 1;
		int sum = 1;
		int answer = 1;

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

문제점

처음에 많은것을 놓쳤었고 이를 다 수정했지만, 15를 입력했을 때 결과가 5로 나왔다. (결과는 4이어야한다)

원인

디버깅을 해보니, for문의 조건식을 end<N+1로 줘서 end가 15일때 구간합을 구하고 N과 동일한지 체크하고 끝나는게아니라, end가 16으로 올라갈때까지 start를 변경할 수 있고 그 과정을 계속 수행한다.
따라서 start == end == 15 일때도 수행해서 answer이 하나 더 큰 5가 나오는것이었다.

end가 N에 도달하면, start가 어떻든 특정 구간합은 무조건 N보다 크게된다. 따라서 이후 과정은 필요없는 과정에 해당한다.

해결

for() -> while(N != end)로 수정했다.

제출코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int start = 1;
		int end = 1;
		int sum = 1;
		int answer = 1;

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

공부한 사항

• 투 포인터

주의할 점

• 초기 answer값은 0이 아닌, 1이다!
  이유는 end가 N에 도달하면 끝나는데, start와 end가 N이라서 N하나만 뽑는 경우의 수를 미리 넣고 초기화해야하기때문이다.