Java

문제 접근 방식 같은 수를 여러번 골라도 상관 없지만 이전 글에서와 같이 9a, 9b 같은 값이 9로 동일한 경우는 순서가 바껴도 똑같기 때문에 이 부분만 중복으로 취급하여 넘어가주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

문제 접근 방식 수열 [1, 7]과 수열 [7, 1]을 같은 경우로 취급하여 오름차순으로 출력하기 위해 [1, 7]만 출력해야 한다. 그러면 [1, 7, 8, 9, 9] 라는 배열이 주어졌을 때 1로 시작하는 경우의 수가 7로 시작하는 경우보다 많을 것이고 8보다는 7이, 9보다는 8이 경우의 수가 더 많아지는 시작에서 끝으로 갈수록 경우의 수가 적어지는 규칙이 있다. 즉 정렬된 배열에서 이미 사용한 인덱스는 다시 사용할 필요가 없기 때문에 재귀 메서드의 파라미터로 인덱스를 추가로 전달해준다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int ..

문제 접근 방식 주어진 수들을 정렬하여 오름차순으로 출력하는건 이전 문제들과 똑같지만 이미 뽑은 수를 재사용하면 안되고 중복된 수열은 제외해야 한다는 조건이 붙었다. 중복된 수열을 제외하는 부분이 많이 힘들었는데 이미 뽑은 수를 체크하는 배열 외에도 현재 재귀 호출에서 이전에 뽑은 수를 기록해둘 지역변수를 하나 추가해서 해결했다. 예를 들어 [1, 7, 9, 9] 같은 수들이 주어진 경우 두 번 등장하는 9를 각각 9a, 9b라고 했을 때 1 7 9a 9b와 1 7 9b 9a는 같은 수열로 취급하여 하나만 출력해야 하는데 이때 9a를 이전에 사용한 값이라고 저장해둘 지역변수에 담아두면 나중에 1 7 까지 뽑고 9b를 뽑는 순간에 비교하여 넘어갈 수 있다. 글로 적으려니 설명을 잘 못하겠어서 재귀 호출 순..

문제 접근 방식 1231 1231 1231 1231 1231 1231 1231 1232 1231 1231 1231 1233 1231 1231 1231 1234 1231 1231 1232 1232 1231 1231 1232 1233 1231 1231 1232 1234 1231 1231 1233 1233 1231 1231 1233 1234 1231 1231 1234 1234 1231 1232 1232 1232 1231 1232 1232 1233 1231 1232 1232 1234 1231 1232 1233 1233 1231 1232 1233 1234 1231 1232 1234 1234 1231 1233 1233 1233 1231 1233 1233 1234 1231 1233 1234 1234 1231 1234..

문제 접근 방식 주어진 배열을 정렬하여 중복해서 선택할 때 M개의 수를 고르는 모든 경우를 출력하면 된다. 모든 수를 중복해서 계속 사용할 수 있기 때문에 사용 여부를 체크하거나 인덱스에 변화를 줄 필요 없이 계속해서 재귀호출과 M번의 반복문을 돌아주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { BufferedReade..

문제 접근 방식 N과 M 시리즈 2번 문제와 같은 문제로 추가로 주어진 배열 입력에 대해 정렬하여 오름차순으로 수열을 만들어 출력하는 문제다. 이전에 등장한 수열이라면 순서 상관없이 중복으로 취급하여 다시 출력하는 경우가 없어야 한다. 예를 들어 1 7 8을 출력했으면 8 7 1 같은걸 출력할 필요가 없다. 즉, 주어진 배열을 순회하며 수열을 만들 때, 다음 자리 수를 뽑는 재귀 호출 시 시작 인덱스를 1씩 증가시켜주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private s..

문제 접근 방식 N과 M (1) 문제와 같은 문제에 조건만 조금 달라져서 풀기가 쉬웠다. 1 ~ 4번 시리즈와는 다르게 정수 배열에 대한 입력이 추가되는데 이를 정렬된 순서로 자기 자신은 제외한 순열을 만들어주면 된다. 코드는 N과 M (1) 문제와 같고 정렬만 추가된다고 이해하면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] permutation; private static boolean[] isUsed; public static void ma..

문제 접근 방식 1 1 1 1 1 2 1 1 3 1 2 2 1 2 3 1 3 3 2 2 2 2 2 3 2 3 3 3 3 3 우선 1부터 N까지의 숫자를 중복이 가능하게 3개를 뽑아서 수열을 만들 수 있을 때 위와 같은 규칙대로 수열을 만들어야 한다. 111, 112, 113 >> 122, 123 위의 숫자를 보면 규칙을 하나 찾을 수 있는데 다음에 올 수 있는 숫자의 범위는 항상 이전의 숫자보다 같거나 커야 한다. 별 찍기도 그렇고 N과 M시리즈도 그렇고 혼자 규칙 찾아서 풀어야 하는거만 빼면 재귀 연습하기는 참 좋긴하다... 어쨋든 이 규칙대로 수열을 만들기 위해서는 재귀 호출을 할 때 다음에 올 숫자의 시작 범위를 파라미터로 넘겨줘야 한다는 것이다. 이 부분만 생각하면서 풀면 어렵지 않게 풀 수 있는..