희제 블로그

문제

---------------------------

---------         ---------

---   ---         ---   ---

- -   - -         - -   - -

0
1
3
2

-
- -
- -   - -         - -   - -
- -   - -

// [BOJ] 4779. 칸토어 집합

import java.io.*;

// public
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            try {
                int N = Integer.parseInt(br.readLine());
                String answer = divideAndConquer(N);

                System.out.println("answer : " + answer);
            } catch (Exception e) {
                break;
            }
        }
    }

    public static String divideAndConquer(int n) {
        if (n == 0) return "-";

        String blanks = "";
        for (int i = 0 ; i < Math.pow(3, n - 1); i++) {
            blanks += " ";
        }

        return divideAndConquer(n - 1) + blanks + divideAndConquer(n - 1);
    }
}

해당 풀이는 메모리 초과가 났는데, 재귀를 들어가면서 반환되는 문자열들의 길이가 3^12 = 531441, 3^11 = 177147, ... 로 메모리를 많이 사용하기 때문인 것으로 추측된다.

풀이 2 - StringBuilder 이용

Java의 String의 경우 특정 인덱스에 위치한 원소값을 수정할 수 없지만 StringBuilder를 사용하면 setCharAt 메소드를 이용하여 수정이 가능하다고 한다. 때문에 매번 새로운 객체를 생성하는 String을 사용할 때보다 메모리를 크게 줄일 수 있다.

// [BOJ] 4779. 칸토어 집합

import java.io.*;

// public
public class Main {
    public static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            try {
                int N = Integer.parseInt(br.readLine());
                sb = new StringBuilder();
                for (int i = 0; i < (int) Math.pow(3, N); i++) {
                    sb.append("-");
                }

                divideAndConquer(0, (int) Math.pow(3, N));

                System.out.println(sb);
            } catch (Exception e) {
                break;
            }
        }
    }

    public static void divideAndConquer(int start, int size) {
        if (size == 1) return;

        int newSize = size / 3;
        for (int i = start + newSize; i < start + 2 * newSize; i++) {
            sb.setCharAt(i, ' ');
        }

        divideAndConquer(start, newSize);
        divideAndConquer(start + 2 * newSize, newSize);
    }
}

문제

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

접근 방식

1. 암호문의 중간에서 삽입 혹은 삭제하는 명령어가 있기 때문에 삽입 및 삭제 연산이 자주 발생할 때 유리한 LinkedList 자료구조를 사용한다.

2. 각 명령어들을 `switch case`문을 사용하여 적절하게 분기 처리한다.

// [SWEA] 1230. 암호문3

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

// public
class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = 10;

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            LinkedList<String> passwords = new LinkedList<>();
            
            for (int i = 0; i < N; i++) {
                passwords.add(st.nextToken());
            }

            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int x, y;
            for (int i = 0; i < M; i++) {
                char command = st.nextToken().charAt(0);
                x = Integer.parseInt(st.nextToken());

                // 각 명령어에 따라 제어 과정을 나눈다.
                switch (command) {

                    // 명령어가 I(삽입)일 경우
                    case 'I':

                        // 앞에서부터 X번째 암호문 바로 다음에 y개의 암호문을 삽입한다.
                        y = Integer.parseInt(st.nextToken());
                        for (int j = 0; j < y; j++) {
                            String password = st.nextToken();
                            passwords.add(x, password);
                            x += 1;
                        }
                        break;
                    
                    // 명령어가 D(삭제)인 경우
                    case 'D':

                        // 앞에서부터 x번째 암호문 바로 다음부터 y개의 암호문을 삭제한다.
                        y = Integer.parseInt(st.nextToken());
                        for (int j = 0; j < y; j++) {
                            passwords.remove(x);
                        }
                        break;

                    // 명령어가 A(추가)인 경우
                    case 'A':

                        // 암호문 뭉치 맨 뒤에 x개의 암호문을 덧붙인다.
                        for (int j = 0; j < x; j++) {
                            passwords.add(st.nextToken());
                        }
                        break;
                    
                    default:
                        break;
                }
            }

            sb.append("#").append(tc).append(" ");

            // 수정된 결과의 처음 10개 암호문을 출력한다.
            for (int i = 0; i < 10; i++) {
                sb.append(passwords.get(i)).append(" ");
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }
}

문제 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXRSXf_a9qsDFAXS

접근 방법

1. M의 이진수 표현의 마지막 N개의 비트가 모두 켜져 있다면, (M + 1)는 2^N의 배수이다.

2. 따라서 (M + 1)가 2^N으로 나누어 떨어진다면 "ON"을 출력하고, 그렇지 않다면 "OFF"를 출력한다.

풀이

// [SWEA] 10726. 이진수 표현

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

// public
class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            sb.append("#").append(tc).append(" ").append((M + 1) % (1 << N) == 0 ? "ON" : "OFF").append("\n");
        }
        
        System.out.println(sb);
    }
}

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18_yw6I9MCFAZN

접근 방법

// [SWEA] 1288. 새로운 불면증 치료법

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

// public
class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 테스트 케이스의 수
        int T = Integer.parseInt(br.readLine());
        
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            // k번째에 센 양의 횟수
            int accNum = 0;

            // 비트연산을 통해 각 숫자가 저장되었는지를 확인할 수 있는 변수
            int numCnt = 0;

            // 0 ~ 9까지 모든 숫자를 탐색하였다면 numCnt는 1111111111(2)로, 1023이 될 것이다.
            // 즉 numCnt 값이 1023이 될 때까지 반복
            while (numCnt < 1023) {

                // accNum에 N을 더함.
                accNum += N;

                // curNum에 현재 누적값 추가
                int curNum = accNum;

                // 각 자리수를 순회하며
                while (curNum > 0) {

                    // 해당 자리수의 숫자에 해당하는 비트 위치와 numCnt를 OR 연산시킨다.
                    numCnt = numCnt | (1 << (curNum % 10));

                    curNum /= 10;
                }
            }
            
            // 0 ~ 9까지의 모든 숫자가 나왔을 때의 accNum을 출력한다.
            sb.append("#").append(tc).append(" ").append(accNum).append("\n");
        }

        System.out.println(sb);
    }
}