프로그래머스_스트림_day20

오늘은 프로그래머스 Level2로 분류된 문제를 풀이하되, 좀 쉬운 문제 3문제를 풀어보았다. 문제 자체는 크게 어렵지 않았고, 겸사겸사 stream을 연습하는 목적으로 풀이해 보았다. 

Sol 1>

https://school.programmers.co.kr/learn/courses/30/lessons/12939

프로그래머스

 

첫 번째 문제는 단순하게 최댓값과 최솟값을 구해서 리턴하는 문제이다. 
본래라면 Arrays.sort를 사용하거나 배열의 크기를 고려하여 버블 혹은 swap을 사용한 정렬로 구할수도 있는 단순한 문제이다. 스트림을 사용해 풀기 위해 주어진 배열을 공백을 기준으로 분리하여 stream을 생성하고,
mapToInt 메서드로 문자열을 정수형으로 형변환 해준뒤, min & max 메서드로 값을 구해준다. 
이때, 자료형이 stream <integer>이므로 getAsInt()로 리턴값을 맞춰주어야 한다.

import java.util.stream.*;
import java.util.*;
class Solution {
    public String solution(String s) {
        String answer = "";
        
        int min = Arrays.stream(s.split(" "))
            .mapToInt(Integer::parseInt)
            .min().getAsInt();
        
        int max = Arrays.stream(s.split(" "))
            .mapToInt(Integer::parseInt)
            .max().getAsInt();
        
        answer = min + " " + max;
        return answer;
    }
}

 

Sol 2>

https://school.programmers.co.kr/learn/courses/30/lessons/12951

프로그래머스

다음으로 JardenCase 문자열 만들기 문제이다. 
생각보다 단순하게 생각했는데, 공백이 연속될 수 있다는 조건을 놓쳐서 몇몇 테스트케이스를 통과하지 못했다. 
마찬가지로 공백을 기준으로 문자열의 단어를 분리해서 stream을 생성하는데, 단순히 공백으로 분리를 해버리면, 단어의 첫 글자를 대문자로 만들 수는 있지만, 기존 문자열의 공백을 유지할 수가 없다.
그리하여 기존의 공백을 유지할 수 있도록 정규식을 사용해서 문자를 분리해야 한다. 

사용하는 정규식은 다음과 같다. (?<=\\s) | (?=\\s+)
아시다시피 \\s는 공백 문자를 나타내는 데, 두 그룹 중 하나라도 포함되면 정규식이 성립한다. 
(? <=\\s) : 이전 위치가 공백인 경우를 찾는다. 
(?=\\s+) : 다음 위치가 하나 이상의 공백으로 시작하는 경우를 찾는다. 
이렇게 함으로써, 문자열을 양쪽에서 감싸고 있는 공백을 제외하고, 내부적으로 연속된 공백도 유지하며 단어 기준으로 문자열을 분리할 수가 있다.

추가적으로 조건에 따라 숫자부터 시작하는 문자는 그대로 두고, 문자부터 시작하는 단어만 첫 문자를 대문자로 바꾸어야 한다. 이 경우 filter를 사용해서 문자로 시작하는 단어를 찾으면 결과에 숫자가 생략되기 때문에, flatMap을 사용하여 각 스트림 요소를 평탄화하여 작업을 해야 한다. 

마지막으로 작업이 끝난 요소들을 문자열로 다시 반환할 때, joining의 파라미터로 " "을 주게 되면 문자를 분리할 때 기준으로 사용한 공백을 다시 채워 넣어서 본래의 상태를 유지할 수 있다.

import java.util.*;
import java.util.stream.*;
class Solution {
    public String solution(String s) {

         String result = Arrays.stream(s.split("(?<=\\s)|(?=\\s+)"))
                .flatMap(word -> {
                    if (word.matches("\\s+")) {
                        return Arrays.stream(new String[]{word});
                    } else {
                        return Arrays.stream(new String[]{
                                Character.isLetter(word.charAt(0))
                                        ? Character.toUpperCase(word.charAt(0)) + word.substring(1).toLowerCase()
                                        : word.toLowerCase()
                        });
                    }
                })
                .collect(Collectors.joining());

        return result;
    }
}

 

Sol 3>

https://school.programmers.co.kr/learn/courses/30/lessons/12941

프로그래머스

마지막으로 두 배열의 곱의 누적합을 구해 최솟값을 만드는 문제다. 
문제를 푸는 개념 자체는 아주 간단하다. 두 배열의 길이는 동일하기 때문에, 한 배열은 오름차순 나머지 한 배열은 내림차순으로 정렬한 후에 각각의 인덱스 값끼리 교차 곱을 누적하면 그 값이 최소가 된다. 

 

import java.util.*;
import java.util.stream.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        List<Integer> arr1 = Arrays.stream(A)
                .boxed()
                .sorted()
                .collect(Collectors.toList());

        List<Integer> arr2 = Arrays.stream(B)
                .boxed()
                .sorted(Comparator.reverseOrder())
                .collect(Collectors.toList());

        int sum = IntStream.range(0, arr1.size())
                .map(index -> arr1.get(index) * arr2.get(index)) // 
                .sum(); // 곱한 값들의 누적합

        return sum;
    }
}

위처럼 단순한 방식으로 코드를 구현할 수 있다. 하지만 채점을 제출해 보면, 정확성 테스트는 모두 맞지만, 효율성 테스트에서 모두 시간 초과가 나는 것을 알 수 있다. 
그렇다면 이 시점에서 정렬하는 방식을 새롭게 생각해봐야 한다. 

Arrays.sort는 기본적으로 dual-pivot-Quicksort 알고리즘을 사용하며, 원시 데이터 타입에 대한 정렬에 최적화가 되어 있다. 

stream을 사용하면 원시 <-> 래퍼 클래스로의 박싱 & 언박싱이 일어나기 때문에, 기본적으로 Arrays.sort보다 느리다. 

그래서 stream 대신에 Arrays.sort를 구현해보려고 생각해 봤지만, 중첩 반복문을 사용해서 정렬을 하는 것은 더 느려질 것이고, 내림차순 정렬을 위해 Comparator를 사용하기 위해서는 원시데이터가 아닌 wrapping 클래스만 가능하기 때문에 똑같을 것이다. 

그리하여 마지막으로 생각해볼 수 있는 것은 heap 자료구조를 사용하는 우선순위큐를 이용하는 것이다. 
O(logN)의 시간 복잡도로 예상과 마찬가지로 빠른 속도로 효율성 테스트를 통과할 수 있었다. 

import java.util.*;
import java.util.stream.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        PriorityQueue<Integer> a = new PriorityQueue<>();
        PriorityQueue<Integer> b = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i=0; i<array1.length; i++){
            a.add(array1[i]);
            b.add(array2[i]);
        }
        int sum = 0;
        while (!a.isEmpty()) {
            sum += a.remove() * b.remove();
        }
        return sum;
    }
}

헌데 하나의 의문점은 우선순위큐에서 요소의 곱을 구하기 위해 하나씩 값을 꺼낼 때, poll은 시간초과가 나는데, remove는 통과가 되는 점이다;; 
기본 실행 로직 자체는 poll은 큐의 가장 앞부분에 있는 값을 꺼내오기 때문에 O(1)이고, remove(Object o)는 객체 o를 찾아서 지우기 위해 한 번의 선형 탐색을 진행해서 O(N)의 시간복잡도를 소요한다. remove에서 삭제할 객체 o를 지정하지 않다고 하더라도 poll이 훨씬 빠른 게 분명한데,,, 무엇의 차이인지는 아시는 분 알려주세요..