알고리즘 재활 15일차 - 11723, 1927, 5430번

운동도 못가겠어요 증말증말로

 

아 오늘 좀 후딱 풀었네

3문제 50분~

 

집합

 

 

출력되는건 check, toggle인 점만 확인하면 더 쉽게 풀 수 있었을거 같다.

비트마스킹으로 메모리 더 적게도 가능하겠다. 꼭 풀고 생각나

 

연산자설명
&	비트 단위 AND 연산 (비트가 모두 1이면 1 반환)
|	비트 단위 OR 연산 (비트 중 하나 이상 1이면 1 반환)
^	비트 단위 XOR 연산 (비트가 서로 다르면 1 반환)
~	비트 단위 NOT 연산 (0 -> 1, 1 -> 0 반환)
<<	비트 Left Shift 연산 (비트를 왼쪽으로 이동)
>>	비트 Right Shift 연산 (비트를 오른쪽으로 이동)

 

보니까 또 기억나네

 

커맨드 별로 기능을 나누어서 작성해주었다.

 

Set 으로 푼 코드 🔽🔽

 

import java.io.*;
import java.util.*;
 
public class Main { // 집합
    public static int M;
    public static Set<Integer> set = new HashSet<>();
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
 
            if (cmd.equals("all")) {
                for (int j = 1; j <= 20; j++) {
                    set.add(j);
                }
            } else if (cmd.equals("empty")) {
                set.clear();
            } else {
                int x = Integer.parseInt(st.nextToken());
 
                switch (cmd) {
                    case "add":
                        set.add(x);
                        break;
                    case "remove":
                        set.remove(x);
                        break;
                    case "check":
                        sb.append(set.contains(x) ? "1\n" : "0\n");
                        break;
                    case "toggle":
                        if (set.contains(x)) {
                            set.remove(x);
                        } else {
                            set.add(x);
                        }
                        break;
                }
            }
        }
 
        System.out.print(sb.toString());
    }
}
 

 

비트마스킹으로 푼 코드 🔽🔽

 

import java.io.*;
import java.util.*;
 
public class Main { // 집합 - 비트마스킹
    public static int M;
    public static int bitSet = 0; 
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        M = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
 
            if (cmd.equals("all")) {
                bitSet = (1 << 20) - 1; 
            } else if (cmd.equals("empty")) {
                bitSet = 0;
            } else {
                int x = Integer.parseInt(st.nextToken()) - 1; // 19까지 사용
                switch (cmd) {
                    case "add":
                        bitSet |= (1 << x);
                        break;
                    case "remove":
                        bitSet &= ~(1 << x);
                        break;
                    case "check":
                        sb.append((bitSet & (1 << x)) != 0 ? "1\n" : "0\n");
                        break;
                    case "toggle":
                        bitSet ^= (1 << x);
                        break;
                }
            }
        }
 
        System.out.print(sb.toString());
    }
}
 

 

 

이상하게 별로 차이 안나네.. 

두 코드를 비교하면 이정도로 차이가 난다.

효율 비교	HashSet 사용 코드	비트마스킹 사용 코드
메모리 사용량	높음 (각 원소마다 객체 오버헤드 발생)	낮음 (4바이트 고정)
시간 복잡도	평균 O(1), 최악 O(n)	O(1)
연산 속도	상대적으로 느림	매우 빠름
코드 복잡도	상대적으로 간단	조금 더 복잡 (비트 연산 이해 필요)

 

모쪼록~ 비트마스킹을 알고리즘에서는 처음 써본것 같다.

난이도 올려서도 풀어봐야지

---

최소 힙

 

 

0이 입력되면 현재까지 넣은 값중에서 가장 작은 값을 출력하면 되는 문제이다.

당연히 정렬을 계속하면서 출력하면 메모리 손해가 크므로 정렬된 큐인 우선순위 큐를 활용해 주었다.

우선순위 큐는 힙으로 구현되고 힙은 완전 이진트리 형태이다.

O(log₂n) 의 시간 복잡도를 가지므로 삽입, 삭제에도 용이.

 

 

import java.io.*;
import java.util.*;
 
public class Main { // 최소 힙
    public static int N;
    public static Set<Integer> set = new HashSet<>();
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> Pq = new PriorityQueue<>();
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int now = Integer.parseInt(st.nextToken());
            if(now == 0){
                if(Pq.isEmpty()){
                    sb.append("0").append("\n");
                }else{
                    sb.append(Pq.poll()).append("\n");
                }
            }else{
                Pq.add(now);
            }
        }
 
        System.out.print(sb.toString());
    }
}
 

 

자주 보는거 같구나 호호

---

AC

 

R 또는 D의 커맨드가 들어오고, 숫자 배열이 주어진다.

R은 배열 뒤집기 ex) 1,2,3 -> 3,2,1 

D는 Delete로 맨 앞 지워주는 커맨드이다.

모든 함수를 동작하고 남은 결과를 출력해주면 된다.

 

배열을 계속해서 R을 만날때마다 뒤집는건 비효율적이다.

따라서 양방향인 Deque을 사용해서 문제를 해결해줬다.

position이 정방향이면 앞에서 연산하고, 역방향이면 뒤에서 연산해주었다.

 

error의 경우 큐가 비어있음에도 D 입력이 들어오는 경우를 신경써주면 된다.

에러 발생 시 error를 StringBuilder에 넣어주고 for문을 탈출하게 해줬다.

배열이 존재하면 괄호로 덮어줘야하고, 출력의 경우 큐에 숫자가 남아있을때만  ',' 를 출력해주었다.

 

import java.io.*;
import java.util.*;
 
public class Main { // AC
    public static int T;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < T; i++) {
            boolean position = false; // false == 정방향, true == 역방향
            boolean error = false;
            String cmd = br.readLine();
            int N = Integer.parseInt(br.readLine());
            Deque<Integer> deque = new ArrayDeque<>();
 
            st = new StringTokenizer(br.readLine(), ",[]");
            while (st.hasMoreTokens()) {
                deque.offer(Integer.parseInt(st.nextToken()));
            }
 
            for (char c : cmd.toCharArray()) {
                if (c == 'R') {
                    position = !position;
                } else if (c == 'D') {
                    if (deque.isEmpty()) {
                        sb.append("error\n");
                        error = true;
                        break;
                    }
                    if (position) {
                        deque.pollLast();
                    } else {
                        deque.pollFirst();
                    }
                }
            }
 
            if (!error) {
                sb.append("[");
                while (!deque.isEmpty()) {
                    sb.append(position ? deque.pollLast() : deque.pollFirst());
                    if (!deque.isEmpty()) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }
 
        System.out.print(sb.toString());
    }
}