투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 알고리즘이 매우 간단하므로 바로 실전 문제를 풀어보자.

문제풀이 백준 2018번

<나의 풀이>

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(st.nextToken());
        
        int l=1, r=1;
        int temp = l;
        int ans = 0;
        
        while(true){
            if (temp==n){
                ans ++;
                temp -= l;
                l++;
            } else if(temp<n){
                r++;
                if (r>n){ break; }  
                temp += r;
            } else if(temp>n){
                temp -= l;
                l++;
            }
        }
        
        System.out.println(ans);
    }
}

교재에 나온 코드도 나의 풀이와 비슷하기 때문에 생략.

문제풀이 백준 1940번

<나의 풀이>
수들을 배열에 담은 후 for문을 통해 반복하면서 타겟값-배열 중 하나의 값이 배열안에 있으면 결과값에 하나를 더하는 방식으로 풀이했다. (만약 중복되는 값이 있었다면 다른 방법으로 풀었어야 했을 것이다.)

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.valueOf(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		long m = Integer.valueOf(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		long[] nums = new long[n];
		
		for (int i=0; i<n; i++) {
			nums[i] = Long.valueOf(st.nextToken());
		}
		
		int res = 0;
		for (int i=0; i<n; i++) {
			long temp = m-nums[i];
			if (Arrays.stream(nums).anyMatch(k -> k==temp)) {
				res ++;
			}
		}
		System.out.println(res/2);
	}
}

<교재 풀이>
투 포인터를 사용했다. 이해하는데 크게 어려움이 없으니 설명은 생략.

import java.io.*;
import java.util.*;

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 M = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(A);
		
		int count=0, i=0, j=N-1;
		while(i<j) {
			if (A[i]+A[j]==M) {
				count++;
				i++;
				j--;
			} else if(A[i]+A[j]>M) {j--;} 
			  else if(A[i]+A[j]<M) {i++;}
		}
		
		System.out.println(count);
	}
}

배운 내용

• 배열 정렬
  • 오름 차순: Arrays.sort(arr);
  • 내림 차순: Arrays.sort(arr,Collections.reverseOrder());
  • 일부만 정렬: Arrays.sort(arr, 0, 4); // 0,1,2,3 요소만 정렬
• 리스트 정렬
  • 오름 차순: Collections.sort(arr);
  • 내림 차순: Collections.sort(list, Collections.reverseOrder());
• 배열, 리스트 내에 특정 값이 있는지 확인
  • Arrays.stream(배열).anyMatch(k -> k==특정 값)
  • 리스트.contains(특정 값)

문제풀이 백준 1253번

<나의 풀이>
투 포인터를 이용해서 더했을 때 해당하는 값과 같은지를 비교하면서 문제를 풀었다. 나의 풀이와 교재 풀이가 매우 비슷해서 교재 풀이는 생략한다.

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		long[] nums = new long[n];
	
		for(int i=0; i<n; i++) { nums[i] = Long.parseLong(st.nextToken()); }
		
		Arrays.sort(nums);
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            int l=0, r=n-1;
            
            while(l<r){
                if (l==i){
                    l++;
                    continue; }
                if (r==i){
                    r--;
                    continue; }
                
                if (nums[l]+nums[r] == nums[i]){
                    ans ++;
                    break;
                } else if(nums[l]+nums[r] > nums[i]){ r--; } 
                  else if(nums[l]+nums[r] < nums[i]){ l++; }
            }
        }
        System.out.println(ans);
	}
}

배운 내용

• int 배열을 List로 변환하기

  • Arrays.asList()로 int 배열 변환하기 - 실패

    	
    	import java.util.Arrays;
    	import java.util.List; 
    
    	public class IntArrayConvertToList {    
      	public static void main(String[] args) {                
          
          	// int 배열        
          	int[] arr = { 1, 2, 3 };        
          
          	// Arrays.asList()         
          	List<int[]> intList = Arrays.asList(arr);         
          
          	// 결과 출력        
          	System.out.println(intList.size()); // 1        
          	System.out.println(intList.get(0)); // I@71bb301       
          	System.out.println(Arrays.toString(intList.get(0)));  // [1, 2, 3]     
      }
    }

  • Arrays.asList()에 int 배열을 파라미터로 전달했을 때 나오기 기대했던 결과는 3개의 element를 가지고 있는, List 타입이다. 하지만, 실제로는 1개의 element를 가지고 있는, List<int[]> 타입이 리턴되었다. Arrays.asList() 메소드는, primitive 타입을 Wrapper 클래스로(여기서는 int에서 Integer로) 형변환해주지 않기 때문에 primitive 타입의 배열은 Arrays.asList()로는 List로 변환할 수 없다. => 반복문 혹은 Stream을 사용하자.