Chapter 05. Stack, Queue (자료구조)

1. 올바른 괄호

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
   	String str = in.next();
    System.out.println(T.solution(str));
    return ;
  }
  
  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;
  }
}

  Note)

  - 괄호가 있으면 거의 스택 문제이다.

 

 

2. 괄호 문자제거

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
 	Main T = new Main();
    Scanner in=new Scanner(System.in);
    String str = in.next();
    System.out.println(T.solution(str));
    return ;
  }
 	public String solution(String str){
    	String answer = "";
      	Stack<Character> stack = new Stack<>();
      	for(char x :  str.toCharArray()){
        	if(x == ')'){
              	while( stack.pop() != '('); 	//?????
             }
          	else stack.push(x);	// 여는 괄호일 때
        }
      	for (int i = 0; i < stack.size(); ++i) answer += stack.get(i);
      	return answer;
    }
}

  Note)

  - 여는 괄호와 알파벳을 push()한다.

  - 닫는 괄호를 만나면 여는 괄호까지 pop()을 시킨다.

  - pop()은 stack()에서 꺼내면서 반환한다.

  - while() 문은 중괄호 절 없이도 수행이 된다.

  - 스택은 stack.get(i)으로 인덱스 접근 가능하다.

  - while( stack.pop() != '(' ); 여는 괄호가 나올 때까지 pop()하라는 의미

 

 

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

<hide/>
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){	
      // 2차원 배열의 행 크기(개수)
      	if(board[i][pos - 1] != 0){			
        // 인형이 발견된 경우
        	int tmp = board[i][pos-1];		
            // 인형번호를 넣는다.
        	board[i][pos - 1] = 0;			
            // 인형 가져왔으니 빈칸으로 만들어버린다.
          	if(!stack.isEmpty() && tmp  == stack.peek() ){	
            // stack의 맨 위에 있는 인형과 tmp가 같은지 확인한다.
            	answer += 2;	// 같으면 두개가 터진다.
              	stack.pop();
            }else stack.push(tmp);
          	break;	
        }
      }
    }
  	return answer;
  }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int [][]board = new int[n][n];
    for(int i = 0; i < n ; ++i ){
    	for(int j = 0; j < n; ++j){
        	board[i][j] = in.nextInt();
        }
    }
    
    int m = in.nextInt();
    int []moves = new int[m];
    for(int i = 0;i < m; ++i){
    	moves[i]=  in.nextInt();
    }
    System.out.println(T.solution(board, moves));
    return ;
  }
}

  Note)

  - 터뜨려진 인형 개수 출력하기

  - pop()으로 꺼내기 전에 같은지 비교한다.

  -  board.length : 2차원 배열의 행 크기 (몇 줄인지)

    -> board[0].length : 2차원 배열의 열 크기 (0번 행이 칸이 몇 칸인지) 

  - 반드시 break 필요하다.

 

4. 후위식 연산 (postfix)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    String str = in.next();
    System.out.println(T.solution(str));
    return ;
  }
  
  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);	
      	// 숫자면 stack에 넣는다 . 
       	// 0의 ASCII: 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);
    // Stack에 하나 남는 값이 연산결과
  	return answer;
  }
}

 

  Note)

  - lt  (연산기호) rt 임에 주의한다.

  - str에서 꺼낸 character의 값이 숫자이면 push()한다.

  - 숫자가 아닌 네 가지 연산기호의 경우에는 각각 연산결과를 새로  push()해준다.

  - isDigit()는 Character의 메서드이다.

  - stack은 Integer로 이루어져 있는 stack을 만든다.

 

 

5. 쇠막대기

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
  	String str = in.next();
    System.out.println(T.solution(str));
    return ;
  }
  
  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(str.charAt(i)); 
      
      else{
      	stack.pop();
        // 여는 괄호 pop()
        if(str.charAt(i - 1) == '(') answer += stack.size();	
        // 레이저 지점 자른다. (스택에 있는 막대기 개수를 누적한다.)
      	else  answer++;
       // 막대기의 끝인 경우이다.
      }
    }
    return answer;
  }
}

  Note)

  - 괄호가 쌍'()'으로 나오면 레이져 발사한다.

  - 닫는 괄호가 나왔을 때, peek()한 게 여는 괄호이면, pop() 시킨다.

  - 닫는 괄호가 막대기의 끝인 경우, 하나를 더해준다.

  - answer += stack.size();

 

 

6. 공주 구하기

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    System.out.println(T.solution(n, k));
    return ;
  }
  public int solution(int n, int k){	// 8, 3
  	int answer = 0;
  	Queue<Integer> Q = new LinkedList<>();
    for(int i = 1; i <= n ; ++i) Q.offer(i);	// 1 ~ 8 차례대로 Q에 넣기
    
    while(!Q.isEmpty()){
    	for(int i = 1; i < k; ++i)  Q.offer(Q.poll());	
        // k보다 작은원소는 꺼내서 뒤에 넣는다.
      	Q.poll();	// 3, 6, 1, 5,2, 8, 4 차례대로 Q에서 제거한다.
      	if(Q.size() == 1) answer += Q.poll();
    }
  	return answer;
	}
}

  Note)

  - Queue 이용한다. 

 

 

7. 교육과정

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in = new Scanner(System.in);
    String need = in.next();
    String plan = in.next();
    System.out.println(T.solution(need, plan));
    return ;
  }
  
  public String solution(String need, String plan){
    Queue<Character> Q = new LinkedList<>();	
 	String  answer = "YES";
      
     for(char x : need.toCharArray()) Q.offer(x);	// Q에 필수과목 넣는다.
     for(char x : plan.toCharArray()) {
      	if(Q.contains(x)){			// 다른 문자는 신경쓰지 않는다.
        	if(x != Q.poll()) return "NO";
        }
      }
      if(!Q.isEmpty()) return "NO";	// 필수 과목을 이수하지 않은 경우
      return answer;
    }
}

  Note)

  - 마지막에 Q가 꼭 비어 있어야한다.

  - for문 ( 필요한 문자가 있는 경우에만 확인한다. ) 

  - 마지막에 필수 과목을 이수하지 않은경우는 Q가 비어있지 않으므로 no를 리턴한다.

  - Q.contains()를 이용한다.

 

 

8. 응급실

<hide/>
import java.util.*;
class Person{	// id와 위험도를 나타내는 Person 객체를 만든다.
	int id;
  	int priority;
	public Person(int id, int priority){
    	this.id = id;
      	this.priority = priority;	// 위험도
    }
}

public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();	// 환자 수
    int m = in.nextInt();
    int [] arr = new int[n];
    
    for(int i = 0; i < n; ++i){
 	   arr[i] = in.nextInt();	// 위험도 배열
    }
    System.out.println(T.solution(n, m, arr));
    return ;
  }
  
  public int solution(int n, int m, int [] arr){
  	int answer = 0;
    Queue<Person> Q = new LinkedList<>();	
    // Person형으로 Queue만들기
   
    for(int i = 0 ; i < n; ++i){
    	Q.offer(new Person(i, arr[i]));	
        // 객체 생성해서 Q에 넣느다.
    }
    while(!Q.isEmpty()){
    	Person tmp = Q.poll();
      	for(Person x : Q){
      		if(x.priority > tmp.priority){		// 아직 우선순위가 아닐 때
            //tmp 순서가 되는지 알기위한 반복문
        		Q.add(tmp);		// 아직 진료할 때가 아니기 때문에 뒤로 넣는다.
          		tmp = null;		// 
        		break;
        	}	
      	 }
      	if(tmp != null){	// 진료 가능해지는 경우
           	answer++;
        	if(tmp.id == m) return answer;
        }
    }
    return answer;
  }
}

  Note)

  - id와 priority를 인스턴스 변수로 갖는 Person 클래스를 만든다.

  - Person형 Queue를 만든다.