[JAVA] 백준 스택 부수기 2

 

6198 옥상 정원 꾸미기 - 골드5

https://www.acmicpc.net/problem/6198

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    Stack<Long> stack = new Stack<>();
    long count = 0;
    for (int i = 0; i < cnt; i++) {
        long num = Long.parseLong(br.readLine());

        while (!stack.isEmpty() && stack.peek() <= num) {
            stack.pop();
            count += stack.size();
        }

        stack.push(num);
    }

    long tmp = stack.size()-1;
    if (tmp > 0) {
        count += (tmp * (tmp+1) / 2);
    }
    System.out.println(count);
}

 

long타입 때문에 한 번 틀렸다. 어렵지는 않은 문제다.

"나를 볼 수 있는 빌딩의 수"를 구하는 문제로 변형하면 스택에 순서대로 넣고 뺄 수 있다.

 

 

 

17178 줄서기 - 골드5

https://www.acmicpc.net/problem/17178

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int lineCnt = Integer.parseInt(br.readLine());
        boolean isBad = false;
        Stack<Ticket> stack = new Stack<>();
        Ticket lastTicket = new Ticket('A', 0);
        for (int i=0; i<lineCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j =0; j<5; j++) {
                if (isBad) 
                    break;
                
                String input = st.nextToken();
                String[] split = input.split("-");
                Ticket current = new Ticket(split[0].charAt(0), Integer.parseInt(split[1]));

                if (stack.isEmpty()) {
                    stack.push(current);
                    continue;
                }

                while (!stack.isEmpty() && current.prevThanMe(stack.peek())) {
                    if (lastTicket.prevThanMe(stack.peek())) {
                        isBad = true;
                        break;
                    }

                    lastTicket = stack.pop();
                }

                stack.push(current);
            }
        }

        if (stack.peek().prevThanMe(lastTicket) && !isBad) 
            System.out.println("GOOD");
        else 
            System.out.println("BAD");
    }
    
    static class Ticket {
        char alphabet;
        int number;

        public Ticket(char alphabet, int number) {
            this.alphabet = alphabet;
            this.number = number;
        }

        public boolean prevThanMe(Ticket ticket) {
            if (ticket.alphabet == this.alphabet) {
                if (ticket.number < this.number) 
                    return true;
                else 
                    return false;
            }

            if (ticket.alphabet - this.alphabet > 0) 
                return false;
            
            return true;
        }
    }
}

 

로직은 그려졌는데, 예외 케이스 때문에 틀릴까봐 조마조마했다.

스택문제는 stack이 비었을 때 peek()을 호출하면 에러가 나는 등 예외케이스가 많아서 메모없이는 못풀 것 같다.

골드5밖에 안되는데 긴장했따...

 

 

 

 

1662 압축 - 골드4

https://www.acmicpc.net/problem/1662

 

public class Main {
    static class Tmp {
        char c;
        int num;

        public Tmp(char c, int num) {
            this.c = c;
            this.num = num;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        Stack<Tmp> stack = new Stack<>();
        for (int i =0; i<input.length(); i++) {
            char c = input.charAt(i);

            if (c  != ')') {
                stack.add(new Tmp(c, 1));
                continue;
            }

            int count = 0;
            while (!stack.isEmpty()) {
                Tmp pop = stack.pop();

                if (pop.c == '(') {
                    count *= Character.getNumericValue(stack.pop().c);
                    break;
                }

                count += pop.num;
            }

            stack.push(new Tmp(c, count));
        }

        int count = 0;
        while (stack.size() != 1) 
            count += stack.pop().num;
        
        System.out.println(count + stack.pop().num);
    }
}

 

어려운 문제는 아니지만 문제 이해하는데 시간이 좀 걸렸다. 

아직도 스택문제 풀 때 긴장하는 걸 보니 아직 덜 익숙해진 것 같다.

 

 

 

 

1863 스카이라인 쉬운거 - 골드4

https://www.acmicpc.net/problem/1863

 

public static void main(String[] args) throws IOException {
    BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    Stack<Integer> stack = new Stack<>();
    int result = 0;
    for (int i=0; i<cnt; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken(); //x
        int y = Integer.parseInt(st.nextToken());

        while (!stack.isEmpty()) {
            if (stack.peek() == y) {
                stack.pop();
                continue;
            }

            if (stack.peek() < y) 
                break;

            stack.pop();
            result++;
        }

        if (y != 0) 
            stack.push(y);
    }

    System.out.println(result + stack.size());
}

 

아이디어만 잘 떠올리면 어렵지 않은 문제다. 0이 들어오는 경우만 잘 고려해주면 된다.

 

 

 

2374 같은 수로 만들기 - 골드4 (강추)

https://www.acmicpc.net/problem/2374

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cnt = Integer.parseInt(br.readLine());

        long result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i =0; i<cnt; i++) {
            int num = Integer.parseInt(br.readLine());

            if (stack.isEmpty()) {
                stack.add(num);
                continue;
            }

            int min = Integer.MAX_VALUE;

            boolean flag = false;
            while (!stack.isEmpty() && stack.peek() < num) {
                flag = true;
                int tmp = stack.pop();
                if (min > tmp) {
                    min = tmp;
                }
            }

            if (flag) {
                result += ((long)num - min);
            }
            stack.add(num);
        }

        if (stack.isEmpty() || stack.size() == 1) {
            System.out.println(result);
        } else {
            int tmpMin =stack.pop();
            while (!(stack.size() == 1)) {
                stack.pop();
            }

            result += ((long)stack.pop() - tmpMin);
            System.out.println(result);
        }
    }
}

 

종이에 그리면서 스택에서 빠지는 경우를 생각하면 쉽게 구할 수 있다. 내림차순으로 쌓아나가면서 쌓아야할 곳을 찾아내는 식으로 진행하면 된다.

몇 번 틀려서 스트레스를 많이 받았는데 정말 좋은문제라고 생각한다.

 

 

 

2800 괄호 제거 - 골드4

https://www.acmicpc.net/problem/2800

 

class InputCharacter {
    char c;
    int idx;

    public InputCharacter(char c, int idx) {
        this.c = c;
        this.idx = idx;
    }
}

public class Main {
    static List<int[]> bracketList = new ArrayList<>();
    static boolean[] visit;
    static String input;
    static TreeSet<String> pq = new TreeSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        findBracket();
        visit = new boolean[bracketList.size()];
        johap(0);

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()) {
            sb.append(pq.pollFirst()).append("\n");
        }

        System.out.print(sb);
    }

    private static void johap(int idx) {
        if (idx >= bracketList.size())
            return;

        for (int i =idx; i<bracketList.size(); i++) {
            visit[i] = true;
            addPq();
            johap(i+1);
            visit[i] = false;
        }
    }

    private static void addPq() {
        StringBuilder sb = new StringBuilder();
        boolean[] notPrint = new boolean[input.length()];

        for (int i =0; i<bracketList.size(); i++) {
            if (visit[i]) {
                notPrint[bracketList.get(i)[0]] = true;
                notPrint[bracketList.get(i)[1]] = true;
            }
        }

        for (int i =0; i<notPrint.length; i++) {
            if (!notPrint[i]) {
                sb.append(input.charAt(i));
            }
        }

        pq.add(sb.toString());
    }

    private static void findBracket() {
        Stack<InputCharacter> stack = new Stack<>();

        for (int i =0; i<input.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(new InputCharacter(input.charAt(i), i));
                continue;
            }

            if (input.charAt(i) == ')') {
                while (stack.peek().c != '(') {
                    stack.pop();
                }

                bracketList.add(new int[]{stack.peek().idx, i});
                stack.pop();
            } else {
                stack.push(new InputCharacter(input.charAt(i), i));
            }
        }
    }
}

 

"서로 다른" 이라는 글자를 안읽어서 틀렸다. 

제대로 문제를 읽어야겠다..ㅠ

 

 

 

9935 문자열 폭발 - 골드4(추천x)

https://www.acmicpc.net/problem/9935

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String pattern = br.readLine();

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));

            if (stack.size() >= pattern.length()) {
                boolean flag = true;

                for (int j = 0; j < pattern.length(); j++) {
                    if (stack.get(stack.size() - pattern.length() + j) != pattern.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = 0; j < pattern.length(); j++) {
                        stack.pop();
                    }
                }
            }
        }

        if (stack.isEmpty()) {
            System.out.println("FRULA");
        } else {
            StringBuilder sb = new StringBuilder();
            for (Character c : stack) {
                sb.append(c);
            }

            System.out.println(sb);
        }
    }
}

시간초과와 메모리 초과를 많이 겪고 충격을 받은 문제다. 풀이를 고집해서 정답을 보는 시간이 많이 지체됐다. 

풀이를 보고 이해한 후, 맞았습니다를 받은 후에도 문제 이해가 안됐다. 아무래도 문제 설명이 잘못됐다고 생각하여 질문글을 올려뒀다. 

백준은 확실히 설명이 불충분한 문제가 많은 것 같다. 스트레스 안받도록 노력해야지