💡 두 포인터의 합과 차 - 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결합니다. - 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있습니다.
아래의 문제는 입력 값이 주어지면 숫자들의 합을 하였을 때, 입력 값을 구하는 가짓수를 구하는 문제입니다.
💡 문제
- 어떠한 자연수 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가지가 있다. - N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
💡 아래의 그림과 같이 sum으로 15를 구하기 위해 루프를 기준으로 처리과정을 확인합니다.
💡 이미지의 처리 과정-1
⭕️ Loop1 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 2의 값을 가집니다. - 합은 3이 되므로 ‘합이 input 보다 작은 경우’로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop2 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 2 → 3으로 이동하여 3의 값을 가집니다. - 합이 6이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop3 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 3 → 4으로 이동하여 4의 값을 가집니다. - 합이 10이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop4 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 4 → 5으로 이동하여 5의 값을 가집니다. - 합이 15이 되므로 ‘합과 input 값이 같은 경우’로 Count를 1 증가합니다. 또한 endIndex를 다음 단계에 오른쪽으로 이동합니다.
⭕️ Loop5 - 시작 인덱스는 1의 값을 가집니다. - 마지막 인덱스 값은 5 → 6으로 이동하여 6의 값을 가집니다. - 합이 21이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(1→2)
💡 이미지 처리 과정 -2
⭕️ Loop 6 - 시작 인덱스는 2의 값을 가집니다 - 마지막 인덱스 값은 6의 값을 가집니다. - 합은 20이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(2→3)
⭕️ Loop 7 - 시작 인덱스는 3의 값을 가집니다. - 마지막 인덱스 값은 6의 값을 가집니다. - 합은 18이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(3→4)
⭕️ Loop 8 - 시작 인덱스는 4의 값을 가집니다. - 마지막 인덱스 값은 6의 값을 가집니다. - 합이 15이 되므로 ‘합과 input 값이 같은 경우’로 Count를 1 증가합니다. 또한 endIndex를 다음 단계에 오른쪽으로 이동합니다.
💡 이미지 처리 과정 -3 ⭕️ Loop 8 - 시작 인덱스는 4의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합은 3이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(4→5)
⭕️ Loop 9 - 시작 인덱스는 5의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합은 18이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(5→6)
⭕️ Loop 10 - 시작 인덱스는 6의 값을 가집니다. - 마지막 인덱스 값은 7의 값을 가집니다. - 합이 13이 되므로 합이 input 보다 작은 경우로 다음 단계에 endIndx를 이동합니다.
⭕️ Loop 11 - 시작 인덱스는 6의 값을 가집니다. - 마지막 인덱스 값은 8의 값을 가집니다.합은 21이 되므로 ‘합이 input 보다 큰 경우’로 이전 startIndex를 빼고 다음 단계에 startIndex를 더합니다(6→7)
- 아래와 같은 과정으로 endIdx 값이 15에 이를 때까지의 만족하는 가짓수를 구합니다.
💡 투 포인터 슬라이딩 윈도우 (Sliding Window with Two Pointers) - 고정된 길이의 윈도우를 배열이나 리스트에서 슬라이딩하면서 특정 조건을 만족하는 부분 구간을 찾는 문제에 사용됩니다. - 예를 들어, 최대 연속 부분 배열의 합을 구하는 등의 문제에 적용할 수 있습니다.
💡 백준 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보다 작거나 같은 자연수이다.
4.1. 시작 인덱스와 마지막 인덱스를 더했을 때, m보다 작은 경우 : 시작 값 오른쪽 이동
4.2. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 큰 경우 : 마지막 값을 왼쪽으로 이동
4.3. 시작 인덱스와 마지막 인덱스를 더했을때, m과 같은 경우 : 카운트 값을 올리고 시작 값을 오른쪽 이동, 끝값을 왼쪽으로 이동
5. 최종 카운팅 된 값을 반환합니다.
/**
* 07. 주몽 : 백준 1940번
* 재료들을 기반으로 만들 수 있는 갑옷의 개수를 구하는 문제
*
* @return ResponseEntity
* @link <https://www.acmicpc.net/problem/1940>
* @since 2024.01.06
*/@GetMapping("/7")public ResponseEntity question07() {
intanswer=0;
intn=6; // 재료의 개수intm=9; // 갑옷을 만드는데 필요한 수Stringinput3="2 7 4 1 5 3"; // 재료들// 1. 배열을 구성하며 문자열 배열을 정수 배열로 캐스팅 합니다.
String[] materialStrArr = input3.split("");
int[] materialArr = newint[materialStrArr.length];
for (inti=0; i < input3.split("").length; i++) {
materialArr[i] = Integer.parseInt(input3.split("")[i]);
}
// 2. 정수 배열을 오름차순으로 정렬합니다.
Arrays.sort(materialArr);
intcount=0; // 갑옷을 만들수 있는 가짓수intstartIdx=0; // 투포인터의 시작 인덱스intlastIdx= n - 1; // 투포인터의 마지막 인덱스// 3. 시작 인덱스 보다 마지막 인덱스 값이 크면 종료합니다.while (startIdx < lastIdx) {
// 4.1. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 작은 경우 : 시작 값 오른쪽 이동if (materialArr[startIdx] + materialArr[lastIdx] < m) {
startIdx++;
}
// 4.2. 시작 인덱스와 마지막 인덱스를 더했을때, m보다 큰 경우 : 마지막 값을 왼쪽으로 이동elseif (materialArr[startIdx] + materialArr[lastIdx] > m) {
lastIdx--;
}
// 4.3. 시작 인덱스와 마지막 인덱스를 더했을때, m과 같은 경우 : 카운트 값을 올리고 시작 값을 오른쪽 이동, 끝값을 왼쪽으로 이동else {
count++;
startIdx++;
lastIdx--;
}
// 5. 최종 카운팅 된 값을 반환합니다.
answer = count;
}
returnnewResponseEntity<>(answer, HttpStatus.OK);
}
💡 아래와 그림과 같이 sum으로 9를 구하기 위해 루프를 기준으로 처리과정을 확인합니다. ⭕️ Loop 1 - 시작값 1과 마지막 값 7로 시작을 합니다. - 두 개의 합이 8인 경우이며 m인 9보다 작습니다. - 해당 경우는 Loop2에서 startIdx 값이 1 증가됩니다.
⭕️ Loop2 - 시작 값 2와 마지막 값 7로 시작을 합니다. - 두 개의 합이 9인 경우이며 m의 값인 9와 같습니다. - 그렇기에 count의 값을 증가합니다. 해당 경우는 Loop3에서 시작값을 1 증가하고 마지막 값을 1 감소합니다.
⭕️ Loop3 - 시작 값 3과 마지막 값 5로 시작을 합니다. - 두 개의 합이 8인 경우이며 m의 값보다 작습니다. - 해당 경우는 Loop4에서 시작 값이 1 증가됩니다.
⭕️ Loop4 - 시작 값 4와 마지막 값 5로 시작을 합니다. - 두 개의 합이 9인 경우이며 m 값인 9와 같습니다. - 그렇기에 count의 값을 증가합니다. 해당 경우는 다음이 불가하기에 루프를 종료합니다.
💡 두 포인터의 합과 차 - 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결합니다. - 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있습니다.
/**
* 08. 좋은 수: 백준 1253번
* N 개의 수에서 다른 두수의 합으로 표현되는 수가 있다면 좋은수이고 총 몇개인지 출력
*
* @return ResponseEntity
* @link <https://www.acmicpc.net/problem/1940>
* @since 2024.01.15
*/@GetMapping("/8")public ResponseEntity question08() {
intcount=0;
intinput1=10;
// [STEP1] 문자열을 배열로 변환Stringinput2="1 2 3 4 5 6 7 8 9 10";
String[] inputArr = input2.split(" ");
// [STEP2] 숫자 배열로 변형int[] inputIntArr = newint[inputArr.length];
for (inti=0; i < inputArr.length; i++) {
inputIntArr[i] = Integer.parseInt(inputArr[i]);
}
// [STEP3] 숫자 배열을 순회하면서 값을 구함for (inti=0; i < inputIntArr.length; i++) {
intstartIdx=0; // 시작 인덱스intendIdx= input1 - 1; // 마지막 인덱스intfindItem= inputIntArr[i]; // 순회되는 값// [STEP4] 값을 기준으로 다음 값과 비교합니다.while (startIdx < endIdx) {
// [STEP4-1] 시작 값과 종료값의 합이 찾는 값과 같은 경우if (inputIntArr[startIdx] + inputIntArr[endIdx] == findItem) {
// [CASE1] 시작 인덱스, 종료 인덱스와 같이 않을 경우 : 종료if (startIdx != i && endIdx != i) {
count++;
break;
}
// [CASE2] 시작 인덱스와 같은 경우 : 시작 인덱스 오른쪽으로 이동elseif (startIdx == i) {
startIdx++;
}
// [CASE3] 종료 인덱스와 같은 경우 : 마지막 인덱스 왼쪽으로 이동elseif (endIdx == i) {
endIdx--;
}
}
// [STEP4-2] 시작값과 종료값의 합이 찾는 값보다 작은 경우 : 시작 값을 오른쪽으로 이동elseif (inputIntArr[startIdx] + inputIntArr[endIdx] < findItem) {
startIdx++;
}
// [STEP4-3] 시작값과 종료값의 합이 찾는 값보다 큰 경우 : 종료 값을 왼쪽으로 이동else {
endIdx--;
}
}
}
returnnewResponseEntity<>(count, HttpStatus.OK);
}
