🙋정렬 + 투 포인터 알고리즘 사용
슈도코드
main() {
N받기(수의 개수)
A[] = Ai받기 (i번째 수)
solution
}
solution(start, end,N, count, A) {
boolean check =true
for(i : N만큼 반복) {
while(check) {
int sum = A의 start 번째 + A의 end 번째
if( sum > A[i] ) {
end --
}
if( sum < A[i] {
start ++
}
if( sum == A[i] {
count++
check = false
}
if(end == start) check = false
}
}
}Troubleshooting
public class goodNumber {
public static int solution(int[] A,int N) {
boolean check =true;
int answer = 0;
for(int i =0; i<N; i++) {
int end = N-1;
int start = 0;
while(check) {
int sum = A[start] + A[end];
if( sum > A[i] ) end-- ;
else if( sum < A[i]) start++ ;
else if( sum == A[i]) {
answer++;
check = false;
}
if(end == start) check = false;
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st= new StringTokenizer(br.readLine());
int[] A = new int[N];
for(int i =0; i <N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
System.out.println(solution(A, N));
}
}
문제
콘솔 결과가 주어진 예시와 다르게 0으로 찍힌다.
원인
sum == A[i] 혹은 end == start 일 때, check = false를 하고 되돌리지 않는게 문제였다.
while을 한 번 돌고 나간 후에는, 다시 그 다음 원소로 while문을 돌아야하므로 check가 true이어야하는데, 이전에 바꾼 후 돌리지않아서 while안으로 들어오지 않는것이었다.
해결
while을 나온 후 바로 check=true를 해주었다.
Trubleshooting2
public class Main {
public static int solution(int[] A,int N) {
boolean check =true;
int answer = 0;
for(int i =0; i<N; i++) {
int end = N-1;
int start = 0;
while(check) {
int sum = A[start] + A[end];
if( sum > A[i] ) end-- ;
else if( sum < A[i]) start++ ;
else if( sum == A[i]) {
answer++;
check = false;
}
if(end == start) check = false;
}
check = true;
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st= new StringTokenizer(br.readLine());
int[] A = new int[N];
for(int i =0; i <N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
System.out.println(solution(A, N));
}
}문제
당연히 맞은줄알고 제출했는데, 너무나 빨간글씨로 '틀렸습니다'가 떴다..!
원인
- 입력값이 최악일경우를 잘 고려해서 변수 type을 설정해야한다!
- 정렬되지 않은 데이터에서 투 포인터 알고리즘을 사용하면, 좋은수를 놓치는경우가 많이 발생한다.
- 좋은수 찾기에서, 투 포인터 알고리즘을 사용할 때 주의할점을 놓쳤다!!
정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다!!
해결
-
타입변경
int[] A -> long[] A
int sum -> long sum
int answer -> long answer
int solution() -> long solution() -
투 포인터 알고리즘을 사용하기전에 데이터를 오름차순 정렬한다.
-
좋은수를 찾았을 때, answer++를 하는 조건에
start != A[i] && end != A[i]를 추가했다.
-> Troubleshhtong 3 발생
Troubleshooting 3
public class Main {
public static int solution(long[] A,int N) {
boolean check =true;
int answer = 0;
for(int i =0; i<N; i++) {
int end = N-1;
int start = 0;
while(check) {
long sum = A[start] + A[end];
if( sum > A[i] ) end-- ;
else if( sum < A[i]) start++ ;
else if( sum == A[i] && start != i && end != i) {
answer++;
check = false;
}
if(end == start) check = false;
}
check = true;
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st= new StringTokenizer(br.readLine());
long[] A = new long[N];
for(int i =0; i <N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(A);
System.out.println(solution(A, N));
}
}
문제
시간초과가 났다
원인
만약, sum == A[i]인데, start == i 이거나 end == i이고 end != start이면 그대로 while문을 또 돌게된다.
이때는 end-- 혹은 start++가 되지 않으므로, 위의 조건들이 그대로 유지돼서 무한루프를 돌게된다.
그리고 꼭 start < i < end 이어야한다고 생각을 잘못했다.
해결
i < start일수도 있고, end < i일수도 있다.
따라서 sum == A[i] 일때, start == i 이면 start++를 하고, end == i이면 end-- 를 해서 다시 값을 확인해봐야한다.
제출코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int solution(long[] A,int N) {
int answer = 0;
for(int i =0; i<N; i++) {
int end = N-1;
int start = 0;
while(end>start) {
long sum = A[start] + A[end];
if( sum > A[i] ) end-- ;
else if( sum < A[i]) start++ ;
else if( sum == A[i]) {
if(start != i && end != i) {
answer++;
break;
} else if(start == i) start ++;
else if(end ==i) end--;
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st= new StringTokenizer(br.readLine());
long[] A = new long[N];
for(int i =0; i <N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
br.close();
Arrays.sort(A);
System.out.println(solution(A, N));
}
}공부한 내용
- 투 포인터 알고리즘 : 양쪽에서 하나씩 좁혀오는 것
- 배열 정렬 : Arrays.sort(배열명)
두번째 풀이
Troubleshooting
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int solution(long[] A,int N) {
int answer = 0;
for(int i=0; i<N; i++) {
int start = 0;
int end = N-1;
while(start < end) {
long sum = A[start] + A[end];
if(sum > A[i]) end--;
else if(sum < A[i]) start++;
else if(sum == A[i]) {
if(start != i && end != i) {
answer++;
break;
}else if(start == i) {
start++;
}else if(end == i) {
end--;
}
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
long[] A = new long[N];
bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(A);
System.out.println(solution(A,N));
}
}문제
백준 제출시, 런타임에러가 났다.
원인
System.in이 들어간, BufferedReader를 두 번 생성한게 문제였다.
백준의 경우 실제로 파일로 입력되는데 입력을 여러 번 선언해버리면 이미 버퍼에 쌓인 부분때문에 제대로 읽을 수 없는것이다.
해결
main에서 StringTokenizer st = new StringTokenizer(bf.readLine()); 선언 전에 쓴 두번째 bf를 지웠다.
Troubleshooting 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int solution(long[] A,int N) {
int answer = 0;
for(int i=0; i<N; i++) {
int start = 0;
int end = N-1;
while(start < end) {
long sum = A[start] + A[end];
if(sum > A[i]) end--;
else if(sum < A[i]) start++;
else if(sum == A[i]) {
if(start != i && end != i) {
answer++;
break;
}else {
start++; //start, end 한 번에 움직이기
end--;
}
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
long[] A = new long[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
bf.close();
Arrays.sort(A);
System.out.println(solution(A,N));
}
}문제
틀렸다.
원인
solution 함수에서 두 수의 합과 기준이 동일 할 때, start == i or end ==i 이면 start++, end-- 를 동시에 처리했다.
해결
모든 수가 다른 정렬된 배열이라는 가정하에, 두 수의 합(start + end)이 같았는데 어떤 수가 i여서, start든 end든 하나만 움직이면, 그 수의 합은 무조건 움직이기 전보다 크거나 작아지므로 그 다음 루프에서는 무조건 이전에 움직였던거의 반대편에서 움직임이 일어난다.
따라서 이것을 한번에 둘 다 움직이는것으로 처리했었다.
하지만! 같은수가 있을 수 있다는 가정이 있었다.
그럼 따로 움직이는게 맞으므로, start == i 이면 start++ , end ==i 이면 end--로 로직은 분리했다.
제출코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int solution(long[] A,int N) {
int answer = 0;
for(int i=0; i<N; i++) {
int start = 0;
int end = N-1;
while(start < end) {
long sum = A[start] + A[end];
if(sum > A[i]) end--;
else if(sum < A[i]) start++;
else if(sum == A[i]) {
if(start != i && end != i) {
answer++;
break;
}else if(start == i) {
start++;
}else if(end == i) {
end--;
}
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
long[] A = new long[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
A[i] = Long.parseLong(st.nextToken());
}
bf.close();
Arrays.sort(A);
System.out.println(solution(A,N));
}
}