[백준] 1253 : 좋다 - JAVA

Benjamin·2022년 11월 16일
0

BAEKJOON

목록 보기
12/70

🙋정렬 + 투 포인터 알고리즘 사용

슈도코드

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));
	}
}

문제

당연히 맞은줄알고 제출했는데, 너무나 빨간글씨로 '틀렸습니다'가 떴다..!

원인

  1. 입력값이 최악일경우를 잘 고려해서 변수 type을 설정해야한다!
  2. 정렬되지 않은 데이터에서 투 포인터 알고리즘을 사용하면, 좋은수를 놓치는경우가 많이 발생한다.
  3. 좋은수 찾기에서, 투 포인터 알고리즘을 사용할 때 주의할점을 놓쳤다!!
    정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다!!

해결

  1. 타입변경
    int[] A -> long[] A
    int sum -> long sum
    int answer -> long answer
    int solution() -> long solution()

  2. 투 포인터 알고리즘을 사용하기전에 데이터를 오름차순 정렬한다.

  3. 좋은수를 찾았을 때, 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));
	}
}

0개의 댓글