섹션5. Stack, Queue(자료구조)

1. 올바른 괄호

2. 괄호문자제거

3. 크레인 인형뽑기(카카오)

4. 후위식 연산(postfix)

5. 쇠막대기

6. 공주구하기

7. 교육과정설계

8. 응급실

---

1. 올바른 괄호

 

import java.util.*;
public class Main {
    public String solution(String str){
       String answer="YES";
       Stack<Character> stack=new Stack<>();
        for(char x:str.toCharArray()){ // 닫는 괄호가 많을때
           if(x=='(') stack.push(x);
           else{ // 닫는 괄호 일때
               if(stack.isEmpty()) return "NO";// stack이 비어있냐 => "NO"
               stack.pop(); // 그렇지 않다면 제일 상단에 있는것 제거
           }
       }
       if(!stack.isEmpty()) // 아직 비어있지 않다면
           return "NO";
       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));
    }
}

 

 

 

2. 괄호문자제거

 

 

 

 

import java.util.*;
public class Main {
    public String solution(String str){
       String answer="";
       Stack<Character> stack=new Stack<>();
       for(char x : str.toCharArray()){
           if(x==')'){ // 닫는괄호면
               while(stack.pop()!='('); // 여는 괄호 아닐때까지 pop
           }
           else // 닫는 괄호가 아니면 push
               stack.push(x);
       }
       for(int i=0; i<stack.size(); i++)
           answer+=stack.get(i);
        return answer;
    }
    public static void main(String[] args) {
       Main T=new Main();
       Scanner kb=new Scanner(System.in);
       String str=kb.nextLine();
       System.out.print(T.solution(str));
    }
}

 

 

 

3. 크레인 인형뽑기(카카오)

 

 

설명

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.

죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다.

(위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다.

모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.

게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,

이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다.

다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다.

위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다.

또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때,

크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 구하는 프로그램을 작성하세요.

 

입력 

첫 줄에 자연수 N(5<=N<=30)이 주어집니다.

두 번째 줄부터 N*N board 배열이 주어집니다.

board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.

0은 빈 칸을 나타냅니다.

1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.

board배열이 끝난 다음줄에 moves 배열의 길이 M이 주어집니다.

마지막 줄에는 moves 배열이 주어집니다.

moves 배열의 크기는 1 이상 1,000 이하입니다.

moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

출력 

첫 줄에 터트려져 사라진 인형의 개수를 출력합니다.

 

 

 

import java.util.*;
public class Main {
    public int solution(int[][] board, int[] moves){
        int answer=0;
        Stack<Integer> stack=new Stack<>();
        for(int pos : moves){ // pos = 크레인 위치
            for(int i=0; i<board.length; i++){// board.length : 행크기
                if(board[i][pos-1]!=0) { // 인형발견
                    int tmp = board[i][pos - 1]; // tmp에 인형 임시보관
                    board[i][pos-1]=0; // 인형자리에 0
                    if(!stack.isEmpty() && tmp==stack.peek()) { // stack이 비어있지 않으면서 제일 상단과 값이 같다면
                        answer += 2;
                        stack.pop(); // 상단 제거
                    }else stack.push(tmp);
                    break;
                }
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T=new Main();
        Scanner kb=new Scanner(System.in);
        int n=kb.nextInt();
        int[][] board=new int[n][n];
       for(int i=0; i<n; i++){
           for(int j=0; j<n; j++){
               board[i][j]=kb.nextInt();
           }
       }
       int m=kb.nextInt();
       int[] moves=new int[m];
       for(int i=0; i<m; i++) moves[i]=kb.nextInt();
       System.out.println(T.solution(board,moves));
    }
}

 

 

4. 후위식 연산(postfix)

 

 

 

import java.util.*;
public class Main {
    public int solution(String str){
        int answer=0;
        Stack<Integer> stack=new Stack<>();
        for(char x: str.toCharArray()){
            if(Character.isDigit(x)) stack.push(x-48); // 아스키 
            else{ // 연산자라면
                int rt=stack.pop();
                int lt=stack.pop();
                if(x=='+') stack.push(lt+rt);
                else if(x=='-') stack.push(lt-rt);
                else if(x=='*') stack.push(lt*rt);
                else if(x=='/') stack.push(lt/rt);
            }
        }
        answer=stack.get(0); // 0 번에 있는거 return
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str=kb.next();
        System.out.println(T.solution(str));
    }
}

 

 

 

5. 쇠막대기

설명

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고,

레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되,

끝점은 겹치지 않도록 놓는다.

• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치,

수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.

2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고,

이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력 

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력 

 

 

 

 

import java.util.*;
public class Main {
    public int solution(String s){
        int answer=0;
        Stack<Character> stack=new Stack<>();
        for(int i=0; i<s.length(); i++){ // for each 문으로 작성하면 index접근이 조금 곤란
            if(s.charAt(i)=='(') stack.push(s.charAt(i));
            else{ // 닫는괄호면
                stack.pop();
                if(s.charAt(i-1)=='(') answer+=stack.size(); // 이전 index=( 면 레이저
                else answer++; // 끝지점 닫는괄호라면 +1
            }
        }
        return answer;
    }
    public static void main(String[] args) {
            Main T=new Main();
            Scanner kb=new Scanner(System.in);
            String s=kb.next();
            System.out.println(T.solution(s));
        }
    }

 

 

6. 공주구하기

 

설명

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.

정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다.

정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다.

그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다.

그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다.

한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다.

그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.

이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3을 외쳐 제외된다.

이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7번 왕자에게 공주를 구하러갑니다.

N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

입력 

첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.

출력 

 

 

 

import java.util.*;

public class Main {
    public int solution(int n, int k){
        int answer=0;
        Queue<Integer> Q = new LinkedList<>();
        for(int i=1; i<=n; i++){
            Q.offer(i);
        }
        while(!Q.isEmpty()){
            for(int i=1; i<k; i++)
                Q.offer(Q.poll()); // 꺼낸 제일 앞의 값을 맨뒤로
            Q.poll(); // 제거
            if(Q.size()==1)
                answer=Q.poll();
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T=new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int k=kb.nextInt();
        System.out.println(T.solution(n,k));
    }
}

 

 

 

7. 교육과정설계

 

 

import java.util.*;

class Main {
    public String solution(String s, String str) {
        String answer="YES";
        Queue<Character> Q=new LinkedList<>();
        // 입력받은 필수목 s를 Q에 순서대로 추가
        for(char x : s.toCharArray()){
            Q.offer(x);
        }
        // 계획한 과목을 순서대로 판별
        for(char x : str.toCharArray()){
            if(Q.contains(x)){ // Q 안에 해당 과목이 있는데 (= 필수과목이다)
               if(x!=Q.poll()) return "NO"; // 근데 첫순서가 아니라면 "NO"리턴
            }
        }
        if(!Q.isEmpty()) return "NO"; // 비어있지않으면(필수과목 듣지않음) "NO"리턴
        return answer;
    }
    public static void main(String[] args) {
        Main T=new Main();
        Scanner kb = new Scanner(System.in);
        String s=kb.next();
        String str=kb.next();
        System.out.println(T.solution(s,str));
    }
}

 

 

8. 응급실

 

 

 

 

import java.util.*;
import java.util.LinkedList;
import java.io.IOException;

class Person{
    int id;
    int priority;
    public Person(int id, int priority){
        this.id=id;
        this.priority=priority;
    }
}
class Solution {
    public int solution(int n, int m, int[] arr) {
        int answer=0;
        int cnt=0;
        Queue<Person> Q=new LinkedList<>(); // Person형 Q
        for(int i=0; i<n; i++){
            Q.add(new Person(i,arr[i])); // (0,60) (1,50) (2,70) ...
        }
        while(!Q.isEmpty()){
            Person tmp=Q.poll(); // tmp = 0번째 값
            for(Person x:Q){
                if(x.priority>tmp.priority){ // 현재 tmp 값보다 우선순위가 높은 값이 있다면
                    Q.offer(tmp); // 맨뒤에 offer
                    tmp=null;
                    break;
                }
            }
            if(tmp!=null){ // 우선순위 높은게 없어서 진료 받을 수 있는 경우
                answer++; // 1증가
                if(tmp.id==m) return answer;
            }
        }
        return answer;
    }
    public static void main(String[] args) throws IOException{
        Solution T=new Solution();
        Scanner kb = new Scanner(System.in);;
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.print(T.solution(n,m,arr));
    }
}
import java.util.*;
import java.util.LinkedList;
import java.io.IOException;

class Person{
    int id;
    int priority;
    public Person(int id, int priority){
        this.id=id;
        this.priority=priority;
    }
}
class Solution {
    public int solution(int n, int m, int[] arr) {
        int answer=0;
        int cnt=0;
        Queue<Person> Q=new LinkedList<>(); // Person형 Q
        for(int i=0; i<n; i++){
            Q.add(new Person(i,arr[i])); // (0,60) (1,50) (2,70) ...
        }
        while(!Q.isEmpty()){
            Person tmp=Q.poll(); // tmp = 0번째 값
            for(Person x:Q){
                if(x.priority>tmp.priority){ // 현재 tmp 값보다 우선순위가 높은 값이 있다면
                    Q.offer(tmp); // 맨뒤에 offer
                    tmp=null;
                    break;
                }
            }
            if(tmp!=null){ // 우선순위 높은게 없어서 진료 받을 수 있는 경우
                answer++; // 1증가
                if(tmp.id==m) return answer;
            }
        }
        return answer;
    }
    public static void main(String[] args) throws IOException{
        Solution T=new Solution();
        Scanner kb = new Scanner(System.in);;
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.print(T.solution(n,m,arr));
    }
}