복습 5

3.6부터 앞으로

1. 좋은 단어 (Stack) -> 문제.. 헷갈리지말자

2. 퇴사 (DP)

   1. n일까지도 일할 수 있다 + (n+1)과 n일을 비교하므로 배열은 p[n+2], t[n+2], dp[n+2]로 진행
   2. 또 dp[day]가 day일이후로 가질 수 있는 최대값이면서, 1일차값이 p[1]과 dp[day+1]로 진행된다면
   	끝에서부터 dp[막날 이후로 가질수있는 값], dp[막날 전날 가질 수 있는값].. 으로 진행해야한다.
   3. 따라서 for(i=n; i>0; i--) 1일부터 시작하게 했으니까 i>0 이어야한다
   4. day는 현재 내 날짜 i + 상담기간 t[i] 이며, 
   	day가 <=n 날짜 안에 끝난다면
   	dp[i] = max(p[i]+dp[day], dp[i+1]); 중 큰 값을 넣고
   	day가 >n 이라면
   	dp[i] = dp[i+1]; 뒤에서부터 오니까 다음날이 가질 수 있는 최대값이 오늘 가질 수 있는 최대값!!
      	
   5. 따라서 dp[1]에 가질 수 있는 최대의 값이 담겨있다
   

3. 가장 긴 펠린드롬 (String)

   스터디원이 푼 것 처럼, 모든 나올 수 있는 숫자의 조합으로 나눠서 계산했다. 코드도 짧아지고 답은 정답인데 효율성에서 0점 맞음…(?)

   import java.util.*;
      
   public class Review {
   	boolean palen(String s) {
   		int j=s.length()-1; //끝부터 시작
      		
   		for(int i=0; i<s.length()/2; i++,j--) {//i는 0부터 j는 끝부터 다가오다 만난다
   			if(s.charAt(i) != s.charAt(j))
   				return false; //아닐때만 잡아내면 되니까
   		}
      		
   		return true; // 안걸리고 나왔으면 true
   	}
      	
       public int solution(String s) {
       	int answer = 0;
       	for(int i=1; i<=s.length(); i++) {
       		for(int j=0; j<s.length(); j++) {
       			if(j+i <=s.length()) {
       				String a = s.substring(j, j+i);
       				System.out.println(a);
       				if(palen(a) == true)
       					answer = Math.max(answer, a.length());
       			}
       		}//in for - 0부터 돌려보는 갯수까지 쪼개봄 (0~5)
       	}//out for - 돌려보는 갯수 (1~5)
          	
       	return answer;
       }
   }
   

4. 문자열 압축 (String)

   오우… 위의 문제랑 비슷해서 비슷하게 풀었는데 다른점은
   

   1) 위에 문제는 j+i 끊어지는 부분에서 멈춘다는 것
   

   2) 이 문제는 j+i 끊어지는 부분에서 멈춘 후에, 그 뒷부분도 찾아내야 한다는 점이었다

   import java.util.*;
      
   //28min
   public class Review {
      	
   	//작은 문자열의 사이즈로
   	static int solution(String s) {
   		int answer=2500;
      		
   		for(int i=1; i<=s.length(); i++) {
   			//일단 하나 넣고 시작하기
   			String answer_s = "";
   			String temp = s.substring(0, i);
   			int num = 1;
   			int idx = 0; boolean chk = false;
      			
   			for(int j=i; j<s.length(); j = j+i) {
   				if(j+i<=s.length()) {
   					if(temp.equals(s.substring(j, j+i))) { // 음... 문자열끼리 비교할때는 == 안쓰는거 잊지말자...
   						num++;
   					}
   					else {
   						if(num == 1)
   							answer_s += temp;
   						else
   							answer_s += num+temp;
   						num = 1;
   					}
   					temp = s.substring(j, j+i); // if 든 else 든 무조건 temp에는 다음 값 넣어줌
   				}//배열 size안에 들어온다는 조건
   				else {
   					chk = true;
   					idx = j;
   				}
   			}//in for
      			
   			//비교는 이미 했고, 못들어간거 넣어주기
   			if(num == 1)
   				answer_s += temp;
   			else
   				answer_s += num + temp;
      			
   			if(chk == true)// 끝까지 도달못했으면
   				answer_s += s.substring(idx, s.length());
      			
   			System.out.println(answer_s);
      			
   			answer = Math.min(answer, answer_s.length());
   		}//out for
      		
      		
   		return answer;
   	}
          
       public static void main(String[] args) {
      
   		System.out.println(solution("abcabcabcabcdededededede"));
          	
   	}
   }
   

5. 경로찾기 (BFS)

   Pos 클래스 필요없고, j행만 가지고 들어가기때문에 큐는 Integer로 설정해준다! 기억해놓기!
   

   또한, 큐가 무한루프를 돌지 않기위해서 어떤 조건일때 add 해주는지도 잘 생각해야한다!

   import java.util.*;
      
   public class Review {
      	
   	//30min
       public static void main(String[] args) {
          	
       	Scanner sc = new Scanner(System.in);
          	
       	int n = sc.nextInt();
          	
       	int arr[][] = new int[n][n];
          	
       	for(int i=0; i<n; i++) {
       		for(int j=0;j<n; j++)
       			arr[i][j] = sc.nextInt();
       	}
          	
       	Queue<Integer> qu = new LinkedList<>();
          	
       	for(int i=0; i<n; i++) {// 인접행렬이니까 0-n행까지만 가보면 된다
       		for(int j=0; j<n; j++) {//i행 쫙 돌기
       			if(arr[i][j] == 1) 
       				qu.add(j);
       		}
          			
   			while(!qu.isEmpty()) {//j행에 방문할 수 있는데까지 다 방문하면서 1로만들어주고 나온다.
   				int nextj = qu.poll();
      				
   				arr[i][nextj] = 1; //i행의 j는 갈수있으니까 1로 만들어줌
      				
   				for(int k=0; k<n; k++) {
   					if(arr[nextj][k] == 1 && arr[i][k] !=1) {
   						//arr[i][k]!=1이라는 뜻은 전행의 1이 있는곳은 전부 안가겠다는 뜻! qu에 안넣겠다는 뜻!
   						qu.add(k);
   					}
   				}
   			}//while
                  
               //그렇게 while 돌고나오면 다음 i행으로 진행한다!
       	}//out for
          	
          	
       	for(int i=0;i<n;i++) {
       		for(int j=0; j<n; j++)
       			System.out.print(arr[i][j] + " ");
       		System.out.println();
       	}
   	}
   }
   

6. RGB거리 (DP)

7. Z (Recursion)

   면이 아닌 점이라고 생각하면 쉽게 풀 수 있다.
   

   또한, 기저조건에서 return 을 해주는것과 멈출 수 없다면 그냥 거기서 출력해주는 것도 좋은 방법!

   import java.util.*;
      
   public class Review {
   	//10min
   	static int answer = 0;
      	
   	static void go(int m, int i, int j, int x, int y) {
   		if(m == 1) {//기저조건
   			if(i==x && j==y)
   				System.out.println(answer);
      			
   			answer++;
   			return;
   		}
      
   		int h = m/2;
      		
   		go(h, i, j, x, y);
   		go(h, i, j+h, x, y);
   		go(h, i+h, j, x, y);
   		go(h, i+h, j+h, x, y);
      
   	}
      	
       public static void main(String[] args) {
       	Scanner sc = new Scanner(System.in);
          	
       	int n = sc.nextInt();
       	//점이라고 생각
       	int m = (int)Math.pow(2, n); // 한면만 가지고 들어가면 나머지는 half 옮기면서 알 수 있다
      
       	int x = sc.nextInt();
       	int y = sc.nextInt();
          	
       	go(m, 0, 0, x, y);
          	
   	}
   }
   

8. 잃어버린 괄호 (Greedy)

   첫 시작은 무조건 +로 시작하니까, - 시작 전까지오는 s[0]은 전부 더해주면 된다
   

   또, 뒤의 -로 쪼개져있는 배열들은 뒤에 +가 있으면 전부 괄호로 묶어서 더해준다는 개념이니까

   -가나오는 배열마다 안에있는 애들을 전부 더해서 -처리해주면 된다.

   import java.util.*;
      
   public class Review {
      	
       public static void main(String[] args) {
       	Scanner sc = new Scanner(System.in);
          	
       	String a = sc.nextLine();
          	
       	String a_split[] = a.split("-"); //-로 나누기
          	
       	String first_split[] = a_split[0].split("\\+"); //첫 -의 앞부분 +들은 전부 더해준다
          	
       	int f = 0;
       	for(int i=0; i<first_split.length; i++)
       		f += Integer.parseInt(first_split[i]);
          	
       	//나머지 -로 쪼개진 부분들은 전부 더해준다
       	int l =0;
       	for(int i=1; i<a_split.length; i++) {
       		//+가 있는 부분은 제거하고 숫자만 더해준다
       		String s[] = a_split[i].split("\\+");
          		
       		for(int j=0;j<s.length; j++)
       			l += Integer.parseInt(s[j]);
       	}
          	
       	System.out.println(f-l);
          	
   	}
   }
   

9. 0 만들기 (Greedy)

   실패!!!!!!!!!!! 비슷하게 따라가다가 결국 조건에서 헤맸다… 으ㅏ아

   import java.util.*;
      
   public class Review {
      	
   	static int target = 0;
      	
   	static void rec(int sum, int sign, int num, int increase, String a) {
   		if(target == increase) {//기저조건
      			
   			sum = sum + sign*num;
   			if(sum == 0)
   				System.out.println(a);
   			return;
   		}
      		
   		rec(sum,  sign, num*10 + (increase+1), increase+1, a+ " " + String.valueOf(increase+1));
   		rec(sum + (sign*num),  1, increase+1,	  increase+1, a + "+" + String.valueOf(increase+1));
   		rec(sum + (sign*num), -1, increase+1, increase+1, a + "-" + String.valueOf(increase+1));
      		
   	}
      	
       public static void main(String[] args) {
       	Scanner sc = new Scanner(System.in);
          	
       	int n = sc.nextInt();
          	
       	for(int i=0; i<n; i++) {
       		target = sc.nextInt();
       		String a = "1";
       		//sum, 부등호 , 초기값, 하나씩 증가해서 n 도달하는 값, 1넣고 출발 
          		
       		rec(0,1, 1, 1, a);
       		System.out.println();
       	}
   	}
          
   }