[문제풀이] 순열2

업데이트:

문제 링크 : 순열2

풀이 시간 : 20분 + 10분

1. 문제 풀이

1부터 N까지 들어있는 배열 2개(A,B)를 각각 순서를 섞고 같은 인덱스 중 큰 값들의 합을 구한다.

그렇게 해서 나온 합 중에서 K 이상인 개수를 구하는 문제

A, B의 조합의 경우를 다 생각하지 않고 A를 고정하고 B가 나올 수 있는 경우만 생각

그 후 A로 만들 수 있는 경우의 수를 곱해주면 정답

1) B의 순서를 섞어서 나올 수 있는 경우의 수를 구한다.(combi 함수)

2) 그 후 K보다 큰 경우의 수들을 구한다.(start 밑 for문)

3) A로 만들 수 있는 경우의 수 곱한다.

2. 소스 코드

    public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 메모이제이션을 위한 배열
		ArrayList<Integer>[] arr = new ArrayList[11];
		int[] mux = new int[11];
		int[] sum = new int[11];
		mux[0]=1;
		sum[0]=0;
		// 1부터 N까지의 합과 곱
		for (int i = 1; i < mux.length; i++) {
			mux[i] =mux[i-1]*i;
			sum[i]=sum[i-1]+i;
		}
		int iter = Integer.parseInt(br.readLine());
		for (int i = 1; i <= iter; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long result = 0;
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			// 테스트케이스 중 N이 처음일 때
			if(arr[N] == null) {
				//N일 때 만들수 있는 경우의 수
				//배열이 1부터 N까지 1씩 증가하는 수열이기 때문에
				//N으로 만들 수 있는 최대값-최소값+1이 만들 수 있는 경우의 수
				int size = 0;
				if(N%2==0) {
					size = (sum[N]-sum[N/2])*2-sum[N]+1;
				}else {
					size = (sum[N]-sum[N/2+1])*2+N/2+1-sum[N]+1;
				}
				arr[N] = new ArrayList<Integer>();
				for (int j = 0; j < size; j++) {
					arr[N].add(0);
				}
				//순열 만들기 배열 두 개(A,B)일 떄 A를 {1,2,...N}으로 고정하고 B만 순열 만들기 
				combi(0,new boolean[N],-1*sum[N],arr[N]);
			}
			// K가 최소값보다 작으면 0부터, 크면 K-sum[N]부터
			int start  = K-sum[N] <0 ? 0: K-sum[N];
			for (int j =start; j < arr[N].size(); j++) {
				result += arr[N].get(j);
			}
			// A의 순열의 개수를 곱해주면 총 개수
			bw.write("#"+i+" "+result*mux[N]);
			bw.newLine();
		}
		bw.flush();
		bw.close();
	}
	//배열의 인덱스 참조를 위해서 sum은 N으로 만들 수 있는 최소값*-1로 계산
	static void combi(int cnt, boolean[] v, int sum, ArrayList<Integer> hm) {
		if (v.length == cnt) {
			hm.set(sum, hm.get(sum)+1);
		} else {
			for (int i = 0; i < v.length; i++) {
				if (!v[i]) {
					v[i] = true;
					//B[i]와 A[cnt] 중 큰 값을 골라 더해준다.
					combi(cnt + 1, v, sum +Math.max(i+1,cnt+1), hm);
					v[i] = false;
				}
			}
		}
	}

3. 후기

추석 연휴에 쉬면서 다른 작업을 하다보니 문제 풀이를 못했다.

프로그래머스 문제는 거의 다 풀었고 이제는 SW Expert나 백준에 비중을 두고 풀 예정이다.

문제에 대한 후기는 SW Expert 사이트는 한번에 여러 테스트케이스를 돌리기 때문에 메모이제이션을 하면 좋은 경우가 많다.

테스트케이스로 iter=2, (N=10, K=60), (N=10, K=66)라면 10에 대한 순열 정보를 (N=10, K=60)일 때 한 번 저장하고 두번째는 배열 참조만 하게끔 만들었다.

참고