[BOJ] 15651 N과 M(3) 자바

문제 : 

중복 순열과 개념이 비슷하다. 하지만 나는 순열조합에 약해 식을 세우지 못하고 dfs로 풀었다. 

dfs 안에서 for문을 통해 숫자가 문자열로 뒤에 공백과 함께 추가된다. m==1, 즉 M을 만족한 경우 마지막으로 for문에서 N만큼 i를 증가시켜 뒤에 연결한 후 출력한다. 이 알고리즘의 결과 시간이 2716ms 으로 너무 비효율적으로 나왔다. 

문자열이 계속 더해지는 경우에는 StringBuilder를 통해 메모리와 시간을 아껴야 한다. 이를 위해 dfs 때마다 더해지는 i를 담을 배열이 필요하다. 또한 dfs 마지막을 단지 배열을 StirngBuilder 객체에 담아 출력하는 함수로 사용한다. 따라서 마지막 dfs(m==0)를 제외하고는 N번을 돌아 1~N까지의 경우를 모두 더해주고 마지막 dfs때는 담긴 숫자들을 출력해주기만 하면 되기에 배열의 길이 M만큼 for문을 돈다. 

실행 결과 시간이 308ms로 눈에 띄게 줄었다. 다시 한번 확실히 하자. String 변수를 계속 더하는 것은 매우 비효율적이다.

 

<결과>