728x90
반응형
문제: https://www.acmicpc.net/problem/1253
1253번: 좋다
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
www.acmicpc.net
책에서 나오는 투 포인터 마지막 문제다. 책에서는 골드 3이라고 되어있는데, 현재는 골드 4로 내려갔다.
따끈따끈하게 실버로 올라온 뉴비에겐 솔직히 이 문제 너무 어려웠다.
책에 있는 풀이를 봐도 이해가 안됐다. 사실 한번 급하게 삽질을 끝낸 적은 있었는데,
다시 하려니까 같은 곳에서 해맨 것이다.
암튼 서론은 여기까지 하고 이제 본론으로 들어가자.
N을 입력받고 N개의 숫자들을 입력을 받고나서 이 숫자들끼리 서로 더해서 배열 안에 있는 요소가 되면
그게 문제에서 얘기하는 '좋은 수'인 것이다. 아 근데 자기 자신을 더해서 그 숫자가 나오는건 제외한다.
ex) 1+1 = 2, 2+2 = 4 ... 왜냐하면 문제에서 "수의 위치가 다르면 값이 같아도 다른 수이다."라고 했다.
이것을 대우로 뒤집어보면 "값이 달라도 같은수이면 수의 위치가 같다." 와 같은 문장이 된다.
결국 같은 수끼리는 더하면 안된다는 말이 문제에 내포되어있는 것이다.
다만 이건 필자같은 코린이들에게는 흐름이 좀 어려울 수 있으니, 그림으로 설명을 해보겠다.
N은 5이며 1 2 3 4 5 를 입력받았다고 가정하자.
그럼 이제 이 흐름들을 토대로 코드를 짜볼 시간이다.
import java.util.*;
import java.io.*;
public class BOJ_1253_4 {
public static void main(String[] args) throws IOException{
// TODO 백준 1253
//입력을 빨리 받기 위한 BufferedReader 클래스 객체 선언
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//한 줄에 하나만 입력 받는다면 StringTokenizer 클래스를 이용한
//문자열 파싱이 필요가 없음.
//nums라는 배열 선언 -> 숫자들을 저장할 배열
int N = Integer.parseInt(br.readLine());
int nums[] = new int[N];
//한 줄에 여러개의 숫자들을 입력받아야 하기 때문에 파싱이 필요해짐.
//StringTokenizer 클래스 객체 선언해줌.
//for문을 이용해서 배열에 파싱한 숫자들을 하나씩 저장해준다.
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
//배열의 내용물을 정렬해준다. 투 포인터 알고리즘을 사용해야 하기 때문이다.
//answer는 '좋은 수'의 개수를 카운팅하기 위한 변수다.
Arrays.sort(nums);
int answer = 0;
//서로 더해서 나와야 하는 값을 target 변수로 설정했음.
//target에 배열의 각 요소 값들이 저장되어야 하므로 for문으로
//while(투 포인터 반복문)을 감싸준다.
for(int i=0; i<N; i++) {
int target = nums[i];
int start = 0, end = N-1;
//투 포인터 알고리즘
while(start < end) {
//sum은 반복문 안에서 값이 계속 바뀌어야 함.
//sum과 target의 값을 비교해야 하기 때문.
int sum = nums[start] + nums[end];
//sum이랑 target이 같을 경우엔 start와 end를 한번 더 체크해준다.
//그래야 자기 자신과 더해서 좋은 수를 찾지 않을 수 있기 때문이다.
if(sum == target) {
if(start != i && end != i) {
++answer;
break;
} else if(start == i) {
++start;
} else {
--end;
}
} else if(sum < target) {
//sum값이 target보다 작다면 값을 늘려줘야 하므로,
//start를 늘려준다.
++start;
} else {
//else라면 sum > target 경우밖에 남지 않는데,
//이는 sum의 값을 줄여줘야 하므로 end를 줄여준다.
--end;
}
}
}
//for문과 while문에서 나온 후 answer를 출력해준다.
System.out.println(answer);
}
}728x90
반응형
'☕JAVA > 👩💻BOJ(백준)' 카테고리의 다른 글
| [투 포인터, JAVA] 백준 - 1940 (2) | 2022.09.20 |
|---|---|
| [투 포인터, JAVA] 백준 - 2018 (0) | 2022.09.19 |
| [투 포인터, JAVA] 백준 - 2467 (0) | 2022.09.19 |
| [구간합, JAVA] 백준 - 10986 (0) | 2022.08.20 |
| [구간합, JAVA] 백준 - 11660 (0) | 2022.08.17 |
