import java.io.*;
import java.util.*;
public class Main {
public String solution(String s){
String ans = "YES";
Stack<Character> stack = new Stack<>();
for(char x : s.toCharArray()){
if(x == '(') stack.push(x);
else {
if(stack.empty()) return "NO";
stack.pop();
}
}
if(!stack.isEmpty()) return "NO";
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
System.out.println(T.solution("()(())()"));
}
}
- python
def solution(s):
answer="YES"
stack=[]
for x in s:
if x=='(':
stack.append(x)
else:
if len(stack)==0:
return "NO"
stack.pop()
if len(stack)>0:
return "NO"
return answer
print(solution("(()(()))(()"))
2) 괄호문자제거
- java
import java.io.*;
import java.util.*;
public class Main {
public String solution(String s){
String ans = "";
Stack<Character> stack = new Stack<>();
for(char x : s.toCharArray()){
if(x == '(') stack.push(x);
else if(x == ')') stack.pop();
else if(stack.empty()) ans += x;
}
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
System.out.println(T.solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"));
}
}
- python
def solution(s):
answer=""
stack=[]
for x in s:
if x==')':
while stack.pop()!='(':
continue
else:
stack.append(x)
answer="".join(stack)
return answer
print(solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"))
3) 충돌하는 수열
- java
package ch03;
import java.io.*;
import java.util.*;
public class 충돌하는수열 {
public ArrayList<Integer> solution(int[] arr){
ArrayList<Integer> ans = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
for(int x : arr){
if(x > 0) stack.push(x);
else {
if(stack.empty() || stack.peek() < 0) stack.push(x);
else {
boolean flag = false;
while(!stack.empty() && stack.peek() > 0){
int left = stack.pop(); // 당연히 양수
if(Math.abs(x) > left) flag = true;
else if(Math.abs(x) == left) {
flag = false;
break;
}
}
if(flag) stack.push(x);
}
}
}
for(int x : stack) ans.add(x);
return ans;
}
public static void main(String[] args) throws IOException {
충돌하는수열 T = new 충돌하는수열();
int[] arr = new int[]{3, 5, -2, -5};
int[] arr1 = new int[]{-2, -1, -3, 1, 3};
int[] arr2 = new int[]{-2, -1, 2, 1, -3, 2};
System.out.println(T.solution(arr2));
}
}
- python
def solution(nums):
stack=[]
for x in nums:
if x>0:
stack.append(x)
else:
if not stack or stack[-1]<0:
stack.append(x)
else:
flag=0
while stack and stack[-1]>0:
left=stack.pop()
if abs(x)>left:
flag=1
elif abs(x)==left:
flag=0
break
else:
stack.append(left)
flag=0
break
if flag==1:
stack.append(x)
return stack
print(solution([3, 5, -2, -5]))
print(solution([-2, -1, -3, 1, 3]))
print(solution([-2, -1, 2, 1, -3, 2]))
4) 쇠막대기
- java
import java.io.*;
import java.util.*;
public class Main {
public int solution(String s){
int ans = 0;
Stack<Character> stack = new Stack<>();
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == '(') stack.push('(');
else {
stack.pop();
if(s.charAt(i-1) == '(') ans += stack.size();
else ans++;
}
}
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
System.out.println(T.solution("()(((()())(())()))(())"));
}
}
- python
import sys
sys.stdin=open("input.txt", "r")
s=input()
stack=[]
cnt=0
for i in range(len(s)):
if s[i]=='(':
stack.append(s[i])
else:
stack.pop()
if s[i-1]=='(':
cnt+=len(stack)
else:
cnt+=1
print(cnt)
5) 가장 큰 수
- java
import java.io.*;
import java.util.*;
public class Main {
public String solution(String s, int n){
String ans = "";
Stack<Integer> stack = new Stack<>(); // 큰 숫자 -> 내림차순의 수여야 함
for(int x : s.toCharArray()){
// 나보다 작은 애들은 빼기 ex. push(7) -> 5, 2 pop
while (!stack.empty() && n > 0 && stack.peek() < (x - 48)) {
stack.pop();
n--;
}
stack.push(x-48);
}
while(n > 0){
stack.pop();
n--;
}
for(int x : stack) ans += x;
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
System.out.println(T.solution("5276823", 3));
}
}
- python
import sys
sys.stdin=open("input.txt", "rt")
num, m=map(int, input().split())
num=list(map(int, str(num)))
stack=[]
for x in num:
while stack and m>0 and stack[-1]<x:
stack.pop()
m-=1
stack.append(x)
if m!=0:
stack=stack[:-m]
res=''.join(map(str, stack))
print(res)
6) 공주 구하기
- java
import java.io.*;
import java.util.*;
public class Main {
public int solution(int n, int k){
int ans = 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) ans = q.poll();
}
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
System.out.println(T.solution(8, 3));
}
}
- python
import collections
def solution(n, k):
tmp=range(1, n+1)
dQ=collections.deque(tmp)
while dQ:
for _ in range(k-1):
dQ.append(dQ.popleft())
dQ.popleft()
if len(dQ)==1:
return dQ.popleft()
print(solution(8, 3))
7) 교육과정설계
- java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public ArrayList<String> solution(String need, String[] plans){
ArrayList<String> ans = new ArrayList<>();
String result = "YES";
for(String p : plans){
Queue<Character> q = new LinkedList<>();
boolean flag = true;
for(char x : need.toCharArray()) q.offer(x);
for(char x : p.toCharArray()){
if(q.contains(x) && x != q.poll()){
result = "NO";
flag = false;
break;
}
}
if(flag && !q.isEmpty()) result = "NO";
if(!flag && q.isEmpty()) result = "YES";
ans.add(result);
}
return ans;
}
public static void main(String[] args) throws IOException {
main T = new main();
String need = "CBA";
String[] plans = {"CBDAGE", "FGCDAB", "CTSBDEA"};
System.out.println(T.solution(need, plans));
}
}
- python
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
need=input()
n=int(input())
for i in range(n):
plan=input()
dq=deque(need)
for x in plan:
if x in dq:
if x!=dq.popleft():
print("#%d NO" %(i+1))
break
else:
if len(dq)==0:
print("#%d YES" %(i+1))
else:
print("#%d NO" %(i+1))
8) 최소힙
- java
package ch03;
import java.io.*;
import java.util.*;
public class Main {
public ArrayList<Integer> solution(int[] nums){
ArrayList<Integer> ans = new ArrayList<>();
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int x : nums){
if(x == 0) {
if(q.isEmpty()) ans.add(-1);
else ans.add(q.poll());
} else q.offer(x);
}
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
int[] arr = new int[]{5,3,6,0,5,0,2,4,0};
System.out.println(T.solution(arr));
}
}
- python
import collections, heapq
def solution(nums):
answer=[]
minH=[]
for x in nums:
if x==0:
if len(minH)==0:
answer.append(-1)
else:
answer.append(heapq.heappop(minH))
else:
heapq.heappush(minH, x)
return answer
print(solution([5, 3, 6, 0, 5, 0, 2, 4, 0]))
9) 최대힙
- java
package ch03;
import java.io.*;
import java.util.*;
public class Main {
public ArrayList<Integer> solution(int[] nums){
ArrayList<Integer> ans = new ArrayList<>();
// Collections.reverseOrder() -> 최대힙
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
for(int x : nums){
if(x == 0) {
if(q.isEmpty()) ans.add(-1);
else ans.add(q.poll());
} else q.offer(x);
}
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
int[] arr = new int[]{5,3,6,0,5,0,2,4,0};
System.out.println(T.solution(arr));
}
}
- python
import collections, heapq
def solution(nums):
answer=[]
minH=[]
for x in nums:
if x==0:
if len(minH)==0:
answer.append(-1)
else:
answer.append(-heapq.heappop(minH))
else:
heapq.heappush(minH, -x)
return answer
print(solution([5, 3, 6, 0, 5, 0, 2, 4, 0]))
10) 마지막 남은 수
- java
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public int solution(int[] nums){
int ans = 0;
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
for(int x : nums) q.offer(x);
while(q.size()>1){
int a = q.poll();
int b = q.poll();
if(a != b) q.offer(a-b);
}
if(!q.isEmpty()) ans = q.poll();
return ans;
}
public static void main(String[] args) throws IOException {
Main T = new Main();
int[] arr = new int[]{5,3,6,0,5,0,2,4,0};
int[] arr1 = new int[]{7,6,3,2,4,5,1};
System.out.println(T.solution(arr));
}
}
- python
import heapq
def solution(nums):
answer=0
maxH=[]
for x in nums:
heapq.heappush(maxH, -x)
while(len(maxH)>1):
a=-heapq.heappop(maxH)
b=-heapq.heappop(maxH)
if a!=b:
heapq.heappush(maxH, -(a-b))
if len(maxH)>0:
answer=heapq.heappop(maxH)
return answer
print(solution([5, 2, 4, 3, 1]))#1
print(solution([7, 6, 3, 2, 4, 5, 1])) #0
