[SWEA] 4008.숫자 만들기 / Next-Permutation

@Next-Permutation / 24m

넥퍼로 풀면 재귀보다 훨씬 효율적으로 풀 수 있는 문제다.

쉬운 문제였음!

 

 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

 

구현 방법

1. 연산자를 +는 0, -는 1, *는 2, /는 3으로 바꿔서 크기가 N - 1인 int 배열에 저장했다.

예를 들면, 문제에서 2 1 0 1 로 주어졌을 때 (1번 테케)

이를 크기가 4인 배열에

0

0

1

3

이렇게 저장하는 식이다.

 

이를 위해서 Arrays.fill(채우려는 배열, 시작인덱스(포함), 끝인덱스(미포함), 채울 값) 을 이용했다.

보통 인덱스를 쓰는 버전은 상대적으로 잘 안 쓰는 것 같은데, 잘 쓰면 매우 유용하다!

 

 

2. 연산자를 배열에 저장해 놓고 그 배열을 Next-Permutation으로 돌린다.

보통은 순열 또는 조합을 만들 때 재귀를 써도 상관없지만 이 문제처럼 원소에 중복이 있는 경우에는 Next-Permutation이 훨씬 더 효율적이다.

예를 들어서 123455 라는 배열로 순열을 만들 경우, 재귀는 123455가 두번 출력되지만 Next-Permutation은 123455는 한번만 출력된다. 이는 숫자 크기를 비교해서 정렬하는 속성 때문이다. (?? 보충 설명 필요)

 

 

3. Next-Permutation 으로 만든 연산자 배열을 가지고 값을 계산한다. 이때, 각 연산자 배열에서 가져온 값을 switch문을 활용해서 계산했다.

 

4. 연산 시 0으로 나눠주는 경우에 대한 예외처리를 해 줘야 한다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	private static int N, minVal, maxVal, num[], operator[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			minVal = Integer.MAX_VALUE;
			maxVal = Integer.MIN_VALUE;
			
			N = Integer.parseInt(br.readLine());
			num = new int[N];
			operator = new int[N - 1];
			
			st = new StringTokenizer(br.readLine());
			int start = 0, end = 0, temp;
			for (int i = 0; i < 4; i++) {
				temp = Integer.parseInt(st.nextToken());
				end += temp;
				Arrays.fill(operator, start, end, i);
				start += temp;
			}
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++)
				num[i] = Integer.parseInt(st.nextToken());
			
			do {
				calc();
			} while(nextPermutation());
			
			sb.append("#" + t + " " + (maxVal - minVal) + "\n");
		}
		System.out.println(sb);
	}

	private static void calc() {
		int rslt = num[0];
		
		for (int i = 0; i < N - 1; i++) {
			switch (operator[i]) {
			case 0: rslt += num[i + 1]; break;
			case 1: rslt -= num[i + 1]; break;
			case 2: rslt *= num[i + 1]; break;
			case 3: 
				if (num[i + 1] == 0) return;
				rslt /= num[i + 1]; break;
			}
		}
		if (minVal > rslt) minVal = rslt;
		if (maxVal < rslt) maxVal = rslt;
	}

	private static boolean nextPermutation() {
		int size = N - 1;
		
		int i = size - 1;
		while (i > 0 && operator[i - 1] >= operator[i]) i--;
		if (i == 0) return false;
		
		int j = size - 1;
		while (operator[i - 1] >= operator[j]) j--;
		swap(i - 1, j);
		
		j = size - 1;
		while (i < j) swap(i++, j--);
		
		return true;
	}

	private static void swap(int i, int j) {
		int temp = operator[i];
		operator[i] = operator[j];
		operator[j] = temp;
	}
}

 

처음에 fail이 떠서 뭐지 하고 봤는데,

0으로 나눠주는 부분에 대한 예외처리에서 나누는 수가 아닌 나누어질 수가 0일때 예외처리를 해버려서 틀렸었다. (a / b면 a가 0일때 예외처리를 했었음..) 바보같은 실수였다.

고치니까 바로 통과됨.

 

끝!