230814 - [Java-python] BruteForce 완전탐색

[robert-min]

• 중복 O, 순서 X
• 중복 O, 순서 O(비내림차순)
• 중복 X, 순서 X
• 중복 X, 순서 O(비내림차순)

[robert-min]

BOJ15651 중복 O, 순서 X 링크

• 문제 풀이 고민
  • 앞자리부터 1부터 숫자 채움
  • 전체 탐색이 완료되면 결과값 저장
• 시간복잡도 : O(N ** M)
  • 최대 7 ** 7 = 823,000 < 1초, 1억 보다 작기 때문에 완전 탐색으로 풀이 가능

python 풀이(재귀)

• " ".join 출력
• 리스트를 활용한 재귀함수

  
  def search(case = []):
  if len(case) == M:
      # 한줄씩 출력
      print(" ".join(case))
  else:
      for i in range(1, N+1):
          search(case + [str(i)])

if name == "main":

input

N, M = map(int, input().split())

# search(M 자리까지) + 탐색 결과 리스트에 문자열 저장
search()

### python 풀이(itertools.product)

```python
import itertools

n, m = map(int, input().split())
lst = map(str, [str(x) for x in range(1, n+1)])
print("\n".join(map(" ".join, itertools.product(lst, repeat=m))))

java 풀이

• java String은 불변 객체로 이어지는 문자열 생성이 불가하면 새로운 객체를 생성해야하기 때문에 메모리 문제가 발생
• StringBuilder은 append 매서드로 변경 가능한 문자열을 만들어 주기 때문에, String을 합치는 작업 시 하나의 대안

import java.io.; import java.util.;

public class Main { static StringBuilder sb = new StringBuilder();

static void input() {
    FastReader scan = new FastReader();
    N = scan.nextInt();
    M = scan.nextInt();
    selected = new int[M + 1];
}

static int N, M;
static int[] selected;

// Recurrence Function (재귀 함수)
// 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
// 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
static void rec_func(int k) {
    if (k == M + 1) { // 다 골랐다!
        // selected[1...M] 배열이 새롭게 탐색된 결과
        for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
        sb.append('\n');
    } else {
        for (int cand = 1; cand <= N; cand++) {
            // k 번째에 cand 가 올 수 있으면
            selected[k] = cand;

            // k+1 번부터 M 번까지 잘 채워주는 함수를 호출해준다.
            rec_func(k + 1);
            selected[k] = 0;
        }
    }
}

public static void main(String[] args) {
    input();

    // 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
    rec_func(1);
    System.out.println(sb.toString());
}

}

### 참고. Java FastReaderAPI

```java

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

[robert-min]

BOJ15652. 중복 O, 순서 O(비내림차순) 링크

• 문제풀이
  • 이전 값보다 큰값이 다음 칸에 들어올 수 있도록 반복문 수정
  • 이전 값이 없을 경우 1부터 시작하도록
• 시간초과
  • 이전 O(N**M)보다 탐색을 적게하기 때문에 적은 시간이 소요

파이썬 풀이

def search(case = []):
    if len(case) == M:
        # 한줄씩 출력
        print(" ".join(case))
    else:
        # 이전값 비교
        if not case:
            start = 1
        else:
            start = int(case[-1])
        for i in range(start, N+1):
            search(case + [str(i)])

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())

    # search(M 자리까지) + 탐색 결과 리스트에 문자열 저장
    search()

자바 풀이

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M + 1];
    }

    static int N, M;
    static int[] selected;

    // Recurrence Function (재귀 함수)
    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if (k == M + 1) { // 다 골랐다!
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            int start = selected[k-1];
            if (start == 0) start = 1;

            for (int cand = start; cand <= N; cand++) {
                selected[k] = cand;
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

    public static void main(String[] args) {
        input();

        // 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
        rec_func(1);
        System.out.println(sb.toString());
    }

[robert-min]

BOJ15649 중복 X, 순서 X 링크

• 문제풀이
  • 이미 사용된 숫자가 아닌 경우에만 탐색

파이썬 풀이

def search(case = []):
    if len(case) == M:
        # 한줄씩 출력
        print(" ".join(case))
    else:
        for i in range(1, N+1):
            if str(i) not in case:
                search(case + [str(i)])

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())

    # search(M 자리까지) + 탐색 결과 리스트에 문자열 저장
    search()

자바 풀이

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M + 1];
    }

    static int N, M;
    static int[] selected;

    // Recurrence Function (재귀 함수)
    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if (k == M + 1) { // 다 골랐다!
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = 1; cand <= N; cand++) {
                boolean isUsed = false;
                for (int i=1; i<k; i++) {
                    if (cand == selected[i]) {
                        isUsed = true;
                    }
                }

                if (!isUsed) {
                    selected[k] = cand;
                    rec_func(k + 1);
                    selected[k] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        input();

        // 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
        rec_func(1);
        System.out.println(sb.toString());
    }
}

[robert-min]

BOJ15650. 중복 X, 순서 O(비내림차순) 링크

• 문제풀이
  • 이전 값 확인 + 사용되지 않은 값 확인

파이썬 풀이

def search(case = []):
    if len(case) == M:
        # 한줄씩 출력
        print(" ".join(case))
    else:
        # 이전값 비교
        if not case:
            start = 1
        else:
            start = int(case[-1])
        for i in range(start, N+1):
            if str(i) not in case:
                search(case + [str(i)])

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())

    # search(M 자리까지) + 탐색 결과 리스트에 문자열 저장
    search()

java 풀이

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M + 1];
    }

    static int N, M;
    static int[] selected;

    // Recurrence Function (재귀 함수)
    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if (k == M + 1) { // 다 골랐다!
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {

            for (int cand = selected[k-1] + 1; cand <= N; cand++) {
                selected[k] = cand;
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

    public static void main(String[] args) {
        input();

        // 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
        rec_func(1);
        System.out.println(sb.toString());
    }
}