배열에서 두 수의 합이 s가 되는 경우의 수(서로 다른 방향으로 움직이는 투 포인터)

29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로  모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 9. 2.
• textsms

[Java]HashMap 응용력 키우기2 -두 수의 합과 세 수의 합 그리고 네 수의 합-

1. 문제 n개의 정수가 입력으로 주어지고, 이 중 서로 다른 위치에 있는 두 개의 수를 뽑아 더했을 때 k가 되는 가짓수를 구하는 프로그램을 작성해보세요. 2. 풀이 가장 쉬운 방법은 $O(N^{2})$으로 해결하는 것이다. 배열에 N개의 정수를 모두 저장하고, 2중 for문을 돌아서 모든 쌍을 검사해서 합이 k가 되는지 검사해보는 것이다 하지만 N의 제한이 최대 10만이라면? 당연히 $O(N^{2})$의 알고리즘을 요구하는 문제는 아닐 것이다 합이 k가 되는 두 원소는 어떻게 선택할 수 있을까? 배열에서 한 원소를 골랐을때, 다른 원소는 무조건 k - (이전에 고른 원소)를 골라야할 것이다. 그러므로, HashMap에 배열의 모든 원소의 정보를 저장해두고, 배열에서 한 원소를 고르는 작업을 O(N)에..

• format_list_bulleted 중간에서 만나기
• · 2023. 3. 27.
• textsms