ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1253 좋다
    백준/두 포인터 2022. 4. 18. 20:57

    다른 사람 블로그를 참고해서 풀었다.

     

    두 포인터를 활용하였다.

     

    1) 풀이 예시

     

    5 =N

    1 2 3 5 8 => number 배열에 오름차순 정렬하여 입력.

     

    를 생각해보자.

     

    2) 3이 좋다 조건을 만족할까?

     

     

    먼저 3이 좋다 조건을 만족하는지 생각해보자.

    일단 두 포인터로 변수 one, two 를 사용한다.

     

    처음에

    one = 0, two = N-1 = 4

    => number[one] = 1, number[two] = 8

    => sum = number[one] + number[two] = 9

     

    3을 변수 value 에 입력한다.

    => value = 3

     

    value (3) < sum(9) 이므로,

    sum 값을 줄여야 value 에 가까워진다.

     

    number 배열을 오름차순 정렬했기 때문에, sum 을 줄이려면 two 인덱스를 감소시켜야 한다.

    => two--

     

    그러면

    one = 0, two = 3

    => number[0] = 1, number[two] = 5

    => sum = 6

    value = 3

     

    value < sum 이므로 역시 two 인덱스를 줄여나가면서 value = sum 을 만족할 때까지 하면 된다.

     

     

    3) 5가 좋다 조건을 만족할까?

    위의 예시를 이어서 풀이한다.

     

    1 2 3 5 8

     

    이 경우도 시작은 one = 0, two = 4

    sum = number[one] + number[two] =  9

    value = 5

     

    value < sum 이므로 two 인덱스를 줄인다.

    one = 0, two = 3

    그런데, 좋다 조건을 만족하려면 자기 자신이 아닌 다른 두개의 합을 구해야 한다.

    그런데 숫자 5의 인덱스는 3으로 two 와 같다.

    그래서 이 경우는 two를 한 번 더 감소시킨다.

     

    one = 0, two = 2

    sum = number[one] + number[two] =  4

     

    value > sum 이므로, sum 을 증가시켜야 value 에 가까워질 수 있다.

    그래서 이번에는 one 인덱스를 증가시킨다.

    one = 1, two = 2

    sum = number[one] + number[two] =  5

    sum = value 이므로 숫자 5는 좋다 조건을 만족한다.

     

    4) 최종 코드

     

    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 void main(String[] args) throws IOException {
    	
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int N = Integer.parseInt(br.readLine());
    	int number []= new int [N];
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
    	
    	for(int i=0; i<N; i++) {
    		number[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	Arrays.sort(number);
    	
    	int count = 0;
    	
    	for(int i=0; i<N; i++) {
    		
    		int one = 0;
    		int two = N-1;
    		
    		while(one<two) {
    		
    			if(one==i) {
    				one++;
    				continue;
    			}
    			
    			if(two==i) {
    				two--;
    				continue;
    			}
    			
    			int sum = number[one]+ number[two];
    			int value = number[i];
    			
    			if(value == sum) {
    				count++;
    				break;
    			}
    		
    		
    			if(value<sum ) {
    				two--;
    			}else if(value>sum) {
    				one++;
    			}
    		}
    	}
    	
    	
    	System.out.println(count);
    	
    	}
    }

     

    참고 블로그 : https://coder-in-war.tistory.com/entry/BOJ-JAVA1253-%EC%A2%8B%EB%8B%A4

     

    [ BOJ ][JAVA][1253] 좋다

    https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net..

    coder-in-war.tistory.com

     

    '백준 > 두 포인터' 카테고리의 다른 글

    1806 부분합  (0) 2024.08.02
    3151 합이 0  (0) 2024.08.02
    1484 다이어트  (0) 2022.06.11
    2461 대표 선수  (0) 2022.05.15

    댓글

Designed by Tistory.