28279번: 덱 2

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다.

www.acmicpc.net

 

☕Language: Java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int cnt = Integer.parseInt(br.readLine());
 
        ArrayDeque<Integer> deque = new ArrayDeque<>();
 
        StringBuilder sb = new StringBuilder();
 
        while (cnt-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            switch (st.nextToken()) {
            case "1":
                deque.addFirst(Integer.parseInt(st.nextToken()));
                break;
            case "2":
                deque.addLast(Integer.parseInt(st.nextToken()));
                break;
            case "7":
                if (!deque.isEmpty()) {
                    sb.append(deque.peekFirst() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            case "8":
                if (!deque.isEmpty()) {
                    sb.append(deque.peekLast() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            case "3":
                if (!deque.isEmpty()) {
                    sb.append(deque.peekFirst() + "\n");
                    deque.removeFirst();
                } else {
                    sb.append("-1\n");
                }
                break;
            case "4":
                if (!deque.isEmpty()) {
                    sb.append(deque.peekLast() + "\n");
                    deque.removeLast();
                } else {
                    sb.append("-1\n");
                }
                break;
            case "5":
                sb.append(deque.size() + "\n");
                break;
            case "6":
                sb.append((deque.isEmpty() ? "1" : "0") + "\n");
                break;
            }
 
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

Deque: Double-Ended Queue

    - 큐의 양쪽으로 요소의 삽입과 삭제를 수행할 수 있는 자료구조

 

 

 

🔗 소스 코드
GitHub

 

 

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 1764번 듣보잡 문제 풀이 (Success)  (0) 2023.09.04
[BaekJoon] 2164번 카드2 문제 풀이 (Success)  (0) 2023.09.03
[BaekJoon] 18258번 큐2 문제 풀이 (Success)  (0) 2023.08.31
[BaekJoon] 1158번 요세푸스 문제 풀이 (Success)  (0) 2023.08.29
[BaekJoon] 10845번 큐 문제 풀이 (Success)  (0) 2023.08.28
 

18258번: 큐 2

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

☕Language: Java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int cnt = Integer.parseInt(br.readLine());
 
        ArrayDeque<Integer> queue = new ArrayDeque<>();
 
        StringBuilder sb = new StringBuilder();
 
        while (cnt-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            switch (st.nextToken()) {
            case "push":
                queue.add(Integer.parseInt(st.nextToken()));
                break;
            case "pop":
                if (!queue.isEmpty()) {
                    sb.append(queue.element() + "\n");
                    queue.remove();
                } else {
                    sb.append("-1\n");
                }
                break;
            case "size":
                sb.append(queue.size() + "\n");
                break;
            case "empty":
                sb.append((queue.isEmpty() ? "1" : "0") + "\n");
                break;
            case "front":
                if (!queue.isEmpty()) {
                    sb.append(queue.peek() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            case "back":
                if (!queue.isEmpty()) {
                    sb.append(queue.peekLast() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            }
 
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

10845번 큐 문제 풀이와 동일한 문제로, 자세한 풀이는 참고 자료 참조🤓

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[BaekJoon] 10845번 큐 문제 풀이 (Success)

10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에

hj0216.tistory.com

 

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 2164번 카드2 문제 풀이 (Success)  (0) 2023.09.03
[BaekJoon] 28279번 덱2 문제 풀이 (Success)  (0) 2023.09.01
[BaekJoon] 1158번 요세푸스 문제 풀이 (Success)  (0) 2023.08.29
[BaekJoon] 10845번 큐 문제 풀이 (Success)  (0) 2023.08.28
[BaekJoon] 28278번 스택2 문제 풀이 (Success)  (0) 2023.08.27
 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

☕Language: Java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        List<Integer> list = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }
 
        StringBuffer sb = new StringBuffer();
 
        int idx = 0;
        for (int i = 0; i < N; i++) {
            idx = idx + K - 1 > list.size() ? idx + K - 1 - list.size() : idx + K - 1;
            while (idx >= list.size()) {
                idx = idx - list.size();
            }
            sb.append(list.get(idx));
            if (i != (N - 1)) {
                sb.append(", ");
            }
            list.remove(idx);
        }
 
        bw.write("<" + sb + ">");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

1. for (int i = 0; i < N; i++) { ... }

    - list에 1부터 N까지 대입

 

2. idx = idx + K - 1 > list.size() ? idx + K - 1 - list.size() : idx + K - 1;

    - 배열은 0부터 시작하므로 (K-1)값을 기준으로 확인

        - list 크기보다 크면 list를 이미 한바퀴 순회한 것으므로 list 크기만큼 빼주기

        - list 크기보다 작으면 그대로 idx에 K-1 더하기

 

3. while (idx >= list.size()) { ... }

    - idx가 list 사이즈보다 크지 않게 반복문 실행

 

4. sb.append(list.get(idx));

    - list에서 K 위치값(배열의 위치이므로 K-1값) 호출

 

5. if (i != (N - 1)) { ... }

    - 마지막 값이 아닐 경우에만 반점(,) 추가

 

6. list.remove(idx);

    - list idx값 호출 후 제거

 

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        Queue<Integer> queue = new LinkedList<>();
 
        for (int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
 
        StringBuilder sb = new StringBuilder("<");
 
        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.add(queue.poll());
            }
            sb.append(queue.poll() + ", ");
        }
 
        sb.append(queue.poll() + ">");
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

1. queue.add(queue.poll());

    - poll(): queue의 첫 번째 요소 출력 및 제거

    - queue.add(...): K 이전의 숫자 제거 후, K 이후에 재 입력

 

2. sb.append(queue.poll() + ", ");

    - K번째 숫자 출력 및 제거

 

3. sb.append(queue.poll() + ">");

    - size가 1일 때는 queue 마지막 요소 출력 및 제거

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[BOJ] 백준 1158번 : 요세푸스 문제 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1

steady-coding.tistory.com

 

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 28279번 덱2 문제 풀이 (Success)  (0) 2023.09.01
[BaekJoon] 18258번 큐2 문제 풀이 (Success)  (0) 2023.08.31
[BaekJoon] 10845번 큐 문제 풀이 (Success)  (0) 2023.08.28
[BaekJoon] 28278번 스택2 문제 풀이 (Success)  (0) 2023.08.27
[BaekJoon] 10828번 스택 문제 풀이 (Success)  (0) 2023.08.26
 

10845번: 큐

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

☕Language: Java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int cnt = Integer.parseInt(br.readLine());
 
        Queue<Integer> queue = new LinkedList<>();
 
        StringBuffer sb = new StringBuffer();
 
        while (cnt-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            switch (st.nextToken()) {
            case "push":
                queue.add(Integer.parseInt(st.nextToken()));
                break;
            case "pop":
                if (!queue.isEmpty()) {
                    sb.append(queue.element() + "\n");
                    queue.remove();
                } else {
                    sb.append("-1\n");
                }
                break;
            case "size":
                sb.append(queue.size() + "\n");
                break;
            case "empty":
                sb.append((queue.isEmpty() ? "1" : "0") + "\n");
                break;
            case "front":
                if (!queue.isEmpty()) {
                    sb.append(queue.peek() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            case "back":
                if (!queue.isEmpty()) {
                    sb.append(queue.toArray()[queue.size() - 1] + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            }
 
        }
 
        bw.write(sb + "");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

1. case "back":

    - 가장 뒤에 들어있는 요소를 출력하기 위해 array로 변환

 

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        Queue<Integer> queue = new LinkedList<>();
 
        StringBuilder sb = new StringBuilder();
 
        int last = 0;
        while (N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            switch (st.nextToken()) {
            case "push":
                last = Integer.parseInt(st.nextToken());
                queue.add(last);
                break;
            case "pop":
                sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\n");
                break;
            case "size":
                sb.append(queue.size()).append("\n");
                break;
            case "empty":
                sb.append((queue.isEmpty() ? 1 : 0)).append("\n");
                break;
            case "front":
                sb.append(queue.isEmpty() ? -1 : queue.peek()).append("\n");
                break;
            case "back":
                sb.append(queue.isEmpty() ? -1 : last).append("\n");
                break;
            }
 
        }
 
        bw.write(sb + "");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

1. int last = 0;

    - 최종값 출력을 위한 last 변수 선언

 

2. queue.poll()

    -  큐의 첫번째 요소 반환 및 삭제

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[알고리즘] 백준 - 10845 ( 큐 ) / 자바

스택이랑 거의 동일한 문제 back만 잘 처리해 주면 된다.

velog.io

 

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 18258번 큐2 문제 풀이 (Success)  (0) 2023.08.31
[BaekJoon] 1158번 요세푸스 문제 풀이 (Success)  (0) 2023.08.29
[BaekJoon] 28278번 스택2 문제 풀이 (Success)  (0) 2023.08.27
[BaekJoon] 10828번 스택 문제 풀이 (Success)  (0) 2023.08.26
[BaekJoon] 10820번 문자열 분석 문제 풀이 (Success)  (0) 2023.08.25
 

28278번: 스택 2

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다.

www.acmicpc.net

 

☕Language: Java

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int cnt = Integer.parseInt(br.readLine());
 
        Stack<Integer> stack = new Stack<>();
 
        StringBuffer sb = new StringBuffer();
 
        while (cnt-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
            switch (st.nextToken()) {
            case "1":
                stack.push(Integer.parseInt(st.nextToken()));
                break;
            case "5":
                if (!stack.isEmpty()) {
                    sb.append(stack.lastElement() + "\n");
                } else {
                    sb.append("-1\n");
                }
                break;
            case "3":
                sb.append(stack.size() + "\n");
                break;
            case "4":
                sb.append((stack.isEmpty() ? "1" : "0") + "\n");
                break;
            case "2":
                if (!stack.isEmpty()) {
                    sb.append(stack.lastElement() + "\n");
                    stack.pop();
                } else {
                    sb.append("-1\n");
                }
                break;
            }
 
        }
 
        bw.write(sb + "");
 
        bw.flush();
        bw.close();
 
    }
 
}
 
 

🤔 해설

10828번 스택 문제 풀이와 동일한 문제로, 자세한 풀이는 참고 자료 참조🤓

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

 

[BaekJoon] 10828번 스택 문제 풀이 (Success)

10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제

hj0216.tistory.com

 

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[BaekJoon] 1158번 요세푸스 문제 풀이 (Success)  (0) 2023.08.29
[BaekJoon] 10845번 큐 문제 풀이 (Success)  (0) 2023.08.28
[BaekJoon] 10828번 스택 문제 풀이 (Success)  (0) 2023.08.26
[BaekJoon] 10820번 문자열 분석 문제 풀이 (Success)  (0) 2023.08.25
[BaekJoon] 9093번 단어 뒤집기 문제 풀이 (Success)  (0) 2023.08.24

티스토리툴바