투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 알고리즘이 매우 간단하기에 어렵지는 않을것이다.
문제
연속된 자연수의 합 구하기 - 백준2018번
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
아니근데 15를 나타낼 때 15하나만 뽑으면 연속된 자연수냐?
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력│←
1번째 줄에 정수 N이 주어진다
출력│→
입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.
추가 사항
제한 시간 : 2초
난이도 : 실버 5
성공률 : 48%
문제 분석하기
해당 문제는 N의 최대값이 10,000,000으로, O(nlogn)이상의 시간 복잡도를 가지는 알고리즘이라면 모두 제한시간을 초과하게 된다.
따라서 O(n)의 복잡도를 가지는 알고리즘을 사용해야하고 이럴 때 자주 사용하는 방법이 투 포인터이다.
연속된 자연수의 합을 구하는 것이 목표이기에 시작 인덱스와 종료 인덱스를 가각 다른 포인터로 지정하여 문제에 접근해 보자.
투 포인터 활용하기
-
입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화 해 준다. 결과 변수 count를 1로 초기화 하는 이유는 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 넣고 초기화했기 때문이다.
-
투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하며 합이 N이 될 경우의 수를 구해준다.
투 포인터 이동 원칙
- sum이 N보다 클 때 :
sum = sum - start_index; start_index++;- sum이 N보다 작을 때 :
end_index++; sum = sum + end_index;- sum과 N이 같을 때 :
end_index++; sum = sum + end_index; count++;
sum과 N이 같을 때 start_index++;를 하지말고 end_index++;를 하자, start_index++를 하면 몇몇 경우의 수를 빼 먹을 수 있다.
또한 for문을 통해 start_index위치부터 end_index위치까지 계산마다 더하지 말고, 이미 계산 된 sum 변수에 포인터를 옮길 때 마다 start_index가 움직였다면 값을 빼고, end_index가 움직였을 땐 값을 더하는 식으로 구성한다.
그렇지 않고 for문으로 작성할 경우, 복잡도가 늘어나 시간 내에 풀지 못한다.
- 2단계를 end_index = N이 될 때까지 반복하며 포인터가 이동할 때마다 현재의 총합과 N을 비교해 값이 같으면 count++를 해준다.
첫 상태를 보자 이미 end_index가 5번 뒤로 물러나 sum에 2,3,4,5를 더한 상태이다. 따라서 sum은 현재 15이고 이는 N과 일치한다.
sum == N이 충족됐기에 count를 1늘려주고 sum += ++end_index를 해 준다.
sum은 이제 21이고 이는 N보다 크다. 따라서 sum -= start_index++로 sum을 20으로 만듦과 동시에 start_index를 한 칸 뒤로 옮긴다.
이렇게 진행하다보면 N = 15기준 아래 두번의 경우에서 count++를 실행하게 되고 최종적으로 count는 4가된다.
end_index가 15가 되면 반복문을 탈출한다.
15라는 수도 15의 연속된 수로 보기 때문에 처음에 count변수의 초기화를 1로 설정 해 둔것.
코드
public class 연속된자연수의합구하기2018 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 1; // end_index가 N이 되는경우 바로 반복문 탈출을 위해 초기화를 0이 아닌 1로한다.
int start_index = 1;
int end_index = 1;
int sum = 1;
while (end_index != N) {
if (sum == N) {
count++;
end_index++;
sum += end_index;
} else if (sum > N) {
sum -= start_index;
start_index++;
} else {
end_index++;
sum += end_index;
}
}
System.out.println(count);
}
}쉬운 코드이기에 자세한 설명은 생략
주몽의 명령 - 백준1940번
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
입력│←
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
출력│→
1번째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
추가 사항
제한 시간 : 2초
난이도 : 실버4
성공률 : 47%
문제 분석하기
문제 풀이에 앞서 시간 복잡도를 고려해 보자. N의 최대 범위가 15,000이기 때문에, O(nlogn)알고리즘을 사용해도 문제가 없다. 버블,선택,삽입정렬을 제외한 나머지 정렬들은 거의 해당범위 내에 들어오기 때문에 위 3개만 제외하고 사용하면 되겠다.
또, 두 재료번호의 합을 구하는게 핵심이니 투 포인터를 사용하면 되고 정렬 후에 사용하는게 문제를 좀 더 적은자원으로 풀 수 있다.
정렬 알고리즘과 투 포인터 사용하기
투 포인터를 사용하기 위해서는 일단 정렬을 해야한다. 값이 274153처럼 무작위인 경우 각 포인터를 줏대없이 움직여가며 합을 찾는데 이런 브루트-포스법 보다는
오름차순으로 정렬하여 두 포인터의 합보다 M이 작다면 왼쪽 포인터를 옮기고,
크다면 오른쪽 포인터를 옮기면 된다.
이해가 안된다면 아래 각각의 상황과 그림을 보며 이해해 보자.
- 정렬이 안된 배열
한개의 포인터가 숫자 한개를 잡고, 나머지 포인터가 다른 모든 경우의 수를 전수조사해나가며 경우의 수를 찾는다. 또, 찾은 경우에 해당 요소를 배제해야하는 배열도 만들어야 한다.(다음 검색 때 위치를 기억해야 함)
따라서 최악의 경우 11,250,000,000번 계산해야 한다. 이는 제한 시간 2초 즉, 2억번 이내의 연산을 아득히 뛰어넘는 수치이므로 사용할 수 없다.
- 정렬이 된 배열 (참고로 M = 9)
그림만 봐도 무슨말인지 이해가 끝 날 것이다.
각 포인터 가 이동하는 원칙은 아래 3가지를 따르면 된다.
파란색 포인터가 i, 검정색 포인터가 j라고 가정하고 작성하겠다.
투 포인터의 이동 법칙
- A[i] + A[j] > M인 경우 = j--;
합이 M보다 크기 때문에 큰 번호 쪽 포인터를 움직여 값을 낮춘다.
- A[i] + A[j] < M인 경우 = i++;
합이 M보다 작기 때문에 작은 번호 쪽 포인터를 움직여 값을 높인다.
- A[i] + A[j] == M인 경우 = i++; j--; count++;
양쪽 포인터를 움직이고(재료는 겹치면 안됨) 정답 개수 1증가 시킴.
매우 간단하니 더이상의 설명은 생략하자.
코드
public class 주몽1940 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[] A = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
int count = 0;
int i = 0;
int j = N - 1;
while (i < j) { // 투 포인터 이동
if (A[i] + A[j] < M) {
i++;
} else if (A[i] + A[j] > M) {
j--;
} else {
i++;
j--;
count++;
}
}
System.out.println(count);
br.close();
}
}※ 참고로 Arrays.sort()에 기본자료형 배열을 넣으면 퀵 정렬의 개선버전인 '이중 피벗 퀵 정렬'을 수행해 준다. 그러니 속도는 걱정말자 :)
※ 참조형의 경우 Arrays.sort()에 넣으면 1.7버전 이후 기준 병합 정렬의 개선 버전인 'Tim Sort'를 수행해 준다. 이것도 속도가 매우 빠르니 걱정말자.
