희연's 개발 일기장

문제 

- 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램

N을 선언하고, 부분집합으로 사용하는지 안하는지 체크하는 check 배열을 n+1크기로 만든다.

ex. N=3

T.DFS(1) 1부터의 원소를 DFS

n+1은 4이고, L은 1이기 때문에 else 문 수행

ch[1]에 1을 체크해준다. 1 0 0 -> DFS(2) 수행하고 DFS(1) 함수가 끝나지 않았기 때문에 리턴 주소를 스택 프레임에 push

L이 2이기 때문에 else문 수행

ch[2]에 1 체크 1 1 0 -> DFS(3) 수행 -> stack.push(DFS(2))

L = 3 else 문 수행

ch 1 1 1 -> DFS(4) -> stack.push(DFS(3))

L = 4 if문 수행

1부터 n까지의 ch 배열에서 사용 가능한 1들을 출력(공집합은 출력하지 않는다) -> 1 2 3

스택 프레임을 pop하면 맨 위의 DFS[3]의 리턴 주소로 돌아간다.

ch[L] = 0;

DFS(L+1);

ch[3] = 0 -> 1 1 0 -> DFS(4) -> if문 수행 -> 1 2 출력 -> stack.pop = DFS(2)

ch[2] = 0 -> 1 0 0 -> DFS(3) -> ch[3]=1 -> 1 3 출력 

...

이렇게 나온 결과들은 1~N까지의 원소를 갖는 집합의 부분집합을 모두 출력할 수 있다.

public class Solution {
    static int n;
    static int[] ch; // check 배열 : 부분집합으로 사용할지 안할지 체크
    public void DFS(int L){
        if(L==n+1){
            String temp = "";
            for(int i=1; i<=n; i++){
                if(ch[i]==1) temp+=(i+" "); // check
            }
            
            if(temp.length()>0) System.out.println(temp); // 공집합 출력 X

        } else {
            ch[L] = 1; // 사용 O
            DFS(L+1); // 왼쪽 = 사용
            ch[L] = 0; // 사용 X
            DFS(L+1); // 오른쪽 = 사용 X
        }
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}

전위 순회

class Node{
    int data;
    Node lt, rt;

    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}
public class Solution {
    Node root;
    public void DFS(Node root){
        if(root==null){
            return;
        } else {
            System.out.println(root.data+" "); // 전위순회
            DFS(root.lt);
            DFS(root.rt);
        }
    }
    public static void main(String[] args) {
        Solution tree = new Solution();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }
}

중위 순회

DFS(root.lt);
System.out.println(root.data+" "); // 중위순회
DFS(root.rt);

후위 순회

DFS(root.lt);
DFS(root.rt);
System.out.println(root.data+" "); // 후위순회

정규표현식

class Solution {
    public String solution(String new_id) {
        String answer = "";
        // 1번
        // new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
        String first = new_id.toLowerCase();

        // 2번
        // new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
        String second = first.replaceAll("[^a-z0-9-_.]","");

        // 3번
        // new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
        String third = second.replaceAll("\\.{2,}",".");

        // 4번
        // new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
        String fourth = third;
        if(fourth.charAt(0)=='.'){
            fourth = fourth.substring(1, fourth.length());
        }

        if(fourth.charAt(fourth.length()-1)=='.'){
            fourth = fourth.substring(0, fourth.length()-1);
        }

        // 5번
        // new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
        String fifth = fourth;
        if(fifth.equals("")){
            fifth = "a";
        }

        // 6번
        // new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
        //     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
        String sixth = fifth;
        if(sixth.length() >=16){
            sixth = sixth.substring(0, 15);

            if(sixth.charAt(sixth.length()-1) == '.'){
                sixth = sixth.substring(0, sixth.length()-1);
            }
        }

        // 7번
        // new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
        String seventh = sixth;
        while(seventh.length() <3){
            seventh += seventh.charAt(seventh.length()-1);
        }

        answer = seventh;
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        System.out.println(T.solution("123_.def"));
    }
}

public class Solution {
    public static int[] solution(int[] arr){
        int[] answer = new int[arr.length];
        int n = arr.length;

        // 반복문 범위 복습하기
        for(int i=0; i< n-1; i++){
            for(int j=0; j<n-i-1; j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for(int i=0; i<arr.length; i++){
            answer[i] = arr[i];
            System.out.println(answer[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {13,5,11,7,23,15};
        System.out.println(T.solution(arr));
    }
}

public class Solution {
    public static int[] solution(int[] arr){
        int[] answer = new int[arr.length];
        int min = Integer.MAX_VALUE;
        int idx = 0;

        for(int i=0; i<arr.length; i++){
            min = Integer.MAX_VALUE;
            for(int j=i+1; j<arr.length; j++){
                if(arr[j] < min){
                    min = arr[j];
                    idx = j;
                }
            }

            // 교체
            int temp = arr[i];
            arr[i] = min;
            arr[idx] = temp;
        }

        for(int i=0; i<arr.length; i++){
            answer[i] = arr[i];
            System.out.println(answer[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {13,5,11,7,23,15};
        System.out.println(T.solution(arr));
    }
}

public class Solution {
    public static int solution(int[] arr, int K){
        // 그냥 하면 오름차순으로 정렬되기 때문에 Collections.reverseOrder으로 내림차순 만들기
        TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());
        int answer = 0;

        // 카드 3장 뽑기
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                for(int z=j+1; z<arr.length; z++){
                    Tset.add(arr[i]+arr[j]+arr[z]);
                }
            }
        }

        int cnt = 0;
        for (int x: Tset) {
            cnt++;
            if(cnt==3){
                answer = x;
                break;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {13,15,34,23,45,65,33,11,26,42};
        int K = 3;
        System.out.println(T.solution(arr, K));
    }
}

public class Solution {
    public static String solution(String str1, String str2){
        Queue<Character> queue = new LinkedList<>();
        String answer = "YES";

        for(int i=0; i< str1.length(); i++){
            char element = str1.charAt(i);
            queue.add(element);
        }

        for(int i=0; i<str2.length(); i++){
            char element = str2.charAt(i);
            if(queue.contains(element)){
                if(element!= queue.poll()){
                    answer = "NO";
                    break;
                }
            }
            if(!queue.isEmpty()){
                answer = "NO";
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        String str1 = "CBA";
        String str2 = "CBDAGE";
        System.out.println(T.solution(str1,str2));
    }
}

import java.util.Stack;

public class Solution {
    public static int solution(String str){
        Stack<Integer> s = new Stack<>();
        int answer = 0;

        for(int i=0; i<str.length(); i++){
            char ch = str.charAt(i);
            if(Character.isDigit(ch)){ // 숫자일 경우
                s.add(ch-48);
            } else { // 숫자가 아닐 경우
                int rt = s.pop();
                int lt = s.pop();

                if(ch == '+'){
                    s.add(lt+rt);
                } else if(ch == '-'){
                    s.add(lt-rt);
                } else if(ch == '/'){
                    s.add(lt/rt);
                } else if(ch == '*'){
                    s.add(lt*rt);
                }
            }
        }

        answer = s.get(0); // 맨 앞의 결과가 연산의 결과가 된다.
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        String str = "352+*9-";
        System.out.println(T.solution(str));
    }
}