REAL 복습 (1) 괄호의 값/스택수열/다리를 지나는 트럭/디스크 컨트롤러

2020-04-20

REAL 복습 (1)

4/16일자

괄호의 값 - 백준 2504 (Stack)

:timer_clock: 6:38 - 7:23 (46min)

package Stack;
   
import java.util.*;
   
public class beak_괄호의값 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
   	
		String s = sc.nextLine();
		Stack<Character> stk = new Stack();
   		
		int sum = 0;	int divider =1;		boolean b = false;
   		
		for(int i=0; i<s.length(); i++) {
			char c = s.charAt(i);
   			
			switch(c) {
			case '(': // 무조건 stk에 (만 넣는다
				stk.add('(');
				divider = divider*2;
				break;
   				
			case '[': // 무조건 stk에 [만 넣는다
				stk.add('[');
				divider = divider*3;
				break;
   				
			case ')': //stk에는 (나 ]만 있으므로, )일 때
				if(stk.isEmpty() || stk.peek() == '[') {//stk에서는 (를 팝해야함
					b = true;
					break;
				}
   				
				if(s.charAt(i-1) == '(') // 앞이 (면 계산해주는거니까 sum에 넣고
					sum += divider;
   				
				//다 수행했다면 
				stk.pop();
				divider /= 2;
				break;
   				
			case ']':
				//무조건 얘를 먼저 수행해줘야 한다
				if(stk.isEmpty() || stk.peek() == '(') {
					b = true;
					break;
				}
   				
				if(s.charAt(i-1) == '[')
					sum += divider;
   				
				//다 수행했다면 
				stk.pop();
				divider /= 3;
				break;
			}
   			
			if(b == true)
				break;
   			
		}//for
   		
		//어쨌든 나오면 sum에 똥값이 들어있던, 정상값이 들어있던 한다!
		//중요한건 stk가 empty인지 아닌지!
		if(stk.isEmpty() && b == false)
			System.out.println(sum);
		else
			System.out.println(0);
	}
}
   

풀기는 금방 풀었는데, 런타임에러가 계속 났다.

이유는 ], ) 조건에서 if(empty

peek() != ‘’) break해주고 나왔어야했는데, sum 계산부터하니까 다른 테스트케이스에서 걸리는 부분이 있었던 것 같다!

이번에는 boolean을 이용해서 아닌 부분이 나타났을때 바로 break걸고 나오고
틀렸는데 empty일때와, 정답일때 empty를 구분하기 위해서, empty&& b==false를 걸어줬다

4/14일자

스택수열 - 백준 1874 (Stack)

⏲ 7:28 - 7:42 (14min)

package Stack;
   
import java.util.*;
public class beak_스택수열 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
   		
		Stack<Integer> stk = new Stack();
		LinkedList<Integer> qu = new LinkedList();
   		
		int n = sc.nextInt();
		StringBuilder sb = new StringBuilder();
   		
		for(int i=0; i<n; i++)
			qu.add(sc.nextInt());
   		
		int x = 1;
		while(x <= n) {
			//무조건 push하고
			stk.push(x);
			sb.append("+\n");
   			
			//같은동안 계속 pop
			while(!stk.isEmpty() && qu.peek().intValue() == stk.peek().intValue()) {
				stk.pop();
				qu.poll();
				sb.append("-\n");
			}
   			
			x++;
		}
   		
		if(stk.isEmpty())
			System.out.println(sb.toString());
		else
			System.out.println("NO");
   		
	}
}

오… intValue() 해주는거 까먹어서 완전 시간 날릴뻔했어 휴..
qu에는 원하는 값이 들어가있고 stk는 무조건 증가시키고 같은동안은 pop

다리를 지나는 트럭 -프로그래머스 42583 (Stack)

⏲ 7:45 -8:03 (18min)

package Stack;
   
import java.util.*;
public class prog_다리를지나는트럭 {
	static class Truck{
		int wei;
		int step;
   		
		Truck(int wei, int step){
			this.wei = wei;
			this.step = step;
		}
	}
   	
	 static public int solution(int bridge_length, int weight, int[] truck_weights) {
		 int sec = 0;
   		 
		 LinkedList<Truck> trk = new LinkedList<>();
   		 
		 //일단 첫번째거 적재
		 trk.add(new Truck(truck_weights[0], 1));
		 sec = 1;
		 int idx = 1;
		 int size = truck_weights.length-1;
		 while(size != -1) {
			 if(!trk.isEmpty()) {
				 //무조건 있는애들 다 옮겨주기
				 for(int i=0; i<trk.size(); i++) {
					 trk.set(i, new Truck(trk.get(i).wei, trk.get(i).step+1));
				 }
				 //****이부분 자꾸 빼먹지 말기!!
				 if(idx<truck_weights.length) {
					 //들어올 수 있는지 확인
					 int we = 0;
					 for(int i=0; i<trk.size(); i++) {
						 we += trk.get(i).wei;					 
					 }
   					 
					 if(we + truck_weights[idx] <=weight) {
						 trk.add(new Truck(truck_weights[idx], 1));
						 idx++;
					 }
				 }
				 //***
   				 
				 //나갈 수 있는지 확인
				 if(trk.get(0).step == bridge_length) {
					 trk.remove();
					 size--;
				 }
			 }
			 else {//적재 고고링
				 trk.add(new Truck(truck_weights[idx], 1));
				 idx++;
			 }
   			 
			 sec++;//초 증가
		 }
   		 
		 return sec+1;
	 }  
}

마지막에 return sec+1; 해주는 거
trk에 다음게 있으면 적재가능한지 확인할 때 (idx가 len을 넘어가지는 않는지!!!!!!!)
size는 0번째까지 돌다가, 마지막에 -1이 되면 종료된다
아니… 기억날 때 세번 째 푸는건데 20분 걸리면 어떡..해…!

디스크 컨트롤러 -프로그래머스 42627 (Heap)

⏲ 8:06 - 8:46 (40min)

package Heap;
   
import java.util.*;
public class prog_디스크컨트롤러 {
	//comparator아니고 Comparable!!!
	static class Disk implements Comparable<Disk>{
		int sec;
		int job;
   		
		Disk(int sec, int job){
			this.sec = sec;
			this.job = job;
		}
		@Override
		public int compareTo(Disk d) {
			//job으로 오름차순!!!
			if(this.job == d.job)
					return this.sec- d.sec;
			else 
				return this.job - d.job;
		}
	}
   	
    static public int solution(int[][] jobs) {
    	int answer = 0;
   
    	PriorityQueue<Disk> pq = new PriorityQueue<>();
    	LinkedList<Disk> list = new LinkedList<>();
   
    	for(int i=0; i<jobs.length; i++)
    		pq.add(new Disk(jobs[i][0], jobs[i][1]));
   
    	for(int i=0; i<jobs.length; i++) {
    		list.add(pq.poll());
    	}
       	
    	int time = 0;
       	
        while(!list.isEmpty()) {
        	for(int i=0; i<list.size(); i++) {
        		if(time>= list.get(i).sec) {
        			time += list.get(i).job;
        			answer += time- list.get(i).sec; //종료시각은 끝난시간 - 시작시간
        			list.remove(i);
        			break; // 한번하면 끝내기
        		}
        		//시작시간이 다  time보다 크다면 -> disk에 안들어온 것이니 지금 시작 불가능
        		//끝까지 다 봤다면
        		if(i == list.size()-1)
        			time++;
        	}
        }
       	
    	return answer/jobs.length;
    }
}
   

PQ가 우선수위 큐이고 -> Disk클래스에 우선순위를 지정해놨기때문에 일반 list에는 우선순위가 적용되지않고 PQ를 사용해야하는 것 같다!!!

그래서 PQ에 넣고 정렬된 것을 list에 넣어준다

    	PriorityQueue<Disk> ll = new PriorityQueue<>();
    	List<Disk> pq = new LinkedList<>();

List가 비지 않은 동안 돌리면서
time보다 sec가 크거나 같지않으면 돌릴 수 있으니까 -> 계산해주고 제거하고 break

끝까지봤는데 전부 time보다 크다면 time++ 해준다!

        while(!list.isEmpty()) {
        	for(int i=0; i<list.size(); i++) {
        		if(time>= list.get(i).sec) {
        			time += list.get(i).job;
        			answer += time- list.get(i).sec;
        			list.remove(i);
        			break;
        		}
                     
        		if(i == list.size()-1)
        			time++;
        	}
        }

 [프로그래머스] N-Queen (java) Backtracking REAL 복습 (2) 암호 만들기/덩치/보물/짝지어 제거하기/여행경로/욕심쟁이 판다 