2470번(투 포인터), 5568번(조합)

2470번

 

 

투 포인터 알고리즘은 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 형태이다

 

1. 2개의 포인터의 시작점이 배열의 시작점인 경우

> 포인터 2개가 같은 방향으로 진행된다

 

 

2. 2개의 포인터가 각각 배열의 시작점과 끝점에 위치한 경우

> 포인터 2개가 양 끝에서 시작하여 반대로 진행된다

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    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 [] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        // 투포인터 사용
        int start = 0;
        int end = arr.length-1;
        int max = Integer.MAX_VALUE;
        int [] output = new int[2];
        while(start<end) {
            int sum = arr[start] + arr[end];
            // start, end 포인터가 만날 때까지 두 용액의 특성값 합을 구하고 초기화를 반복
            if(max > Math.abs(sum)) { // 합의 절댓값이 기존 합보다 낮은 경우 더 0에 가까운 값
                output[0] = arr[start];
                output[1] = arr[end];
                max = Math.abs(sum);
                if(sum==0) break;
            }
            if(sum<0) start++; // 합을 크게 해줘야 하기 때문에 왼쪽의 포인터가 이동
            else end--; // 합을 줄여줘야 하기 때문에 오른쪽에 위치한 포인터가 이동
        }
        System.out.println(output[0]+" "+output[1]);
    }
}

 

5568번

 

 

조합과 문자열 결합을 통해 만들 수 있는 정수를 모두 set에 넣는다 (중복 제거)

만들 수 있는 정수의 개수를 출력해야 하므로 set의 크기를 구한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {

    static Set <String> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int [] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }
        boolean [] visited = new boolean[n];
        int[] out = new int[k];
        permutation(arr, 0,n,k,visited,out);
        System.out.println(set.size());
    }

    static void permutation(int[] arr, int depth, int n, int k, boolean[] visited, int[] out) {
        if (depth == k) {
            String sum = "";
            for(int i=0; i<out.length; i++) {
                sum += String.valueOf(out[i]);
            }
            set.add(sum);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, depth + 1, n, k, visited, out);
                visited[i] = false;
            }
        }
    }
}