(1)자료구조 ③ 투 포인터

 

*️⃣ 투포인터

 

-  투 포인터는 2개의 포인터로 알고리즘의 시간복잡도를 최적화 한다.
- 시간 인덱스와 종료 인덱스를 투포인터로 지정하여 문제에 접근하는 방식

 

 

 

1. 연속된 자연수의 합 구하기

 

 

 

• 문제

Q. 어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다.            당신은 어떤 자연수 N(1≤N≤10,000,000)을 몇 개의 연속된 자연수는 N이어야 한다.            예를 들어 15을 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다.            반면, 10을 나타내는 방법은 10, 1+2+3+4이다.            N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.
[입력]	[출력]
1번째 줄에 정수 N (1≤N ≤10,000,000)이 주어진다.	입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.
[입력]	[출력]
15	4

 

 

• 시간복잡도

제한시간: 2초 N의 최댓값은 10,000,000 O(nlogn) 알고리즘 이용할시, 시간초과 O(n) 알고리즘 이용필수  -----> 투 포인터

 

 

• 풀이방법

1. 입력받은 값을 N에 지정한 후 코드에 사용할 변수를 모두 초기화하기     (결과변수 count= 1로 초기화 이유 -----> N이 15일 때 숫자 15만 뽑는 경우의 수) 2. 배열을 탐색하면서 N이 될 경우의 수 구하기  ( start_index →  //  end_index  → )      연속된 수의 합이 N이 될 때 결과값↑ 3. 이동할 떄마다 현재의 총합과 N을 비교해 값이 같으면 count 1만큼 증가

 

 

• 이동방법

<<<<  이동방식  >>>>

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 = 15 sum == N; count = 2, end_index++;

sum = sum + end_index = 21 sum > N; count = 2, start_index++;

sum = sum - start_index = 20 sum > N; count = 2, start_index++;

 

      start_index

            ⬇️

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

                                                 ⬆️

                                           end_index

 

 

• 코드 순서

1. n 변수 저장 2. 사용자 변수 초기화(count = 1, start_index = 1, end_index=1, sum=1) 3. while end_index !=n:    if sum == n : 경우의 수 증가, end_index 증가, sum값 변경    elif sum > n : sum 값 변경, start_index 증가    else: end_index 증가, sum 값 변경 4. 경우의 수 출력

 

 

• 정답

n = int(input())              count = 1              start_index = 1              end_index = 1              sum = 1              while end_index != n:                  if sum == n:                     count += 1                     end_index += 1                     sum += end_index                 elif sum > n:                     sum -= start_index                     start_index += 1                 else:                     end_index += 1                     sum += end_index            print(count)
[입력]	[출력]
15	4

 

n = int(input())              count = 1              start_index = 1              end_index = 1              sum = 1              while end_index < n/2 +1 :                  if sum == n:                     count += 1                     end_index += 1                     sum += end_index                 elif sum > n:                     sum -= start_index                     start_index += 1                 else:                     end_index += 1                     sum += end_index            print(count)

 

 

 

2. 주몽의 명령

 

 

 

• 문제

Q. 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다.          그래서 야철대장에게 철기군이 입을 갑옷을 만들라고 명령했다.          야철대장은 주몽의 명령에 따르기 위해 연구에 착수하던 중 갑옷을 만드는 재료들은 각각 고유한 번호가 있고,          갑옷은 2개의 재료로 만드는 데 2가지 재료의 고유한 번호를 합쳐 M(1≤M≤10,000,000)이 되면          갑옷이 만들어진다는 사실을 발견했다.          야철대장은 자신이 만들고 있는 재료로 갑옷을 몇개 만들 수 있는지 궁금해졌다.          야철대장의 궁금증을 풀어주기 위해 N(1≤N≤15,000)개의 재료와 M이 주어졌을 때          몇 개의 갑옷을 만들 수 있을지를 구하는 프로그램을 작성하시오.
[입력]	[출력]
1번째 줄에 재료의 개수 N ( 1 ≤ N ≤ 15,000 )	1번째 줄에는 갑옷을 만들 수 있는 개수를 출력
2번째 줄에는 갑옷을 만드는 데 필요한 수 M (1 ≤ M ≤ 100,000,000)
3번째 줄에는 N개의 재료들이 가진 고유한 번호, 공백을 기준 (고유한 번호 ≤ 100,000)
[입력]	[출력]
6 9 2 7 4 1 5 3	2

 

 

• 시간복잡도

1. N의 최대범위 15,000 2. O(nlongn) 문제 없음 3. 정렬알고리즘 + 투포인터로 지정해 문제에 접근

 

 

• 풀이방법

1.  재료 데이터를 리스트A에 지정한 후 오름차순으로 정렬하기 2. 투 포인터 i, j를 양쪽 끝에 위치시킨 후 문제의 조건에 적합한 포인터 이동원칙을 활용해 탐색을 수행 3. i와 j가 만날 때까지 반복, 반복이 끝나면 count 출력

 

• 이동방법

<<<< 이동방식 >>>>

A [i] + A [j]  >  M : j -- ;       A [i] + A [j]  <  M : i++;       A [i] + A [j] == M : i++ ; j -- ; count++;

<<<<   실행    >>>>

A[0] + A[5] = 8 < M  => i++

A[1] + A[5] = 9 == M  => count++; i++; j--;

A[2] + A[4] = 8 < M  => i++

A[3] + A[4] = 9 == M  =>  count++; i++; j--;

 

1

2

3

4

5

7

 

                                    ⬆️        ⬆️

                                      i            j

 

 

• 코드 순서

1. N (재료의 개수), M(갑옷이 되는 번호) 선언 2. A (재료 데이터 저장 리스트) , A 리스트 정렬하기 3. i ( 시작 인덱스 = 0 ), j ( 종료 인덱스 = N-1) , count ( 정답값 = 0 ) 4. while i < j :         if 재료 합 < M : 작은 번호 재료를 한 칸 위로 변경         elif 재료 합 > M : 큰 번호를 한 칸 아래로 변경         else 경우의 수 증가, 양쪽 index 각각 변경 5.  count 출력

 

• 정답

N = int(input());             M = int(input());             A = list(map(int, input().split()))             A.sort()             count = int(0)             i = int(0)             j = int(N-1)             while i < j:                     if A[i] + A[j] < M:                     i += 1                 elif A[i] + A[j] > M:                     j -= 1                 else:                     count += 1                     i += 1                     j -= 1             print(count)
[입력]	[출력]
6 9 2 7 4 1 5 3	2

 

 

 

3. '좋은 수' 구하기

 

• 문제

Q. 주어진 N개의 수에서 다른 두 수의 합으로 표현되는 수가 있다면            그 수를 '좋은 수'라고 한다.            N개의 수 중 좋은 수가 총 몇 개인지 출력하시오.
[입력]	[출력]
1번째 줄에 수의 개수 (1 ≤ N ≤ 2,000)	좋은 수의 개수를 출력한다.
2번째 줄에 N개의 수의 값(Ai)이 주어진다. (lAil ≤ 1,000,000,000 , Ai는 정수)
[입력]	[출력]
10 1 2 3 4 5 6 7 8 9 10	8

 

 

• 시간복잡도

1. N의 개수가 최대 2,000   2. 하나를 찾는 알고리즘의 시간 복잡도는 N²보다 작아야 합니다.  3. 좋은 수 하나를 찾는데 시간 복잡도가 N²인 알고리즘을 사용하면 시간복잡도는 N³가 되어 제한시간 초과 4. 좋은 수 하나를 찾는 알고리즘의 시간복잡도는 최소 O(nlogn)이어야 함 5. 정렬 + 투포인터 알고리즘 사용 6. 단, 정렬된 데이터에서 자기 자신을 좋은 수 만들기에서 포함하면 안 됨

 

 

• 풀이방법

1. 수를 입력받아 리스트에 저장한 후 오름차순으로 정렬 2. 투포인터 i, j를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙을 활용해 탐색을 수행합니다.    (판별의 대상이 되는 수는 K라고 가정합니다.) 3. K가 N이 될 때까지 반복하며 좋은 수가 몇개인지 샙니다.

 

 

 

• 이동방법

<<<< 이동방식 >>>>

A [i] + A [j]  >  K : j -- ;        A [i] + A [j]  < K : j ++ ;       A [i] + A [j]  == K : count++;

<<<<   실행    >>>>

i j 만날 때까지 두 수의 합이 1이 되는 경우가 없으므로 종료

i j 만날 때까지 두 수의 합이 2이 되는 경우가 없으므로 종료

i =1 j=2 일 때,  두 수의 합이 3  ==> count++ 프로세스 종료

i =1 j=3 일 때,  두 수의 합이 4  ==> count++ 프로세스 종료

i =1 j=4 일 때,  두 수의 합이 5  ==> count++ 프로세스 종료

 

K

   ⬇️

1

2

3

4

5

6

7

8

9

10

 

 

 

• 코드 순서

1. N (데이터 개수) , Result (좋은 수 개수 저장 변수) 2. A (수 데이터 저장 리스트) , A (리스트 정렬) 3. for N만큼 반복:     변수 초기화 ( 찾고자 하는 값 fine = A [k], 포인터 i, 포인터 j )     while i < j :        if A[i] + A[j] == find :           두 포인터 i, j가 k가 아닐 때 좋은 수 개수 1 증가 및 while 문 종료           두 포인터가 i 나 j가 k가 맞을 때 포인터 변경 및 계속 수행        elif A[i] + A[j] < find : 포인터 i 증가        else : 포인터 j 감소      4. 좋은 수 개수 출력

 

• 정답

N = int(input())        Result = 0         A = list(map(int, input().split()))         A.sort()         for k in range(N):             find = A[k]             i = int(0)             j = int(N - 1)           while i < j:  # 투 포인터 알고리즘                 if A[i] + A[j] == find:  # find는 서로 다른 두 수의 합 이어야 함을 체크                     if i != k and j != k:                         Result += 1                         break                     elif i == k:                         i += 1                     elif j == k:                         j -= 1                 elif A[i] + A[j] < find:                     i += 1                 else:                     j -= 1         print(Result)
[입력]	[출력]
10 1 2 3 4 5 6 7 8 9 10	8

 

N = int(input())        Result = 0         A = list(map(int, input().split()))         A.sort()         for k in range(N):             find = A[k]             i = int(0)             j = int(N - 1)           while i < j:  # 투 포인터 알고리즘                 if A[i] + A[j] == find:  # find는 서로 다른 두 수의 합 이어야 함을 체크                     if i != 0 or j != 0:                          i += 1                           j -= 1                      else j == k:                         Result +=1                         break                 elif A[i] + A[j] < find:                     i += 1                 else:                     j -= 1         print(Result)
[입력]	[출력]
10 1 2 3 4 5 6 7 8 9 10	8