package Math;

import java.util.*;

//조합 (중복 x)
public class beak_N과M_2 {

	static int n;
	static int m;
	static StringBuilder sb;
	static LinkedList<Integer> numbers;
	
	public static void comb(int count) {
		if(count == m) {
			for(int i: numbers)
				sb.append(i + " ");
			
			sb.append("\n");	
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(numbers.contains(i+1))
				continue;
			
			if(!numbers.isEmpty() && i<numbers.getLast()) // i가 numbers의 맨 끝 값보다 작을때는 continue 
				continue;
			
			numbers.add(i+1);
			comb(count+1);
			numbers.removeLast();
		}
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		sb = new StringBuilder();
		numbers = new LinkedList<>();
		
		comb(0);
		
		System.out.println(sb.toString());
	}
}


//https://limkydev.tistory.com/186  -> 순열, 중복순열, 조합, 중복조합

package Math;

import java.util.*;

//순열 (중복x)
public class beak_N과M_1 {

	static int n;
	static int m;
	static StringBuilder sb;
	static LinkedList<Integer> numbers;
	
	public static void perm(int count) {
		if(count == m) {
			for(int i:numbers)
				sb.append(i + " ");
			
			sb.append("\n");
			return;
		}
		
		for(int i=0;i<n; i++) {
			if(numbers.contains(i+1))
				continue;
			
			numbers.add(i+1);
			perm(count+1);
			numbers.removeLast();
		}
		
	}

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		sb = new StringBuilder();
		numbers = new LinkedList<>();
		
		perm(0);
			
		System.out.println(sb.toString());
	}
}

package Math;

import java.util.Arrays;

public class prog_3_최고의집합 {

	  public int[] solution(int n, int s) {
	      int[] answer = new int[n];
	      
	      if(n>s)
	    	  return new int[] {-1}; //바로 새로 생성해서 return 해주기
	      
	      for(int i=0; i<n; i++)
	    	  answer[i] = s/n; //집함 크기만큼에, s/n을 넣어준다. 여기서 -1 +1 해주는게 가장 큰수가 나올 가능성 높음
	      
	      int g = s- (s/n)*n; //나머지만큼 +1씩 해준다
	      
	      if(g == 0) //딱 떨어지면 중복도 가능한거고 합이 딱떨어진다는거니까
	    	  return answer;
	      
	      for(int i=0; i<g; i++)
	    	  answer[i] = answer[i] +1;
	      
	      Arrays.sort(answer);
	      
	      return answer;
	  }
	
	public static void main(String[] args) {
		
	}
}

package T0324;

import java.util.*;

public class t1 {
	
	static public int solution(String s, String pattern) {
		int answer = 0;
		
		int ch[] = new int[32];
		
		for(int i=0; i<pattern.length(); i++)
			ch[pattern.charAt(i)-'a']++; //0-a, 1-b, 2-c, 3-d
		
		for(int i=0; i<=s.length()-pattern.length(); i++) {
			String ss = s.substring(i, i+pattern.length());
			System.out.println(ss);
			int test[] = new int[32];
			
			for(int j=0; j<ss.length(); j++) {
				test[ss.charAt(j)-'a']++;
			}
			
			boolean ck = false;
			for(int k=0; k<32; k++) {
				if(ch[k] != test[k])
					ck = true;
			}
			
			if(ck == false)
				answer++;
			
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		
		System.out.println(solution("aaaaaa", "a"));
	}
}

package Greedy;

import java.util.Arrays;

public class prog_3_단속카메라 {

    public int solution(int[][] routes) {
        int answer = 0;
        int cam = -30001; //제일 작은 값으로 초기화
        Arrays.sort(routes, (a,b) -> Integer.compare(a[1], b[1])); // 1번째 배열로 오름차순
        
        
        for(int i=0;i<routes.length; i++) {
        	if(cam < routes[i][0]) {//내 끝점보다 현재 시작점이 큰 경우에는 겹치지 않는다.
        		cam = routes[i][1]; //cam에 다시 끝점을 넣어주고 다음 시작점과 비교한다
        		answer++;
        	}
        }
        
        return answer;
    }
}