HackerRank-Permuting Two Arrays

[문제 설명]

출처:https://www.hackerrank.com/challenges/two-arrays/problem?isFullScreen=true

[문제 이해하기]
영어 문장을 이해하면
첫번째 줄에 q 라는 질문 갯수가 주어진다.
질문 중 첫번째 줄에는 n,k를 각각 입력받는다.
n은 배열의 크기, k는 합을 나타내는 조건

각 A배열과 B배열을 순회하며 k이상인 조합을 찾는 문제

처음 문제를 읽고 2중 FOR문이 생각이 났다. 하지만 문제에서는 배열 크기가 10^9이므로 시간초과가 발생할것임을 알수 있었다.

다른 방법으로 TWO POINT가 생각이 났다.
먼저 A={}배열을 오름차순으로 정렬하고,B={}배열을 내림차순으로 정렬하였다.

이러한 형태로 정렬한다.

그리고 로직을 수행한다.

먼저 start와 end 지점에서 포인터가 출발한다.
처음 start + end 값은 k를 넘지 못한다. 그러므로 start만 증가한다.

그림처럼 포인터가 변경된다.
만약 start + end >= k 이상이면 start,end는 같이 증가한다.

아래 그림순으로 이동하다 start가 n-1지점을 만나면 종료되었을때
k를 넘는 갯수가 A.size()이상이면 "YES" 아니면 "NO"를 출력

[전체 소스코드]

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {
    static String answer ="";
    static StringBuilder sb = new StringBuilder();
    static int cnt = 0;
     
    /*
     * Complete the 'twoArrays' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY A
     *  3. INTEGER_ARRAY B
     */

    public static String twoArrays(int k, List<Integer> A, List<Integer> B) {
    
     // Write your code here
        Collections.sort(A);
        Collections.sort(B,new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                
                return o2 - o1;
            }
            
        });
        
        
        int n = B.size();
        int start = 0;
        int end = 0;
        while(start <= n-1) {
            if(A.get(start) + B.get(end) >= k) {
                cnt++;
                start++;
                end++;
            }else {
                start++;
            }
        }
        
        
        if(cnt >= A.size()){
            sb.append("YES");
        }else{
            sb.append("NO");
        }
        answer = String.valueOf(sb);
        sb.setLength(0); 
        cnt = 0;
        return answer;
    }


}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int n = Integer.parseInt(firstMultipleInput[0]);

                int k = Integer.parseInt(firstMultipleInput[1]);

                List<Integer> A = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                List<Integer> B = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                String result = Result.twoArrays(k, A, B);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}