백트래킹 문제 (재귀 연습)

• BOJ 15649: N과 M(1)
• https://www.acmicpc.net/problem/15649

java

• 메모리: 22,888KB, 시간: 216ms
• TypeCasting 오류 해결
• JAVA 입출력 방법 공부

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

public class CodingTest {
    static int n,m;
    static char[] answer; // 출력값 (0<=idx<m)
    static boolean[] visited;// 방문 값 기록(1<=idx<=n)
    static StringBuilder sb = new StringBuilder();
    public static void backtracking(int k){
        if (k==m){
            sb.append(answer).append('\n');
            return;
        }
        for(int i=1; i<=n;i++){
            if(!visited[i]){
                answer[2*k]= (char)(i+'0'); // idx, typecasting 주의
                visited[i]=true;
                backtracking(k+1);
                visited[i]=false;
                // arr[k] 삭제 생략
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n= Integer.parseInt(st.nextToken());
        m= Integer.parseInt(st.nextToken());

        visited = new boolean[n+1];
        answer = new char[2*m]; // 출력을 위한 빈 문자 추가
        for (int i=1;i<2*m;i+=2){
            answer[i]=' ';
        }

        backtracking(0);

        System.out.println(sb);
    }
}

• java로 알고리즘 문제를 잘 풀어보지 않아서 자바 입출력, 자료형 casting에서 에러가 나서 시간이 좀 걸렸다.
• 자바 입출력은 나중에 한번 제대로 정리해봐야겠다.

Java Convert int to char

https://www.javatpoint.com/java-int-to-char

• TypeCasting

  • int: 4 byte -> char: 2 byte

  • Integer 숫자에 해당하는 ASCII 문자값이 char로 저장된다.

  • 따라서, 원래 int 값 그대로 char로 변환하기 위해서는 '0'을 더하여 아스키코드를 맞춰주어야 한다. '0'의 아스키 숫자는 48인데, 48을 더해줌으로써 0부터 시작되는 숫자값이 보여질 수 있는 것이다.

• 코드 예시

  public class IntToCharExample1{  
  public static void main(String args[]){  
  int a=65;  
  char c=(char)a;  // 65를 바로 캐스팅
  System.out.println(a);  // 출력값: A
  }}  

  public class IntToCharExample2{  
  public static void main(String args[]){  
  int a=1;    
  char c=(char)a;    
  System.out.println(c);  // 출력값: print nothing
  }}  

  public class IntToCharExample3{  
  public static void main(String args[]){  
  int a=1;    
  char c=(char)(a+'0');    // 아스키코드: 1+48 
  System.out.println(c);   // 출력값: '1'
  }}  

python

1. 일반 풀이

• 메모리: 30,840KB, 시간: 224ms

n, m = map(int, input().split())
visited = [0 for _ in range(n + 1)]
answer = []


def bt(k: int):
    if k == m:
        print(' '.join(map(str, answer)))
    for i in range(1, n + 1):
        if visited[i]==0:
            answer.append(i)
            visited[i] = 1
            bt(k + 1)
            visited[i] = 0
            answer.pop()


bt(0)

2. python itertools permutations 라이브러리 사용

• 메모리: 33,516KB, 시간: 80ms

import itertools

n, m = map(int, input().split())
li = map(str, range(1, n+1))

print("\n".join(list(map(' '.join,itertools.permutations(li,m)))))