본문 바로가기
Java/Java

[리뷰] 해결 못한 알고리즘 다시 풀기 -3

앤 썸 2022. 7. 8. 16:22
728x90
반응형

1. 올바른 괄호 stack

package stackqueue.ch05_2;

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

//올바른 괄호
//isEmpty로 확인
//push, peek,pop
public class Stackqueue01 {
	public String solution(String str) {
		String answer = "YES";
		Stack<Character> stack = new Stack<>();
		for (char x : str.toCharArray()) {
			stack.push(x);
		}
		int cnt = 0;
		while (!stack.isEmpty()) {
			if (stack.pop() == ')') {
				if (stack.isEmpty())
					return answer = "NO";
				while (stack.pop() != '(') {
					cnt++;
				}

				while (cnt != 0) {
					stack.push(')');
					cnt--;
				}
			} else
				answer = "NO";
		}

		return answer;
	}

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

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//넣고 확인하는 것이 아니라 넣으면서 확인
public class Stackqueue01_2 {
	public String solution(String str) {
		Stack<Character> stack = new Stack<>();
		String answer="NO";
		for(char x : str.toCharArray()) {
			if(x=='(') stack.push(x);
			else {
				if(stack.isEmpty()) return answer;
				stack.pop();
			}
		}
		if(!stack.isEmpty()) return answer;
		else return answer="YES";
		
	}
	public static void main(String[] args) {
		Stackqueue01_2 T = new Stackqueue01_2();
		Scanner kb = new Scanner(System.in);
		String str= kb.next();
		
		System.out.println(T.solution(str));
	}

}

 

2. 괄호문자 제거 stack

package stackqueue.ch05_2;

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

//괄호문자제거
// 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면, pop
// 스택이 비어있을 때만, 문자열에 추가하는 방식

public class Stackqueue02 {
	public String solution(String str) {
		String answer = " ";
		StringBuilder sb= new StringBuilder();
		Stack<Character> stack = new Stack<>();
		char[] arr = str.toCharArray();
		for (int i = 0; i < arr.length; i++) {
			
		
			if (arr[i] == '(') stack.push(arr[i]);
		
			else if (arr[i]==')') stack.pop();
			
			if(stack.isEmpty()&&arr[i]!='('&&arr[i]!=')')
				sb.append(arr[i]);
			
		}

		return answer=sb.toString();
	}

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

}

 

package stackqueue.ch05_2;
//일단 모두 넣고, 닫는 괄호가 나오면, 여는 괄호가 나올때까지 pop

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

public class Stackqueue02_2 {
	public String solution(String str) {
		String answer=" ";
		Stack<Character> stack =new Stack<>();
		char[] arr = str.toCharArray();
		for(int i=0;i<arr.length;i++) {
			if(arr[i]==')') {
				while(stack.pop()!='(');
			}
			else
				stack.push(arr[i]);
		}
		
		StringBuilder sb= new StringBuilder();
		while(!stack.isEmpty()) sb.append(stack.pop());
		
		return answer=sb.reverse().toString();
	}
	public static void main(String[] args) {
		Stackqueue02_2 T= new Stackqueue02_2();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//1. stack을 get을 이용해 순서대로 출력
//2. stack을 메서드 이용하지 않고 순서대로 출력
public class Stackqueue02_3 {
	public void solution(String str) {
		Stack <Character> stack=new Stack<>();
		for(char x:str.toCharArray()) {
			if(x==')') {
				while(stack.pop()!='(');
			}
			else
				stack.push(x);		
		}
		//1
		for(char x:stack) System.out.print(x);
		
		System.out.println();
		
		//2
		for(int i=0;i<stack.size();i++) System.out.print(stack.get(i));
	}
	public static void main(String[] args) {
		Stackqueue02_3 T=new Stackqueue02_3();
		Scanner kb= new Scanner(System.in);
		String str=kb.next();
		T.solution(str);
	}

}

 

3. 크레인 인형뽑기 stack

package stackqueue.ch05_2;

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

public class Stackqueue03 {
	public int solution(int n, int[][] arr1, int m, int[] arr2) {
		int answer = 0;
		Stack<Integer> stack = new Stack<>();

		for (int x : arr2) {
			for (int j = 0; j < n; j++) {
				if (arr1[j][x] != 0) {
					if (!stack.isEmpty()) {
						if (stack.peek() != arr1[j][x]) {
							stack.push(arr1[j][x]);
							arr1[j][x]=0;
						} else {
							arr1[j][x]=0;
							stack.pop();
							answer+=2;
						}
					} else {
						stack.push(arr1[j][x]);
						arr1[j][x]=0;
					}

					break;
				}
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		Stackqueue03 T = new Stackqueue03();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr1 = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr1[i][j] = kb.nextInt();
			}
		}
		int m = kb.nextInt();
		int[] arr2 = new int[m];
		for (int j = 0; j < m; j++)
			arr2[j] = kb.nextInt()-1;
		System.out.println(T.solution(n, arr1, m, arr2));
	}

}

+) 세련된 풀이

package stackqueue.ch05_2;

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

//배열 초기화 한번만 하기위해 tmp라는 임시변수에 배열 값 저장
public class Stackqueue03_2 {
	public int solution(int n, int[][] arr1, int m, int [] arr2) {
		Stack<Integer> stack = new Stack<>();
		int answer=0;
		
		for(int x:arr2) {
			for(int j=0;j<n;j++) {
				if(arr1[j][x]!=0) {
					int tmp=arr1[j][x];
					arr1[j][x]=0;
					if(!stack.isEmpty()&&stack.peek()==tmp) {
						stack.pop();
						answer+=2;
					}
					else stack.push(tmp);
					break;
				}
				
			}
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Stackqueue03_2 T = new Stackqueue03_2();
		Scanner kb = new Scanner(System.in);
		
		int n=kb.nextInt();
		int[][] arr1 = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				arr1[i][j]=kb.nextInt();
			}
		}
		int m=kb.nextInt();
		int[] arr2=new int[m];
		for(int i=0;i<m;i++) arr2[i]=kb.nextInt()-1;
		
		System.out.println(T.solution(n, arr1, m, arr2));
	}

}

 

4. 후위식 연산 stack

package stackqueue.ch05_2;
//스택에 연산자 까지 넣고
import java.util.Scanner;
import java.util.Stack;

public class Stackqueue04 {
	public int solution(String str) {
		int answer=0;
		Stack<Integer> stack = new Stack<>();
		for (char x : str.toCharArray()) {
			if (x == '+') {
				int tmp = stack.pop();
				stack.push(stack.pop() + tmp);
			} else if (x == '-') {
				int tmp = stack.pop();
				stack.push(stack.pop() - tmp);
			} else if (x == '*') {
				int tmp = stack.pop();
				stack.push(stack.pop() * tmp);
			} else if (x == '/') {
				int tmp = stack.pop();
				stack.push(stack.pop() / tmp);
			} else
				stack.push(Character.getNumericValue(x));
		}

		return answer=stack.pop();
	}

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

 

package stackqueue.ch05_2;
//스택에 숫자만 넣고, 연산자를 만날경우 스택에서 pop

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

public class Stackqueue04_2 {
	public int solution(String str) {
		int answer=0;
		Stack<Integer> stack = new Stack<>();
		for(char x: str.toCharArray()) {
			if(x=='+') {
				int i=stack.pop();
				int j=stack.pop();
				stack.push(j+i);
			}
			else if(x=='-') {
				int i=stack.pop();
				int j=stack.pop();
				stack.push(j-i);
				
			}
			else if (x=='/') {
				int i=stack.pop();
				int j=stack.pop();
				stack.push(j/i);
			}
			else if(x=='*') {
				int i=stack.pop();
				int j=stack.pop();
				stack.push(j*i);
			}
			else
				stack.push(Character.getNumericValue(x));
		}
	
		return answer=stack.pop();
	}
	public static void main(String[] args) {
		Stackqueue04_2 T = new Stackqueue04_2();
		Scanner kb = new Scanner(System.in);
		String str = kb.next();
		System.out.println(T.solution(str));
	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

public class Stackqueue04_3 {
	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);
			}
		}
		
		return answer=stack.pop();		
	}
	public static void main(String[] args) {
		Stackqueue04_3 T = new Stackqueue04_3();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}

}

 

5. 쇠막대기 stack

package stackqueue.ch05_2;

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

public class Stackqueue05 {
	public int solution(String str) {
		Stack<Character> stack = new Stack<>();
		int answer=0;
		char[] arr = str.toCharArray();
		for(int i=0;i<str.length();i++) {
			if(arr[i]=='(') {
				i++;
				if(arr[i]==')')
					answer+=stack.size();
				else {
					i--;
					stack.push('(');
				}
			}else {
				stack.pop();
				answer++;
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		Stackqueue05 T = new Stackqueue05();
		Scanner kb=new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//str.charAt()을 이용해 문자열의 문자에 접근
public class Stackqueue05_3 {
	public int solution(String str) {
		Stack<Character> stack = new Stack<>();
		int answer = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				stack.push(str.charAt(i));
			} else if (str.charAt(i - 1) == '(') {
				stack.pop();
				answer += stack.size();
			} else {
				stack.pop();
				answer++;
			}

		}

		return answer;
	}

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

}

 

6. 공주구하기 queue

package stackqueue.ch05_2;

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

public class Stackqueue06 {
	public int solution(int n, int m, int[] arr) {
		int answer = 0;
		Queue<Integer> q = new LinkedList<>();
		for (int x : arr)
			q.offer(x);

		while (!q.isEmpty()) {
			for (int i = 1; i < m; i++) {
				q.offer(q.poll());
			}
			q.poll();
			if (q.size() == 1)
				answer = q.poll();
		}

		return answer;
	}

	public static void main(String[] args) {
		Stackqueue06 T = new Stackqueue06();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = i + 1;
		int m = kb.nextInt();
		System.out.println(T.solution(n, m, arr));
	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//직접 배열에 넣지않고, 바로 stack에 넣는 방법
public class Stackqueue06_2 {
	public int solution(int n, int m) {
		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 < m; i++)
				q.offer(q.poll());
			q.poll();
			if(q.size()==1) answer=q.poll();
		}

		return answer;
	}

	public static void main(String[] args) {
		Stackqueue06_2 T = new Stackqueue06_2();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		System.out.println(T.solution(n, m));
	}

}

 

7. 교육과정설계 queue

package stackqueue.ch05_2;

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

public class Stackqueue07 {
	public String solution(String str1, String str2) {
		String answer = "NO";
		Queue<Character> q = new LinkedList<>();
		for (char x : str1.toCharArray())
			q.add(x);

		for (char x : str2.toCharArray()) {
			if (q.isEmpty()) {
				return answer="YES";
			} else {
				if (q.peek() == x)
					q.poll();
				else if (q.contains(x))
					return answer;
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		Stackqueue07 T = new Stackqueue07();
		Scanner kb = new Scanner(System.in);
		String str1 = kb.next();
		String str2 = kb.next();
		System.out.println(T.solution(str1, str2));

	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//x!=Q.poll, !Q.isEmpty()
public class Stackqueue07_2 {
	public String solution(String str1, String str2) {
		String answer="NO";
		Queue<Character> q = new LinkedList<>();
		for(char x : str1.toCharArray()) q.offer(x);
		for(char x : str2.toCharArray()) {
			if(q.contains(x)) {
				if(q.poll()!=x) return answer; 
			}
		}
		
		if(q.isEmpty()) return answer="YES";
		
		return answer;
	}
	public static void main(String[] args) {
		Stackqueue07_2 T = new Stackqueue07_2();
		Scanner kb = new Scanner(System.in);
		String str1= kb.next();
		String str2= kb.next();
		System.out.println(T.solution(str1, str2));
	}

}

 

8. 응급실 queue

package stackqueue.ch05_2;

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

public class Stackqueue08 {
	public int solution(int n,int m,int[] arr) {
		int answer=0;
		Queue<Integer> q = new LinkedList<>();
		for(int x : arr) {
		}
	
		
		return answer;
	}
	public static void main(String[] args) {
		Stackqueue08 T = new Stackqueue08();
		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));
	}

}

 

+) 세련된 풀이

package stackqueue.ch05_2;

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

//객체로 만들어서 비교
class Person {
//implements Comparable<Person>{
	public int id, priority;

	Person(int id, int priority) {
		this.id = id;
		this.priority = priority;
	}
//	@Override
//	public int compareTo(Person o) {
//		if(o.priority==this.priority) return o.id-this.id;
//		else
//			return o.priority-this.priority;
//	}
}

public class Stackqueue08_2 {
	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()) {
			Person tmp = q.peek();
			for (Person x : q) {
				if (tmp.priority < x.priority) {
					q.offer(q.poll());
					tmp = null;
					break;
				}
			}
			if (tmp != null) {
				q.poll();
				answer++;
				if (tmp.id == m)
					return answer;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Stackqueue08_2 T = new Stackqueue08_2();
		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));
	}

}
728x90
반응형
저작자표시 비영리

'Java > Java' 카테고리의 다른 글

[리뷰] 해결 못한 알고리즘 다시 풀기 -5  (0) 2022.08.22
[리뷰] 해결 못한 알고리즘 다시 풀기 -4  (0) 2022.07.08
[리뷰] 정렬 / 스케줄 정리  (0) 2022.07.08
[Java] 예제로 공부하는 Java 100 문제 풀이  (0) 2021.06.17
[Java] 1. 개발 환경 구축과 자바 실행  (0) 2021.06.17

'Java/Java' Related Articles

티스토리툴바