문제 url:
N과 M(2)
문제:
🤔 문제 알아보기
이번 문제는, 이전 문제 15649번과 아주 유사하다.
차이점이 있다면 고른 수열이 반드시 오름차순이어야 한다는 점,
즉, 1,2,3,4 와 같이 오름차순으로 정렬되면 OK! 1,2,4,3 이런식으로 수열이 오름차순이 아니면 NOT OK!
그러면, 오름차순이 되도록 현재 값과 이전값을 비교해서 큰 수만 저장하도록 하면 될 것이다.
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static boolean[] visited;
static StringBuilder sbd;
static int j;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sbd = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new int[M];
visited = new boolean[N];
dfs(N, M, 0);
System.out.println(sbd);
}
static void dfs(int N, int M, int depth) {
if(depth == M) {
for(int val : arr) {
sbd.append(val).append(" ");
}
sbd.append("\n");
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
if(depth > 0 && arr[depth] < arr[depth -1]) {
visited[i] = false;
continue;
}
dfs(N, M, depth + 1);
visited[i] = false;
}
}
}
}
😎 코드 풀이 및 해석
코드를 보면 이전 문제와 거의 차이가 없다. 차이가 하나 존재한다면 아래 로직이 추가되었을 뿐이다.
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
if(depth > 0 && arr[depth] < arr[depth -1]) {
visited[i] = false;
continue;
}
dfs(N, M, depth + 1);
visited[i] = false;
}
↓
if(depth > 0 && arr[depth] < arr[depth -1]) {
visited[i] = false;
continue;
}해당 코드는 즉, 현재 arr에 저장된 값이 이전에 저장된 값보다 작다면
즉, 오름차순이 아니라면 재귀호출을 진행하지 않고, i를 N이전까지 반복문을 도는 것이다.
이렇게 되면, 만약 1,2,3,4가 출력되고 그 다음 수 1,2,4,3이 출력되어야 할 때 3이 4보다 작기 때문에 출력되지 않고 반복문을 마치게 되는 것이다.
여기서 중요한 점은 반드시 visited[i] = false를 해줘야 하는 것인데,
만약 TC에 5,4를 주었다고 가정하자, 그럼 다음과 같은 결과값이 나와야 한다.
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5하지만, 만약
visited[i] = false를 해주지 않으면 결과는 다음과 같다
1 2 3 4
1 2 3 5
1 2 4 5
코드를 봤을 때 분명 오름차순으로 정렬된 것을 볼 수 있다. 하지만 1,3,4,5처럼 나와야 하는 값들이 나오지 않은데, 이는 visited[2] 즉, 숫자 3에 대해서 visited를 false로 지정하지 않아 발생한 문제이다.
이를 재귀적으로 보면, 1,2,4,5를 호출할 때
1,2,4까지 갔다가 마지막 depth가 3인 부분에서 3을 호출했다. 하지만! 3은 4보다 작기 때문에 visited가 true로 변환되고 continue에 의해 visited[2] = false로 바꿔지지 않고 계속 true로 머물게 되면서 발생한 문제이다.
그래서 continue를 하기 이전에 visited[i] = false; 해당 로직을 먼저 실행해주는 것이다.
✨ 코드 리팩토링
간단히 오름차순으로 구현하는 것인데도 시간이 좀 오래걸렸다. 그래서 또 더 나은 방법과 접근법을 배워보고자 다른 코드를 공부해보았다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static StringBuilder sbd;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sbd = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M];
dfs(1,0);
System.out.println(sbd);
}
static void dfs(int at, int depth) {
if(depth == M) {
for(int val : arr) {
sbd.append(val).append(" ");
}
sbd.append("\n");
return;
}
for(int i = at; i <= N; i++) {
arr[depth] = i;
dfs(i + 1, depth + 1);
}
}
}
먼저 기존에 dfs 메서드에 파라미터로 입력했던 N과 M은 전역변수로 설정하였고, 그 대신 at이라는 파라미터를 생성하였다.
변수 at은 즉 현재 위치를 의미하는 변수로, 현재 i번째를 의미하는 것이다.
at은 언제나 i+1을 입력받기 때문에 이전보다 작은수가 올 수 없으며, 또한 중복되는 값 역시 올 수 없다.
왜? 반복문 i의 시작값이 at으로 설정되어 있기 때문에 이미 존재하고 있는 숫자는 at 이전 숫자이기 때문에 올 수 없는 것이다.
이렇게 하니, 이전코드보다 훨씬 간결하게 짤 수 있어졌다.
💕 참고자료
