프로그래머스 > 최고의 입찰가

package lmhs.comm.base.test;

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;

public class StackTest {
    public static void main(String[] args) {
        int n= 3; //참가자 
        int[][] record = {{1,100},{2,150},{3,300},{1,200},{2,250},{3,350},{2,-1},{3,-1},{3,190}};
        int[][] record2 = {{4,120},{3,200},{4,220},{4,150},{4,250},{2,150},{4,-1},
                {4,-1},{2,200},{4,300},{4,200},{2,150},{4,-1},{2,-1},{4,100},{4,-1},{3,-1},{2,-1},{4,-1},{4,-1}};
        int[] result  = solution(n, record);
        for(int i:result) {
            System.out.println(i);
        }
    }
    
    static int[] solution(int n, int[][]record){
        int[] result = new int[n];
        
        //참가자별 입찰가를 stack 에 담는다.
        Map<Integer,Stack<Integer>>map = new HashMap();
        for(int i=0;i<record.length;i++){
            Stack<Integer> stack = map.getOrDefault(record[i][0], new Stack<Integer>());
            
            if(record[i][1]==-1 ) {
                stack.pop();
            } else {
                stack.add(record[i][1]);
            }
            map.put(record[i][0], stack);
        }

        //최종 입찰가로 map 을 재구성
        Map<Integer,Integer> r = new HashMap();
        for(Entry<Integer, Stack<Integer>> s : map.entrySet()) {
            if(s.getValue().size()>0) {
                Stack<Integer> st = s.getValue();
                r.put(s.getKey(), st.peek());
            } else {
                r.put(s.getKey(), 0);
            }
        }
        
        //미참가 번호 있는 경우 
        if(r.size()!=n) {
            int[] mems = new int[n]; 
            for(int i=0;i<n;i++) {
                mems[i]=i+1;
            }
            //map 에 key 로 존재하지 않는 미참가 번호를 채운다 .
            Set<Integer> keyset = map.keySet();
            for(int i=0;i<mems.length;i++) {
                int m = i+1;
                if(!keyset.contains(m)) {
                    r.put(m,0);
                }
            }
        }

        //입찰가 기준(map.value) 으로 정렬 
        List<Entry<Integer, Integer>> list = r.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).collect(Collectors.toList());
        
        //참가자 (map.key)만 반환
        int idx=0;
        for(Entry<Integer, Integer> e: list) {
            result[idx] =e.getKey();
            idx+=1;
        }
        
        return result;
    }
}

효율적인 정렬 방법 찾기 
map 보다는 배열 사용 권고 >불필요한 메모리 사용 

package lmhs.comm.base.test;

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;

public class StackTest {
    public static void main(String[] args) {
        int n= 4; //참가자 
        int[][] record = {{1,100},{2,150},{3,300},{1,200},{2,250},{3,350},{2,-1},{3,-1},{3,190}};
        int[][] record2 = {{4,120},{3,200},{4,220},{4,150},{4,250},{2,150},{4,-1},
                {4,-1},{2,200},{4,300},{4,200},{2,150},{4,-1},{2,-1},{4,100},{4,-1},{3,-1},{2,-1},{4,-1},{4,-1}};
        int[] result  = solution(n, record2);
        for(int i:result) {
            System.out.println(i);
        }
    }
    
    static int[] solution(int n, int[][]record){
        int[] result = new int[n];
        
        Stack<Integer> entry[] = new Stack[n];
        
        for(int i = 0; i < n; i++){
            entry[i] = new Stack<Integer>();
        }
        
        
        //참가자별 입찰가를 stack 에 담는다.
        Map<Integer,Stack<Integer>>map = new HashMap();
        for(int i=0;i<record.length;i++){           
            if(record[i][1]==-1 ) {
                entry[record[i][0]-1].pop();
            }else {
                entry[record[i][0]-1].push(record[i][1]);
            }         
        }

        Map<Integer,Integer> r = new HashMap();

        for(int i = 0; i< n; i++) {
             //arr[i] = entry[i].isEmpty()? 0 : entry[i].pop();
            r.put(i+1, entry[i].isEmpty()? 0 : entry[i].pop());
        }
        
        //입찰가 기준(map.value) 으로 정렬 
        List<Entry<Integer, Integer>> list = r.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).collect(Collectors.toList());
        
        //참가자 (map.key)만 반환
        int idx=0;
        for(Entry<Integer, Integer> e: list) {
            result[idx] =e.getKey();
            idx+=1;
        }

        return result;
    }
}