Stack, Queue - (2)

Stack, Queue - (2)

5-5. 쇠막대기 | 스택 사용

• 1) 여는 괄호는 일단 push
• 2) 닫는 괄호 만나면 구분
• a) 레이저인지: 바로 앞이 ( 여는 괄호일 때
• stack.size() 만큼 answer에 누적 : 레이저 왼쪽 막대기가 잘려나간 부분이므로
• b) 막대기 오른쪽인지
• answer +1 ; //그래야 오른쪽 끝 막대기 부분(닫는 괄호 1개당) 잘림 처리 가능

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

/* 5-5. 쇠막대기 
[입력]
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다.
[출력]
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
*/
public class Main1 {
    //솔루션 함수
    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();//일단 꺼내서
                //(1) 바로 앞자리가 ( 여는 괄호이면 == 레이저이므로
                //스택 사이즈만큼 막대기 잘렸을 거임
                if(str.charAt(i-1) == '(') {
                    answer += stack.size();
                }else { //(2)레이저 X==막대기 오르쪽 끝
                    answer++; //끝 부분으로 잘린 부분 담기
                }        
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        System.out.println(T.solution(str));
    }
}

---

🟨 큐 (Queue)

• ‘맨 뒤’ 데이터 추가 : offer()
• ‘맨 앞’ 데이터 꺼냄 : poll()
• ‘맨 앞’ 데이터 확인 : peek()
• 큐 사이즈 확인 : size()
• 특정 데이터 포함여부 확인 : contains()
• 내부 빈 상태 확인 : isEmpty()

---

5-6. 공주 구하기 | 큐 사용

• 1) 큐 내부 초기화
• 2) 사이클
  1. a) 1~k-1 까지 앞데이터 빼서 뒤에 붙임
  2. b) k번째 데이터는 그냥 poll()
  3. c) 큐 사이즈 1 남았을 때 걔가 answer 임

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 5-6. 공주 구하기
[입력]
첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.
[출력]
첫 줄에 마지막 남은 왕자의 번호를 출력합니다.
*/
public class Main2 {
    //솔루션 함수 
    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()) {
            //k번째 직전까지 돌면서 앞데이터는 뒤에 다시 붙임
            for(int i = 1; i<k; i++) {
                Q.offer(Q.poll());
            }
            //k번째는 그냥 뺌
            Q.poll();
            //마지막 1개가 공주구하러 갈 왕자임 
            if(Q.size() == 1) answer = Q.poll();
        }    
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();

        System.out.println(T.solution(n, k));
    }
}

---

5-7. 교육과정 설계

• 1) 필수과목순서는 큐에 세팅
• 2) 계획서 내부를 돌면서
  1. a) 내부 각 과목이 큐에 담겨있으면 isContains()
  2. b) 그런데 현재의 큐 맨앞 데이터 poll != 현재의 과목과 다를 경우 :순서X => NO
• 3) 내부 다 순회한 뒤에도 여전히 큐가 남아있다면 아직 이수X 필수과목 존재하므로 =>NO

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 5-7. 교육과정 설계 | 큐 사용
[입력]
첫 줄에 한 줄에 필수과목의 순서가 주어집니다. 모든 과목은 영문 대문자입니다.
두 번 째 줄부터 현수가 짠 수업설계가 주어집니다.
[출력]
첫 줄에 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력합니다.
*/
public class Main3 {
    //솔루션 함수 
    public String solution(String need, String plan ) {
        String answer = "YES";
        Queue<Character> Q = new LinkedList<>();

        //필수과목 모두 세팅
        for(char x : need.toCharArray()) Q.offer(x);
        //계획표 돌면서
        for(char x : plan.toCharArray()) {
            if(Q.contains(x)) { //현재의 과목이 필수과목에 존재하면 
                //근데 그 과목이 큐 첫번째 값과 다르면 순서 X : "NO"
                if(x != Q.poll()) return "NO";
            }
        }
        //다 순회했는데도 필수과목에 무언가 남아있으면 이수하지 않은 필수과목 존재하는 것이므로 : "NO"
        if(!Q.isEmpty()) return "NO";

        return answer;
    }


    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);

        String a = kb.next();
        String b = kb.next();

        System.out.println(T.solution(a, b));
    }
}

---

5-8. 응급실

1) Person 클래스 (id, 우선순위) 만듬

2) 큐에 처음 대기순서, 우선순위를 담고

3) 큐에 데이터 존재하는 동안 반복하면서

1. a) 현재의 큐 맨 앞을 tmp로 뺴와서
2. b) 큐 전체 순회하며 현재의 tmp 우선순위보다 높은 애 존재할 경우
3. c) 현재의 tmp는 큐 맨 뒤로 보내고, 현재의 tmp를 null 처리

4) for문 다 돌고도 여전히 tmp가 null 아닌 경우는, 현재의 tmp가 가장 우선순위 높은 애인 것이므로 id가 우리가 찾는 m인지 확인 후 answer 세팅

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 5-8. 응급실
[입력]
첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.
두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.
위험도는 값이 높을 수록 더 위험하다는 뜻입니다.
[출력]
M번째 환자의 몇 번째로 진료받는지 출력하세요.
*/

//각 사람 클래스 생성
class Person{
    int id; 
    int priority;
    public Person(int id, int priority) {
        this.id = id;
        this.priority = priority;
    }
}
// 메인 클래스
public class Main4 {
    //솔루션 함수
    public int solution(int n, int m, int[]arr) {
        int answer= 0;
        Queue<Person> Q = new LinkedList<>();
        //큐 내부 = 대기환자 초기화
        for(int i = 0; i<n; i++) {
            Q.offer(new Person(i, arr[i]));
        }
        //내부 순회
        while(!Q.isEmpty()) {
            //큐에 존재하는 첫 번째 환자tmp 꺼내서 
            Person tmp = Q.poll();
            //큐 내부 돌며
            for(Person x : Q) {
                //꺼낸 tmp보다 우선순위 더 높은 x가 큐에 존재할 경우 
                if(x.priority>tmp.priority) {
                    Q.offer(tmp); //일단 꺼낸 애는 뒤에 담기 
                    tmp = null;//기존 tmp = null
                    break; //탈출
                }
            }
            //탈출했는데도 여전히 tmp 가 null 아니라면
            // -> 자기보다 우선순위 높은 애가 없어서 자기가 진료받는 사람인 거임
            if(tmp!= null) {
                answer++;
                //진료 받은 사람id가 우리가 찾는 사람이면 현재의 answer 리턴
                if(tmp.id == m) return answer;
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4  T = new Main4();
        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.println(T.solution(n, m, arr));
    }
}