개발자 Lim

단계적으로 풀기 좋은 dfs, bfs 문제가 있어 같이 포스팅 하게 되었다.

<의역>: mxn 만큼의 '1'(땅) '0'(물)로 이루어진 이차원 char 배열이 있을 때  1이 존재하는 공간(땅)의 갯수를 반환 하라.

단 연속적으로 이어진 공간은 한 개의 땅으로 인정한다.  

<접근법>

이차원 배열을 순차적으로 탐색하여 '1'인 곳을 반견하면 땅의 갯수+1

그리고 해당 지점을 기준으로 dfs로 탐색하여 '1'인 곳은 방문 했다는 표시를 하고

각 방향에서 '0'이 나오거나 배열의 범위의 맨 끝에 도달하면 return 

<코드>

class Solution {
    public void dfs(char[][] grid,int i, int j){
        if(i<0||i>= grid.length||j<0||j>=grid[0].length)
            return;
        if(grid[i][j]=='0')
            return;
        grid[i][j]='0';
        
        dfs(grid, i+1, j); dfs(grid, i-1, j);
        dfs(grid, i, j+1); dfs(grid, i, j-1);
    }
    public int numIslands(char[][] grid) {
        int count=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]=='1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
}

<의역>: 위에 문제에서 한 가지 조건이 추가 단순히 땅의 갯수를 반환 하는 것이 아니라

상하좌우가 전부 물로 둘러 싸인 섬의 갯수를 반환 

<접근법>

해당 문제의 값이 땅은 0이고 물은 1임을 이용하여 

이차원배열을 순차적으로 탐색할 때 해당 값이 0이면 그 점을 기준으로 dfs 하여

벽이라면 0, 그렇지 않으면 1을 반환하도록 하고 방문한 땅을 표시

그 후 상하좌우 4방향에 탐색한 결과값을 곱하여 반환

(만약 주변에 벽이 있다면 0, 물로만 둘러 싸여 있다면 1이 반환될 것)

<코드>

class Solution {
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n*m)
    public int dfs(int[][] grid,int i,int j){
        if(i<0||i>=grid.length||j<0||j>= grid[0].length)
            return 0;
        if(grid[i][j]>0)
            return 1;
        grid[i][j] = 2;

        return dfs(grid, i+1, j)*dfs(grid, i-1, j)*dfs(grid, i, j+1)*dfs(grid, i, j-1);
    }
    public int closedIsland(int[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==0)
                    count+=dfs(grid,i,j);
            }
        }
        return count;
    }
}

<의역>: 바로 위에 있던 1254번 문제에서 섬의 갯수를 반환 했다면 이제는 섬을 구성하는 cell의 갯수를 반환 할 것 

<접근법>

마찬가지로 이차원 배열을 순차적으로 탐색하되 해당 값이 1 이라면 해당 값을 기준으로 dfs 탐색 

해당 공간이 땅이라면 1을 반환하고 그렇지 않으면 0을 반환 만약 배열의 범위 끝에 맞닿는 다면 벗어 놨다면 따로 변수를 통해 섬이 아님을 표시 + 각각 방문한 땅을 표시 

종합적으로 해당 영역이 섬이 아닐 경우

해당 cell에서 상하좌우의 땅의 수를 모두 더해 반환

<코드>

class Solution{
    private boolean isIsland = true;
    public int dfs(int [][] grid,int i,int j){
        int count = 0;
        if(i<0||i>= grid.length||j<0||j>=grid[0].length) {
            isIsland = false;
            return 0;
        }
        if(grid[i][j]<1)
            return 0;

        if(grid[i][j]==1) {
            grid[i][j]=-1;
            count=1;
        }

        int[][] fourWay = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] way:fourWay) {
            count += dfs(grid,i+way[0],j+way[1]);
        }

        return count;
    }
    public int numEnclaves(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]==1) {
                    int tmp = dfs(grid, i, j);
                    if(isIsland)
                        ans+=tmp;
                    isIsland = true;
                }
            }
        }
        return ans;
    }
}

의역: 오름차순으로 정렬되어 있는 정수 배열 arr와 정수 k가 주어질 때 자연수 1부터 해당 배열의 요소들을 제외하고 카운트 할때 k번째로 오는 수를 구하라.  

풀이:

1. 자료구조 Set 사용

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int findKthPositive(int[] arr, int k) {
        HashSet<Integer> map = new HashSet<Integer>();
        int count = 0; int checker = 0;
        for (int unit:arr)
            map.add(unit);
        while(checker!=k)
            if(!map.contains(++count))
                checker++;

        return count;
    }
}

2. OnePass 알고리즘 

class Solution {
    // 시간 복잡도 O(n)
    public int findKthPositive2(int[] arr, int k) {
        for (int i : arr) {
            if (i <= k) k++;
            else break;
        }
        return k;
    }
}

3. 이진 탐색 활용

class Solution {
    // 시간 복잡도 O(log n) 공간복잡도 O(1)
    // 배열 범위 내부에서 k보다 작은 것이 있다면 카운트++ 그러나 카운트가 증가하면서 새롭게
    // 배열 범위 내부에서 작은 값이 생긴다면 카운트++
    public int findKthPositiveOtimal(int []arr, int k){
        int start = 0; int end = arr.length;
        // 해당 이진 탐색으로 찾는 것 -> 1부터 카운트 하며 k까지 증가 할때 해당 값이 k보다 작아 지는
        // 수 들의 갯수
        while(start<end){
            int mid = (start+end)/2;
            // 해당 식을 통해 arr[mid]의 값이 최종적으로 카운트 했을 때의 값보다 작아짐을 확인 가능
            if(arr[mid]-mid-1<k)
                start = mid+1;
            else
                end = mid;
        }
        return k+start;
    }
}

조건:

• 0 <= low <= high <= 10^9

의역: 두 정수를 포함한 사이의 홀 수의 개수를 반환하라.

풀이:

1. 단순 반복 (Time out)

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int countOddsFail(int low, int high) {
        int ans=0;
        for(int i=low;i<=high;i++){
            if(i%2==1) ans++;
        }
        return ans;
    }
}

2. 수학의 경우의 수 

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOdds(int low, int high) {
        if(low==high) return low%2==1?1:0;
        int ans = 0;

        if(low%2==0&&high%2==0){
            ans = (high-low)/2;
        }
        else if(low%2==1&&high%2==1){
            ans = (high-low)/2+1;
        }
        else{
            ans = (high-low-1)/2+1;
        }

        return ans;
    }
}

2-1 좀 더 최적화

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOddsOtimal(int low, int high){
        // low가 짝수라면 홀수로 바꾸기
        // 어차피 짝수는 no Count 이기 때문에 정답에는 영향을 미치지 않음
        if((low&1)==0){
            low++;
        }

        // 만약 low와 hight둘다 짝수였다면 0이 나오고 그것이 아니라면
        // 둘다 홀수 임으로 두 수 사이의 범위/2 +1 법칙이 성립
        return low>high?0:(high-low)/2+1;
    }
}

<메모>

최대한 나올 수 있는 경우의 수를 공통의 경우로 만들어 줄이자. 

조건:

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• All the values in score are unique.

의역: 각 고유한 값을 가진 정수형 배열이 들어올 때 해당 배열의 인덱스에 맞추어서 1등이면 Gold Medal 2등이면 Silver Medal 3등이면 Bronze Medal 그 외라면 각 순위를 문자열로 담은 문자열 배열을 반환하라.

풀이:

1. 단순 반복

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n)
    public String[] findRelativeRanks(int[] score) {
        String price[] = {"Gold Medal","Silver Medal","Bronze Medal"};
        int indexHighArray[] = new int[score.length];
        String ans[] = new String[score.length];

        for (int i=0;i<score.length;i++){
            int tmp = -1; int index=0;
            for(int j=0;j< score.length;j++){
                if(tmp<score[j]){
                    tmp = score[j];
                    index = j;
                }
            }
            score[index] = -1;
            indexHighArray[i] = index;
        }
        // 만들어 진 것 크기가 큰 수 부터 내림 차순의 인덱스 배열
        for(int i=0;i<score.length;i++){
            if(i<3)
                ans[indexHighArray[i]]=price[i];
            else
                ans[indexHighArray[i]]=(i+1)+"";
        }
        return ans;
    }
}

예상외로 모든 풀이 중 가장 사용 메모리가 적었다.

2. TreeSet, Map 자료구조 활용

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks1(int[] score) {
        String price[] = {"mask","Gold Medal","Silver Medal","Bronze Medal"};
        String ans[] = new String[score.length];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        TreeSet<Integer> tset = new TreeSet<Integer>();
        // TreeSet을 활용하여 자동 정렬
        for (int num:score)
            tset.add(num);

        Iterator<Integer> it = tset.iterator();
        // map에 key를 배열의 값 value를 배열에서의 값의 순위 정보 저장
        int order = score.length;
        while(it.hasNext()){
            int key = it.next();
            map.put(key,order--);
        }
        // Map에 저장된 순위 정보를 불러와 ans 배열 생성
        for(int i=0;i<score.length;i++){
            int value = map.get(score[i]);
            if(value<=3)
                ans[i]=price[value];
            else
                ans[i]=(value)+"";
        }
        return ans;
    }
}

확실히 시간 복잡도를 O(n^2)을 O(n)으로 줄이니 속도가 개선된 모습 

+ 아래 함수들을 TreeMap 대신 사용하면 더 빠르게 개선이 가능

int[] copy = score.clone();
Arrays.sort(copy);

3. 기수 정렬 이용 Map을 긴 배열로 대체 

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks2(int[] score){
        int peapleNum = score.length;
        String[] ans = new String[peapleNum];
        int max = 0;
        for (int num: score)
            max = max<=num? num:max;
        int scoreArray[] = new int[max+1];

        // 가장 큰 수+1 만큼의 길이의 배열을 만들고 각 해당하는 수의 인덱스에 순위정보 저장
        for(int i=0;i<score.length;i++)
            scoreArray[score[i]] = i+1;

        int rank = 1;
        for(int i=scoreArray.length-1;i>=0;i--){
            if(rank> peapleNum) break;
            // scoreArray 배열에서 score 배열에 있는 수 만을 활용 하게끔 하는 조건
            // 자바에서 정수형 배열은 생성 후 따로 값을 초기화 하지 않으면 자동으로 0
            if(scoreArray[i]>0){
                switch (rank){
                    case 1:ans[scoreArray[i] - 1] = "Gold Medal";rank++; break;
                    case 2:ans[scoreArray[i] - 1] = "Silver Medal";rank++; break;
                    case 3:ans[scoreArray[i] - 1] = "Bronze Medal";rank++; break;
                    default: ans[scoreArray[i]-1] = rank+""; rank++; break;
                }
            }
        }
        return ans;
    }
}

메모: 가급적 만들 수 있는 자료구조를 사용하지 않고 해결이 가능하다면 사용하지 말고 풀이 해볼 것

의역: 정수를 7진법으로 바꾼 문자열을 반환해라

(주의점: 실제 진법에서 음수는 보수로 처리하는데 해당 문제에서는 단순히 앞에 - 붙인 걸로 음수를 처리 함) 

풀이:

재귀 함수 사용

(기억해야 할 내용 재귀는 스택과 같이 제일 먼저 호출한 내용을 제일 마지막으로 처리한다.) 

즉 7^0 부터 나누는 것을 처음으로 호출하고 7^i 까지 나누는 걸 호출 한다면

7^i 부터 처리하고 7^0을 마지막으로 처리한다. 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    private StringBuilder ans = new StringBuilder();
    private int recusiveNum;
    private void helper(int i){
        int divisor = (int)Math.pow(7,i);
        if(recusiveNum<divisor)
            return;
        helper(i+1);
        int highDigit = recusiveNum/divisor;
        recusiveNum %= Math.pow(7,i);
        ans.append(highDigit);
    }
    public String convertToBase7(int num) {
        if(num==0) return "0";
        recusiveNum = Math.abs(num);
        helper(0);
        if(num<0)
            ans.insert(0,"-");
        return ans.toString();
    }
}

최적화 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    public String convertToBase7Otimal(int num){
        if(num<0)
            return "-"+convertToBase7Otimal(-num);
        if(num<7)
            return num+"";
        return convertToBase7Otimal(num/7)+num%7;
    }
}

메모: 재귀는 쉽게 생각하고 간결하게 짜야 한다.

의역: (BST) 자식이 부모와 같은 값을 가질 수 있는 조건이 추가된 이진트리가 주어질 때 해당 트리에서 가장 많이 나온 노드값 들의 배열을 반환하시오  

의역: 첫 번째 예시에서는 2가 가장 많은 노드 값이었기 때문에 2를 반환

두 번째 예시에서는 0이 가장 많은 노드 값이기 때문에 0을 반환

풀이:

1. 전위순회(dfs) + Map

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    // 가장 빈도가 높게 나온 횟 수
    private int maxValue=1;
    private HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    // 전위순회 알고리즘 (DFS)
    public void helper(TreeNode2 root){
    	// HashMap의 contains() 함수를 사용해도 되지만 더 효율적으로 바꾼 것
        if(root!=null){
            Integer value = map.get(root.val);

            if(value!=null){
            	// 최대 빈도 갱신
                if(value+1>maxValue)
                    maxValue = value+1;
                map.put(root.val,value+1);}

            else map.put(root.val,1);
            helper(root.right);
            helper(root.left);
        }
    }
    public int[] findMode(TreeNode2 root) {
        List<Integer> ans = new ArrayList<Integer>();
        helper(root);

        Set<Integer> set = map.keySet();
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            int key = it.next();
            int value = map.get(key);
            // 가장 빈도가 높은 횟수랑 같다면 추가
            if(value==maxValue)
                ans.add(key);
        }
        return  ans.stream()
                .mapToInt(i -> i)
                .toArray();

    }
}

1-1 map을 사용하지 않고 BST의 성질을 이용해 개선 시킨 코드

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    ArrayList<Integer> ans;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        ans = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        helper(root);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);

        int rootValue = root.val;
        // 루트 노드인 경우와 값이 달라진 경우
        if (pre == null || rootValue != pre.val) {
            count = 1;
        } else {
            count++;
        }
        // maxCount 최대 빈도 수와 비교 해서 크다면 ArrayList 최신화
        if (count > maxCount) {
            ans.clear();
            ans.add(rootValue);
            maxCount = count;
        } else if (count == maxCount) {
            ans.add(rootValue);
        }
        pre = root;

        helper(root.right);
    }
}

메모: BST 중복값을 허용하는 이진 트리

링크: https://leetcode.com/problems/find-mode-in-binary-search-tree/description/

조건:

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words의 각 원소는 대문자와 소문자의 혼용으로 이루어져 있습니다.

의역: 문자열들의 배열 words가 주어질 때 해당 문자열에서 미국식 키보드 기분 한 행의 키만 사용해서 만든 문자열들을 배열로 만들어 반환해라. 

미국식 키보드:

• 첫 번째 행: "qwertyuiop",
• 두 번째 행: "asdfghjkl", 
• 세 번째 행: "zxcvbnm".

의역: 첫 번째 예시에서는 Alaska와 Dad 만이 2번째 행의 문자들로 구성되어 있기에 저 둘이 반환되었으며

두 번째 예시에서 omk는 첫 번째 두 번째 세 번째 모든 행의 문자들로 구성되어 있기에 빈 공간을 반환합니다.

세 번쨰 예시에서는 words의 원소 모두 2번째 행의 문자들로 구성되어 있기에 words 그대로를 반환합니다.

풀이: 

1. 정규식 이용

class Solution {
    // 시간 복잡도O(n*String.matches()) 공간복잡도 O(1)
    public String[] findWords(String[] words) {
        List<String> ans = new ArrayList<String>();
        // [a|b]* 는 a 또는 b가 0번 이상 반복되어 구성된 문자열임을 의미한다.
        for(int i=0;i<words.length;i++){
            if(words[i].matches("[q|Q|w|W|e|E|r|R|t|T|y|Y|u|U|i|I|o|O|p|P|]*")
            ||words[i].matches("[a|A|s|S|d|D|f|F|g|G|h|H|j|J|k|K|l|L]*")
            ||words[i].matches("[z|Z|x|X|c|C|v|V|b|B|n|N|m|M]*"))
                ans.add(words[i]);
        }
        return ans.toArray(new String[ans.size()]);
    }

}

1-1. (한 줄로 줄인 코드)

toLowerCase()를 통해 대소문자 구별을 없애고  | 조건을 추가하여 한 줄로 정리된 모습 

Stream.of(array): 지정된 array를 바탕으로 Stream 객체를 만듭니다.

Stream.filter(람다식): 람다식의 조건을 바탕으로 Stream 객체의 정보를 정리합니다.

String.mathch(정규식): 해당 정규식과 동일한 문자열이면 true 아니면 false를 리턴 합니다.

Stream.toArray(Type[]::new)는 Stream을 Type의 배열로 변환합니다.

public String[] findWords(String[] words) {
    return Stream.of(words).filter(s -> s.toLowerCase().matches("[qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*")).toArray(String[]::new);
}

2. Set 자료구조 활용 (브루트 포스)

class Solution {
        public String[] findWords(String[] words){
        ArrayList<String>list=new ArrayList<>();

        // mask로 사용할 set 초기화
        String p="qwertyuiop";
        HashSet<Character>a=new HashSet<>();
        for(int i=0;i<p.length();i++){
            a.add(p.charAt(i));
        }
        String q="asdfghjkl";
        HashSet<Character>b=new HashSet<>();
        for(int i=0;i<q.length();i++){
            b.add(q.charAt(i));
        }
        String r="zxcvbnm";
        HashSet<Character>c=new HashSet<>();
        for(int i=0;i<r.length();i++){
            c.add(r.charAt(i));
        }
        
        int j=0;
        for(int i=0;i<words.length;i++){
            String words2=words[i].toLowerCase();
            if(a.contains(words2.charAt(0))){
                for(j=1;j<words2.length();j++){
                    if(!a.contains(words2.charAt(j))){
                        break;
                    }
                }
                if(j==words[i].length()){
                    list.add(words[i]);
                }
            }
            else  if(b.contains(words2.charAt(0))){
                for(j=1;j<words2.length();j++){
                    if(!b.contains(words2.charAt(j))){
                        break;
                    }
                }
                if(j==words2.length()){
                    list.add(words[i]);
                }
            }
            else if(c.contains(words2.charAt(0))){
                for( j=1;j<words2.length();j++){
                    if(!c.contains(words2.charAt(j))){
                        break;
                    }
                }
                if(j==words2.length()){
                    list.add(words[i]);
                }
            }
        }
        return list.toArray(new String[list.size()]);
    }
}

메모: 더 간결하게 줄인다고 해당 코드가 무조건 효율적이지는 않다.

링크: https://leetcode.com/problems/keyboard-row/

조건:

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique. (배열 안의 정수 값은 중복이 존재하지 않는다)
• All the integers of nums1 also appear in nums2.

권장 사항: Could you find an O(nums1.length + nums2.length) solution? 

의역: 두 개의 정수 배열 nums2[]와 nums2[]의 부분집합 nums1[]이 주어질 때

ex: nums2 = {1,2,3,4,5,6}, nums1 = {1,5}

정수형 배열 ans[]를 반환하라 (nums1.length == ans.length)

ans[]의 각 인덱스값은 nums1[]의 각 인덱스 값과 매칭되어 ans[i] = function(nums[i]);

nums1의 각 인덱스의 해당하는 값을 nums2에서 찾고 그 뒤로 해당 값보다 큰 값이 나오면 그 값을 ans에 집어 넣는다.

만약 nums2에 뒤에 더 큰 값이 나오지 않는다면 -1을 넣는다.

의역: nums1[0]의 값은 nums2[2]의 값과 매칭되며 nums2 배열에서 다음 인덱스 안에 4보다 큰 값이 없으므로 ans[0] = -1

nums[1]의 값은 nums2[0]의 값과 매칭되며 nums2 배열에서 다음 인덱스 값이 1보다 큰 3이므로 ans[1] = 3

nums[2]의 값은 nums2[3]의 값과 매칭되며 nums2 배열에서 3 다음 인덱스가 존재 하지 않으므로 ans[2] = -1

의역: nums1[0]의 값은 nums2[1]의 값과 매칭되며 nums2 배열에서 다음 인덱스 값이 2보다 큰 3이므로 ans[0] = 3

nums[1]의 값은 nums2[3]의 값과 매칭되며 nums2 배열에서 3 다음 인덱스가 존재 하지 않으므로 ans[1] = -1

풀이: 

1. 정공법 브루트 포스

class Solution {
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n)
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int ans[] = new int[nums1.length];
        Arrays.fill(ans,-1);
        for(int i=0;i< nums1.length;i++){
            int pos = -1;
            for(int j=0;j< nums2.length;j++){
                if(nums1[i]==nums2[j])
                    pos = j;
                if(pos!=-1&&nums2[pos]<nums2[j]){
                    ans[i] = nums2[j];
                    break;
                }
            }
        }
        return ans;
    }
}

2. 기수 정렬 응용 (정수형의 범위 만큼의 저장공간 생성 후 활용)

class Solution {
    // 시간 복잡도 O(n+m) 공간 복잡도 O(n)
    // 가능한 이유 nums1[i], nums2[i] 값의 범위가 좁기 때문에
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 0 <= nums1[i], nums2[i] <= 10^4
        int numsNextBigger[] = new int[10001];
        Arrays.fill(numsNextBigger,-1);
        int ans[] = new int[nums1.length];
        // numsBigerNext에 nums2의 모든 값에 대한 다음 큰 값의 정보를 담는다.
        for(int i=0;i<nums2.length;i++){
            for(int j=i;j<nums2.length;j++){
                if(nums2[i]<nums2[j]){
                    numsNextBigger[nums2[i]] = nums2[j];
                    break;
                }
            }
        }
        // 반복문을 통한 저장된 자료값 매핑
        for(int i=0;i<nums1.length;i++){
            ans[i] = numsNextBigger[nums1[i]];
        }
        return ans;
    }
}

3. monotone stack기법 변형

(스택의 원소들을 오름차순, 혹은 내림차순 상태를 유지하도록 하는 것)

스택에 숫자 x를 넣는다고 할 때 x를 넣기 전에 x 이상의 수를 모두 제거하고 x를 넣는 것.

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int ans[] = new int[nums1.length];
        Stack<Integer> stack = new Stack<Integer>();
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        // nums2의 모든 값들의 nextGreaterElement 정보를 map에 저장
        for(int i=0;i<nums2.length;i++){
            int tmp = nums2[i];
            // stack에 순서대로 값을 push 하다가 다음 값이 전에 push 한 값보다 크다면
            while(!stack.isEmpty()&&tmp>stack.peek()) {
                // 전에 넣어둔 값을 제거 하고 전에 넣어둔 값의 nextGreaterElement로 map에 저장
                map.put(stack.pop(), tmp);
                // while문으로 반복하게 되어 차례대로 과정 수행
            }
            stack.push(tmp);
        }

        int i=0;
        for (int num:nums1) {
        // getOrDefault() 함수는 찾는 key 값이 없다면 정해둔 (-1)값을 반환  
            ans[i++] = map.getOrDefault(num,-1);
        }
        return ans;
    }
}

메모: 컬렉션의 빌트인 함수들을 사용하여 빅오 표시법의 시간복잡도를 줄여도 해당 빌트인 함수들의 소요 시간으로 인해 분명히 단순 빅오 표기법 상으로는 3번 풀이가 더 효율적이나 예상외로 2번이 더 효율적이었다.

되도록이면 빌트인 함수들을 사용하는 걸 줄이자.