14954번, 15649번, 15650번, 15651번, 15625번

14954번

 

기초 수학 연습 문제 4번과 유사한 문제이다 (자세한 풀이는 그쪽에 적어둠)

 

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println(isHappy(number) ? "HAPPY" : "UNHAPPY");
    }

    public static boolean isHappy (int number) {
        Set<Integer> set = new HashSet<>();
        while(set.add(number)) {
            int eachSum = 0;
            while(number>0) {
                eachSum += (number % 10) * (number % 10);
                number /= 10;
            }
                number = eachSum;
        }
        if(number == 1) {
            return true;
        }
        return false;
    }
}

 

15649번 (순열, 백트래킹) - visited 사용

 

 

 

헷갈려서 찾아보다가 한 블로그에서 발견한 댓글... (사랑합니다)

 

 

int [ ] in : 선택하고자 하는 숫자 N개의 배열

int [ ] out: 선택한 숫자 M개를 담기위한 배열

boolean [ ] visited: 숫자를 선택했는지 알려주는 배열 (true일 경우 선택o, false일 경우 선택x)

 

맞긴 했지만 메모리가 너무 크고 오래 걸린다

import java.util.Scanner;

public class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] in= new int[n];
        for(int i = 0; i<n; i++) {
            in[i] = i+1;
        }
        boolean [] visited = new boolean[n];
        int [] out = new int[m];
        permutation(visited, 0,n,m,in,out);
    }

    public static void permutation (boolean [] visited, int depth, int n, int m, int[] in, int[] out) {
        if(depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(out[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 0; i<n; i++) {
            if(visited[i] != true) {
                visited[i]= true;
                out[depth] = in[i];
                permutation(visited,depth+1,n,m,in,out);
                visited[i]= false;
            }
        }
    }
}

15650번 (조합, 백트래킹) - visited 사용

 

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

int [ ] arr = 조합을 뽑아낼 숫자 N개의 배열

boolean [ ] visited: 숫자를 선택했는지 알려주는 배열 (true일 경우 선택o, false일 경우 선택x)

 

depth == n 이 되면 모든 인덱스를 다 보았으므로 재귀를 종료한다 

import java.util.Scanner;

public class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] arr= new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = i+1;
        }
        boolean [] visited = new boolean[n];
        combination(arr,visited,0,n,m);
    }

    public static void combination (int[] arr, boolean[] visited, int depth, int n, int m) {
        if(m == 0) {
            for(int i = 0; i<n; i++) {
                if(visited[i]) {
                    System.out.print(arr[i]+" ");
                }
            }
            System.out.println();
            return;
        }

        if(depth == n) return;

        visited[depth] = true;
        combination(arr,visited,depth+1,n,m-1);
        visited[depth] = false;
        combination(arr,visited,depth+1,n,m);
    }
}

순서가 상관 없고, 중복도 없으므로 선택된 원소를 따로 저장하지 않고, 원소들과 visited만 이용하여 방문한 원소들을 순서대로 확인 후 출력한다. 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행한다. start 는 탐색의 시작 기준

import java.util.Scanner;

public class Practice {
    static void combination(int[] arr, boolean[] visited, int start, int n, int m, int depth) {
        if (depth == m) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, m,depth+1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] arr= new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = i+1;
        }
        boolean [] visited = new boolean[n];
        combination(arr,visited,0,n,m, 0);
    }
}

 

15651번 (중복 순열)

 

 

중복 순열: 순서 O, 중복 O > 집합 {1, 2, 3} 중 3개의 원소를 선택한 중복 순열 = 27가지

중복 조합: 순서 X, 중복 O

 

일반 순열에서 중복 선택을 방지하기 위해 만들었던 visited 배열이 없어진다

 

인텔리제이에서는 돌아갔는데 시간 초과 떠서 틀린 풀이 ㅎㅎ......

틀린 이유는 StringBuilder 가 아니라 System.out.print(arr[i] + " "); 로 했기 때문에

입력의 경우는 Scanner 보다는 BufferedReader 가 빠르다고 한다

 

BufferedReader :  엔터만 경계로 인식하고 입력받은 데이터가 String으로 고정, 별도의 데이터 가공이 필요(Scanner는 띄어쓰기와 엔터를 경계로 하여 입력값을 인식하므로 별도의 가공이 필요 없다)

 

버퍼를 사용하는 입력은, 키보드의 입력이 있을 때마다 한 문자씩 버퍼로 전송한다. 버퍼가 가득 차거나 혹은 엔터가 나타나면 버퍼의 내용을 한 번에 프로그램에 전달하므로 속도가 빠르다 (버퍼는 데이터를 한 곳에서 다른 하나 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 임시 메모리 영역)

 

BufferedReader 클래스의 주요 메서드 : close() , readLine() 등

 

BufferedReader는 다음과 같이 사용한다

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
String s = br.readLine();
int i = Integer.parseInt(br.readLine());

입력의 경우 readLine(); 메서드를 사용하며 리턴값이 String으로 고정되어 있기 때문에 다른 타입으로 입력 받기 위해서는 반드시 형변환이 필요하다. 예외 처리를 반드시 해줘야 하기 때문에 try/catch문으로 감싸주거나, throws IOException 을 통한 예외처리를 실시한다

 

StringTokenizer:  사용자가 지정하는 구분자를 경계로 하여 문자열을 나눠주는 클래스 (사용자가 구분자 지정을 생략하면 공백이나 탭이 기본 구분자) nextToken(); 을 통해 존재하는 토큰을 리턴한다

 

import java.util.Scanner;

public class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            in[i] = i + 1;
        }
        int[] out = new int[m];
        permutation(0, n, m, in, out);
    }

    public static void permutation(int depth, int n, int m, int[] in, int[] out) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(out[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            out[depth] = in[i];
            permutation(depth + 1, n, m, in, out);
        }
    }
}

StringBuilder 와 BufferedReader를 사용한 풀이 (생소하다...)

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

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            in[i] = i + 1;
        }
        int[] out = new int[m];
        permutation(0, n, m, in, out);
        System.out.println(sb);
    }

    static StringBuilder sb = new StringBuilder();

    public static void permutation(int depth, int n, int m, int[] in, int[] out) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                sb.append(out[i] + " ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < n; i++) {
            out[depth] = in[i];
            permutation(depth + 1, n, m, in, out);
        }
    }
}

근데 난 메모리 차이가 scanner 사용했을 때랑 bufferedreader 사용했을 때랑 큰 차이가 없다.....왜죠?

 

15652번 (중복 조합, 비내림차순)

 

 

비내림차순이란 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 뜻함

조합과는 다르게 중복이 가능하기 때문에 선택한 원소를 저장하는 배열(int [ ] out)은 필요

 

현재 선택한 원소보다 뒤의 것만 선택 가능하지 않고, 현재 선택한 원소를 포함하여 그 뒤의 것들을 선택 가능

조합 코드에서 중복을 체크하기 위해 사용한 visited를 사용하는 부분을 제거

 

import java.util.Scanner;

public class Practice {
    static void combination(int[] arr, int[] out, int start, int n, int m, int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(out[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < n; i++) {
            out[depth] = arr[i];
            combination(arr, out, i, n, m, depth + 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        int[] out = new int[m];
        combination(arr, out,0, n, m, 0);
    }
}