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++; } }
-
