BLOG :||

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String text = "0";
        int len = number.length();
        k = number.length()-k;
        Stack<String> s = new Stack<>();//stack을 어떻게 유추하나
        s.push(number.substring(0,1));
        for(int i = 1; i<len;++i) {
            while(s.size() > 0 &&Integer.parseInt(s.peek()) < Integer.parseInt(number.substring(i,i+1)) && s.size()-1+len-i >= k) {
                s.pop();
            }
            if(s.size() < k)//pop조건에서 제외되어도 사이즈에 따라 예외처리는 해야 한다.
                s.push(number.substring(i,i+1));
        }
        String t = "";
        while(s.size() > 0) {
            t= s.pop()+t;
        }
        while(true) {
            if(t.charAt(0) == '0')
                t = t.substring(1, t.length());
            else
                break;
        }
        return t;
    }
/*
    public String solution(String number, int k) {
        String text = "0";
        int val = -1;
        int max = getRemoveNumT(0,k,number, val);
        
        return Integer.toString(max);
    }
    public int getRemoveNumT(int originI, int k, String number, int max) {
        String tmp = "";
        for(int i = originI; i<number.length()-k+1;++i) {
            if(i == 0)
                tmp = number.substring(i+1, number.length());
            else {
                tmp = number.substring(0, i)+number.substring(i+1, number.length());
            }
            if(k == 1) {
            	if(max < Integer.parseInt(tmp))
            		max = Integer.parseInt(tmp);
            }
            else {
            	int t = getRemoveNumT(i, k-1, tmp, max);
            	if(t > max)
            		max = t;
            }
        }
		return max;
    }
*/
}

처음에 재귀로 했다가 효율성 테스트에서 시간 초과가 떴었다.

뭐가 문제일까 하면서 다른 사람이 질문한 내용을 봤는데 stack을 쓰면 좋다고 하는 글을 보고...

고민해보고 풀어보니까 감탄이 나오더라.

제외해야 되는 글자 수에 걸리지 않는 한에서

peek()보다 현재 값이 크면 값을 pop()하고 push()를 한다.

코딩테스트에서 문제만 푸는건 요새는 다들 하니까 이런 효율성을 찾으려고 해야 한다..

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        if(people.length == 1)
            return 1;
        Arrays.sort(people);
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i<people.length;++i)
            list.add(people[i]);
        int len = 0;
        int big = 0;
        while(list.size() > 0) {
            len = list.size();
            big = list.get(len-1);
            if(list.size() >1 && big+list.get(0) <= limit) {
                list.remove(list.size()-1);
                list.remove(0);
            }
            else {
                list.remove(list.size()-1);
            }
            answer++;
        }
        
        return answer;
    }
}

인원을 무게 순으로 정렬한다.

가장 무게가 나가는 사람이 가장 가벼운 사람을 태우지 못하면 배 하나 들고 나간다.

태울 수 있으면 태운다. 끝이다.

지금 생각해보니 저걸 list로 하지말고 deque를 쓰는게 좋았을텐데..

deque나 set이나 회사에서 잘 안쓰는 자료구조는 까먹을 때가 많아서 문제다.

import java.util.*;
class route implements Comparable<route>{
    int a;
    int b;
    int c;
    public route(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    @Override
    public int compareTo(route r) {
        if(a < r.a)
            return -1;
        else if(a > r.a)
            return 1;
        else {
            if(c < r.c)
                return -1;
            else if(c > r.c)
                return 1;
            else 
                return 0;
        }
    }
}

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<route> list = new ArrayList<>();
        for(int i = 0; i<routes.length;++i) {
            list.add(new route(routes[i][0],i, 0));
            list.add(new route(routes[i][1],i, 1));
        }
        
        Collections.sort(list);
        //Queue<route> stack = new LinkedList<>();
        //int min = list.get(0).a;
        //int max = list.get(list.size()-1).a;
        //stack.add(list.get(0));
        int minC = -30001;
        for(int i = 0; i<list.size();++i) {
            route t = list.get(i);
            if(t.c == 1) {
                if(minC < routes[t.b][0]) {
                    answer++;
                    minC = t.a;
                }
            }
        }
        // c             d
        //-20 1 0, -18 3 0, -14 2 0, -13 3 1, -5 4 0, -5 2 1, -3 4 1, 15 1 1
        
        //들어온 뒤에 처음 나가는 것이 있을 경우 카메라를 놓는다.
        //나간 것이 존재하고 이후에 값이 들어올 경우, 
        return answer;
    }
}

취업한 이후로 블로그 쓰고 싶지 않았는데.. 계속 했어야 했다.

스터디 책에서 그리디 알고리즘이 나왔으므로 관련 문제를 올려본다.

키 포인트는 카메라를 두는 조건을 명확히 설정을 하고 이에 맞춰 코딩을 해야 한다.

일단 차량이 들어오고 나가는 각 시점을 시간 순으로 정렬을 해야겠다 싶어서 이를 따로 쪼개 list에 넣고 정렬을 했다.

차량 진출시점의 최소값이 -30000이었기 때문에 우선 카메라 위치의 min 값으로 -30001을 잡았고

for문을 돌리면서 list 내의 객체가 out일 때(c==1) 마지막 카메라의 위치가 차가 진입한 시점보다 이전이면 나갈때 카메라를 하나 세워주는 식으로 진행했다. 차량의 inout을 시간순으로 정렬했기 때문에 마지막 카메라 위치만 알면 되니까 값을 따로 기억하지는 않고 마지막 카메라 위치만 체크해서 풀면 꽤 간단했다.