REAL 복습 (2)

4/7일자

1. 암호 만들기 - 백준 1759 (Backtracking)

   :timer_clock: 10:46 - 11:22 (32min)

   package Backtracking;
      
   import java.util.*;
   public class back_암호만들기 {
   	static int n;
   	static int m;
   	static LinkedList<String> arr;
   	static LinkedList<String> list;
   	static LinkedList<String> result;
      	
   	public static int vo(String s) {
   		int num = 0;
   		String v = "aeiou";
   		for(int i=0; i<s.length(); i++) {
   			if(v.contains(String.valueOf(s.charAt(i))))
   					num++;
   		}
   		return num;
   	}
      	
   	//mCn
   	public static void Combination(int num) {
   		if(num == n) {
   			String a = "";
   			for(String s : result) {
   				a +=s;
   			}
   			int numb=vo(a);
   			if(numb>=1 && n-numb>=2)
   				list.add(a);
      				
   			return;
   		}
   		else {
   			for(int i=0; i<arr.size(); i++) {
   				if(result.contains(arr.get(i)))
   					continue;
   				//result가 empty가 아닐때!!
   				if(!result.isEmpty() && i<=arr.indexOf((result.getLast())))
   					continue;
      				
   				result.add(arr.get(i));
   				Combination(num+1);
   				result.removeLast();
   			}
   		}
   	}
      	
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		n = sc.nextInt();
   		m = sc.nextInt();
   		sc.nextLine();
      		
   		list = new LinkedList<>();
   		result = new LinkedList<>();
   		arr = new LinkedList<>();
      		
   		String s[] = sc.nextLine().split(" ");
      		
   		for(int i=0; i<m; i++) 
   			arr.add(s[i]);
      		
   		//미리 정렬한다! (조합으로 풀면 정렬순서가 섞일일이 없다)
   		arr.sort(null);
   		//mCn으로 구할 수 있는 string 전부 구한다
   		Combination(0);
   		//다 구하면  1.최소한개의 모음 2.최소 두개의 자음으로 구성인지
      		
   		for(int i=0; i<list.size(); i++)
   			System.out.println(list.get(i));
   	}
   }
      
   

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

1. 덩치 - 백준 1768 (BruteForce)

   ⏲ 11:32 - 11:42 (10min)

   package bruteforce;
      
   import java.util.*;
      
   public class beak_덩치 {
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
   		int n = sc.nextInt();
      		
   		int arr[][] = new int[n][2];
   		for(int i=0 ;i<n; i++) {
   			arr[i][0] = sc.nextInt();
   			arr[i][1] = sc.nextInt();
   		}
      		
   		int d[] = new int[n];
      		
   		for(int i=0; i<n; i++) {
   			for(int j=0; j<n; j++) {
   				if( i == j)
   					continue;
   				if(arr[i][0]<arr[j][0] && arr[i][1] < arr[j][1])
   					d[i]++;	
   			}
   		}
      		
   		for(int i=0; i<d.length; i++)
   			System.out.print((d[i]+1) + " ");
   	}
      	
   }
      
   

   • 생각보다 문제푸는 법이 곰방 생각남

2. 보물 - 백준 1026 (Sort)

   ⏲ 12:00 - 12:05 (5min)

   package Sort;
      
   import java.util.*;
   public class beak_re_보물 {
      
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		int n = sc.nextInt();
      		
   		int a[] = new int[n];
   		int b[] = new int[n];
      		
   		for(int i=0; i<n; i++) {
   			a[i] = sc.nextInt();
   		}
   		for(int i=0; i<n; i++) {
   			b[i] = sc.nextInt();
   		}
      		
   		Arrays.sort(a);
   		Arrays.sort(b);
      		
   		int answer = 0;
   		for(int i=0; i<n; i++) {
   			answer += a[i] * b[n-i];
   		}
      		
   		System.out.println(answer);
   	}
   }
      
   

   • 이것도! 쉽게 풀어야하는 문제

3. 짝지어 제거하기 - 백준 1026 (Sort)

   ⏲ 12:10 - 12:20 (10min)

   package Stack_Queue;
      
   import java.util.*;
   public class prog_짝지어제거하기 {
      
   	public int solution(String s) {
   		int answer = 0;
      		
   		Stack<Character> stk = new Stack<>();
      		
   		for(int i= s.length()-1; i>=0; i--) {
   			char c = s.charAt(i);
   			if(!stk.isEmpty() && stk.peek() == c)
   				stk.pop();
   			else
   				stk.push(c);
   		}
      		
   		if(stk.isEmpty())
   			answer = 1;
      		
   		return answer;
   	}
   }
      
   

   • 한 삼분 버벅이다가, 금방 풀음

4. 여행 경로 - 프로그래머스 43164 (Dfs)

   ⏲ 12:30 - 12:50 (20min)

   package Dfs_Bfs;
      
   import java.util.*;
      
   public class prog_re_여행경로 {
   	static String tic[][];
   	static int n;
   	static LinkedList<String> list;
      	
   	static public void dfs(int idx, boolean visited[], int num, String s) {
   		String next = tic[idx][1];
   		s = s + next + ",";
      		
   		if(num == n) {
   			list.add(s);
   			return;
   		}
      
   		for(int i=0; i<tic.length; i++) {
   			if(tic[i][0].equals(next) && !visited[i]) {
                   visited[i] = true;
   				dfs(i,visited,num+1, s);
   				//까먹지 말기
                   visited[i] = false;
   			}
   		}
      		
   	}
      	
   	static public String[] solution(String[][] tickets) {
   		tic = tickets;
   		n = tickets.length;
      		
   		list = new LinkedList<>();
      		
   		for(int i=0; i<tickets.length; i++) {
   			boolean visited[] = new boolean[tickets.length];
   			if(tickets[i][0].equals("ICN")) {
   				visited[i] = true;
   				dfs(i ,visited,1, "ICN,");
   			}
   		}
              
   		list.sort(null);
              
   		String s[] = list.get(0).split(",");
      		
   		return s;
   	}
      	
   }
      
   

   • ”,” 찍어 주는거 잊지말자!

5. 욕심쟁이 판다 - 백준 1937 (DP)

   ⏲ 13:13 - 12:53 (40min)

   package DP;
      
   import java.util.*;
   public class beak_re_욕심쟁이판다 {
      
   	static int maze[][];
   	static int root[][];
   	static int n;
   	static int dx[] = {0,0,1,-1};
   	static int dy[] = {1,-1,0,0};
      	
   	static public int backt(int x, int y) {
   		if(root[x][y] !=0)
   			return root[x][y];
   		//그게 아니라면 일단 1 넣어 줌
   		root[x][y] = 1;
      		
   		for(int i=0; i<4; i++) {
   			int nx = x+dx[i];
   			int ny = y+dy[i];
      			
   			if(nx>=0 && nx<n && ny>=0 && ny<n) {
   				if(maze[x][y] <maze[nx][ny]) {
   					root[x][y] = Math.max(backt(nx,ny) + 1, root[x][y]);
   				}
   			}
   		}
      		
   		return root[x][y];
   	}
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		n = sc.nextInt();
      		
   		maze = new int[n][n];
   		root = new int[n][n];
      		
   		for(int i=0; i<n; i++) {
   			for(int j=0; j<n; j++) {
   				maze[i][j] = sc.nextInt();
   			}
   		}
      		
   		for(int i=0; i<n; i++) {
   			for(int j=0; j<n; j++) {
   				if(root[i][j] ==0)
   					backt(i,j);
   			}
   		}
      		
   		int max = 0;
      		
   		for(int i=0; i<n; i++) {
   			for(int j=0; j<n; j++) {
   				max = Math.max(max, root[i][j]);
   			}
   		}
      		
   		System.out.println(max);
   	}
   }
      
   

   • 오 못풀 줄 알았는데 풀었따… 싱기방기..
   • 메모이제이션으로 풀었따!