자료구조 1 (연습)

17413번 단어 뒤집기 2

문제

풀이

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();
        String str = sc.nextLine() + " "; // 마지막 단어도 뒤집을 수 있게 
        boolean isCheck = false; // < 과 >의 사이에 존재 여부
        
        for(char c : str.toCharArray()) {
            if(c == '<') {
                while(!stack.isEmpty()) {
                    bw.write(stack.pop());
                }
                bw.write(c);
                isCheck = true;
            } else if(c == '>') {
                bw.write(c);
                isCheck = false;
            } else if(isCheck) {
                bw.write(c);
            } else { // 뒤집어야 할 문자열인 경우
                if(c == ' ' || c == '\n') { // 단어의 끝이라면
                    while(!stack.isEmpty()) {
                        bw.write(stack.pop());
                    }
                    bw.write(c);
                } else {
                    stack.push(c);
                }
            }
        }
        bw.flush();
        
        sc.close();
    }
}

10799번 쇠막대기

문제

풀이

해당 문제는 코딩테스트 대비 강의에서 풀이했던 문제이므로 넘어간다.

import java.util.Stack;
import java.util.Scanner;

public class Main {
    public int solution(String str) {
        int answer= 0;
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(') {
                stack.push('(');
            } else {
                stack.pop();
                if(str.charAt(i - 1) == '(') {
                    answer += stack.size();
                } else {
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        System.out.print(T.solution(str));
    }
}

17298번 오큰수

문제

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int arr[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 0; i < n; i++) {
            // 현재 원소가 스택의 가장 top 원소 보다 값이 큰 경우
            // pop한 값을 인덱스로하는 곳의 값을 현재 원소로 바꿈
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        
        while(!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }
        
        for(int i : arr) {
            sb.append(i).append(' ');
        }
        System.out.println(sb.toString());
    }
}

17299번 오등큰수

문제

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static final int MAX = 1_000_001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int cnt[] = new int[MAX];
        int index[] = new int[n];
        int answer[] = new int[n];

        for(int i = 0; i < n; i++) {
            index[i] = Integer.parseInt(st.nextToken());
            cnt[index[i]]++;
        }

        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && cnt[index[i]] > cnt[index[stack.peek()]]) {
                answer[stack.pop()] = index[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }

        for(int i = 0; i< n; i++) {
            sb.append(answer[i]).append(' ');
        }
        System.out.println(sb.toString());
    }
}