REAL 복습 (3)

4/8일자, 4/18일자

1. 빙산 - 백준 1759 (Bfs)

   :timer_clock: 10:55 - 12:00 (1h)

   package Dfs_Bfs;
      
   import java.util.*;
      
   public class beak_빙산_re {
   	static class Pos{
   		int x;
   		int y;
   		Pos(int x, int y){
   			this.x = x;
   			this.y = y;
   		}
   	}
      	
   	static int arr[][];
   	static boolean visited[][];
   	static int n;
   	static int m;
   	static LinkedList<Pos> tozero;
   	static LinkedList<Pos> notzero;
      	
   	static int dx[] = {0,0,1,-1};
   	static int dy[] = {1,-1,0,0};
      	
   	public static boolean melt() {
   		boolean b = false;
      		
   		int a_size = notzero.size();
   		for(int i=0; i<a_size; i++) {
   			//사방 보면서 0이되면 tozero에 넣고, 0보다 크면 값 바꿔주고 위치 다시 넣고
   			Pos p = notzero.poll();
   			int cnt = 0;
   			for(int j=0; j<4; j++) {
   				int nx = p.x + dx[j];
   				int ny = p.y + dy[j];
      				
   				if(nx>=0 && nx<n && ny>=0 && ny<m && arr[nx][ny] == 0)
   					cnt++;
   			}
      			
   			if(arr[p.x][p.y] - cnt > 0) {
   				arr[p.x][p.y] -= cnt;
   				notzero.add(new Pos(p.x, p.y));
   				b = true;
   			}
   			else
   				tozero.add(new Pos(p.x,p.y));
   		}
      		
   		int b_size = tozero.size();
   		for(int i=0; i<b_size; i++) {
   			Pos p = tozero.poll();
   			arr[p.x][p.y] = 0;
   			visited[p.x][p.y] = false;
   		}
      		
   		return b; // false라는건 0만 있다는 뜻
   	}
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		n = sc.nextInt();
   		m = sc.nextInt();
      		
   		arr= new int[n][m];
      		
   		tozero = new LinkedList<>();
   		notzero = new LinkedList<>();
   		visited= new boolean [n][m];
      		
   		sc.nextLine();
   		for(int i=0; i<n; i++) {
   			String s[] = sc.nextLine().split(" ");
   			for(int j=0; j<m; j++) {
   				int x = Integer.parseInt(s[j]);
   				arr[i][j] = x;
   				if(x !=0) {
   					notzero.add(new Pos(i,j));
   					visited[i][j] = true;
   				}
   			}
   		}
      
      		
   		int year = 0;
   		while(true) {
      			
   			if(!melt()) {
   				year = 0;
   				break;
   			}
   			//visited
   			boolean ck[][] = new boolean [n][m];
   			for(int i=0; i<n; i++) {
   				for(int j=0; j<m; j++)
   					ck[i][j] = visited[i][j];
   			}
      			
      
   			int size = 0;
   			int c_size = notzero.size();
   			for(int i=0; i<c_size; i++) {
   				Pos p = notzero.get(i);
   				if(ck[p.x][p.y] == true) {
   					size++;
   					Queue<Pos> qu = new LinkedList<>();
   					qu.add(p);
   					ck[p.x][p.y] = false;
   					while(!qu.isEmpty()) {
   						Pos pp = qu.poll();
   						for(int j=0; j<4; j++) {
   							int nx = pp.x + dx[j];
   							int ny = pp.y + dy[j];
      							
   							if(nx>=0 && nx<n && ny>=0 && ny<m && ck[nx][ny] == true) {
   								qu.add(new Pos(nx,ny));
   								ck[nx][ny] = false;
   							}
   						}
   					}
      
   				}
      				
   			}
      			
   			year++;
      			
   			if(size >=2)
   				break;
   		}
      		
   		System.out.println(year);
   	}
   }
      
   

   • 다시 풀어도 시간초과…아….!!!!!!!!!!!!!!!!!!!!1

2. 기타줄 - 백준 (Greedy)

   ⏲ 12:02 - 12:27 (25min)

   package greeedy;
      
   import java.util.*;
      
   public class beak_기타줄_re {
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		int n = sc.nextInt();
   		int m = sc.nextInt();
      
   		int p = Integer.MAX_VALUE;
   		int g = Integer.MAX_VALUE;
      		
   		for(int i=0; i<m; i++) {
   			p = Math.min(p, sc.nextInt());
   			g = Math.min(g, sc.nextInt());
   		}
      		
   		int answer = 0;
   		answer = Math.min(Math.min((n/6 + 1)*p, (n/6)*p + (n%6)*g),n*g); 
      		
   		System.out.println(answer);
   	}
   }
      
   

   • 생각해내는데에 조큼 걸림!
   • 여기서 키포인트는 min 패키지, min 낱개를 일단 구해놓는 것!
   • 1. 패키지로만 전부살건지
     2. 낱개로만 전부 살건지
     3. 패키지로 사고 + 나머지를 낱개로 살건지

3. N-Queen - 백준 (Backtracking)

   ⏲ 12:30 - 12:40 (10min)

   package Backtracking;
      
   import java.util.*;
   public class beak_엔퀸_re {
   	static int n;
   	static int arr[][];
   	static int hang[];
   	static int answer = 0;
      	
   	public static boolean ck(int lev) {
   		for(int i=0; i<lev; i++) {
   			if(hang[i] == hang[lev])
   				return false;
   			if(Math.abs(hang[i] - hang[lev]) == Math.abs(i-lev))
   				return false;
   		}
   		return true;
   	}
      	
   	public static void bt(int lev) {
   		if(lev == n) {
   			answer++;
   			return;
   		}
   		for(int i=0; i<n; i++) {
   			hang[lev] = i; // hang[i] = lev가 아니다! lev행에 i를 다 넣어보는것
      			
   			if(ck(lev))  // lev행 전까지 가보는 것
   				bt(lev+1);
   		}
   	}
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		n = sc.nextInt();
      		
   		arr = new int[n][n];
   		hang = new int[n];
      				
   		bt(0); // 영층부터 가본다
   		System.out.println(answer);
   	}
   }
      
   

   • hang에 뭘 넣어줘야하는지 까먹지 말자! hang[lev] = i를 넣어주는 것!

4/6일자

1. 조이스틱 - 프로그래머스 (Greedy)

   ⏲ 12:42 - 13:02 (20min)

   package greeedy;
      
   public class prog_조이스틱_re {
          
   	static public int solution(String name) {
       	int answer = 0;
      		
       	int big = name.length()-1;
          	
   		for(int i=0; i<name.length(); i++) {
   			char c = name.charAt(i);
       		answer += Math.min('Z'-c+1, c-'A' -1);
          		
       		int next = i+1;
       		while(next<name.length() && name.charAt(next) == 'A')
       			next++;
          		
       		big = Math.min(big , i+i+name.length()-next);
       	}
      		
      		
   		return answer;
       }
          
   	public static void main(String[] args) {
      		
   	}
   }
      
   

   • 제일 많이 도는건 len-1까지이고 그것과 대적할 것은, 돌아서 a위치 전까지 가는걸 확인해보는 것!