www.acmicpc.net/problem/5397

 

5397번: 키로거

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이

www.acmicpc.net

두 개의 덱을 이용하여 해결할 수 있습니다.

덱을 두 개 사용한 이유는 커서의 위치를 조정해주기 위함입니다.

저는 커서 좌, 우를 나누는 left와 right 덱을 선언하여 커서는 무조건 left를 가리키게 유지하였습니다.

 

우선 입력으로 '<', '>', '-' 그리고 나머지 문자가 주어집니다.

 

<이 주어지면 left에서 가장 뒤에있는 문자를 right 앞으로 push합니다. (left가 비어있으면 패스)

>이 주어지면 right에서 가장 앞에있는 문자를 left 뒤로 push합니다. (right가 비어있으면 패스)

-이 주어지면 left에서 가장 뒤에있는 문자를 pop합니다. (left가 비어있으면 패스)

나머지 문자가 주어지면 커서를 left로 유지해야하기 때문에 left 뒤로 push합니다.

 

이 과정이 끝나면 right에 있는 문자들을 앞에서부터 순서대로 left의 뒤로 차례대로 push하여 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Deque<Character> left, right;
    static char ch[];
 
    static void print() {
        while(!left.isEmpty()) {
            sb.append(left.peekFirst());
            left.removeFirst();
        }
        
        sb.append("\n");
    }
    
    static void func() {
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '<') {
                if (left.isEmpty())
                    continue;
                right.addFirst(left.peekLast());
                left.removeLast();
            } else if (ch[i] == '>') {
                if (right.isEmpty())
                    continue;
                left.addLast(right.peekFirst());
                right.removeFirst();
            } else if (ch[i] == '-') {
                if (left.isEmpty())
                    continue;
                left.removeLast();
            } else
                left.addLast(ch[i]);
        }
        
        while(!right.isEmpty()) {
            left.addLast(right.peekFirst());
            right.removeFirst();
        }
    }
 
    static void input() throws Exception {
        left = new ArrayDeque<>();
        right = new ArrayDeque<>();
 
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            func();
            print();
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 3190 뱀  (0) 2021.02.02
boj 2346 풍선 터뜨리기  (0) 2021.02.02
boj 10866 덱  (0) 2021.02.02
boj 11000 강의실 배정  (0) 2021.02.01
boj 1966 프린터 큐  (0) 2021.02.01

www.acmicpc.net/problem/10866

 

10866번: 덱

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

www.acmicpc.net

덱의 기능들을 연습해볼 수 있는 기본적인 문제입니다.

 

덱은 push와 pop이 앞, 뒤로 모두 가능한 자료구조입니다.

 

push_front X : X를 덱 앞으로 push

push_back X : X를 덱 뒤로 push

pop_front : 덱의 가장 앞에있는 정수를 pop, 만약 덱이 비어있으면 -1 출력

pop_back : 덱의 가장 뒤에있는 정수를 pop, 만약 덱이 비어있으면 -1 출력

size : 덱의 크기 출력

empty : 덱이 비어있으면 1, 아니면 0을 출력

front : 덱의 가장 앞에있는 정수 출력, 만약 덱이 비어있으면 -1 출력

back : 덱의 가장 뒤에있는 정수 출력, 만약 덱이 비어있으면 -1 출력

 

위의 명령이 입력되는대로 수행해주시면 됩니다.

 

 

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Deque<Integer> dq = new ArrayDeque<>();
    static int N;
 
    static void push_front(int x) {
        dq.addFirst(x);
    }
 
    static void push_back(int x) {
        dq.addLast(x);
    }
 
    static void pop_front() {
        if (dq.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(dq.peekFirst() + "\n");
        dq.removeFirst();
    }
 
    static void pop_back() {
        if (dq.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(dq.peekLast() + "\n");
        dq.removeLast();
    }
 
    static void size() {
        sb.append(dq.size() + "\n");
    }
 
    static void empty() {
        if (dq.isEmpty())
            sb.append("1\n");
        else
            sb.append("0\n");
    }
 
    static void front() {
        if (dq.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(dq.peekFirst() + "\n");
    }
 
    static void back() {
        if (dq.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(dq.peekLast() + "\n");
    }
 
    static void input() throws Exception {
        String type;
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = st.nextToken();
 
            if ("push_front".equals(type)) {
                x = Integer.parseInt(st.nextToken());
                push_front(x);
            } else if ("push_back".equals(type)) {
                x = Integer.parseInt(st.nextToken());
                push_back(x);
            } else if ("pop_front".equals(type))
                pop_front();
            else if ("pop_back".equals(type))
                pop_back();
            else if ("size".equals(type))
                size();
            else if ("empty".equals(type))
                empty();
            else if ("front".equals(type))
                front();
            else
                back();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 2346 풍선 터뜨리기  (0) 2021.02.02
boj 5397 키로거  (0) 2021.02.02
boj 11000 강의실 배정  (0) 2021.02.01
boj 1966 프린터 큐  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01

www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

www.acmicpc.net

수업 시작시간과 종료시간이 주어집니다.

이 정보들을 가지고 모든 수업을 진행하는데 최소의 강의실을 사용해야합니다.

 

저는 우선순위 큐를 이용하였습니다.

일단 수업시간 정보를 2차원배열을 통해 [시작시간][종료시간]으로 저장하였고,

시작 시간 빠른 순, 시작 시간 같으면 종료 시간 빠른 순으로 정렬하였습니다.

 

큐에는 수업 종료시간만 저장해주면 되고, 큐에 넣은 종료시간과 다음 수업 시작시간을 비교합니다.

종료시간보다 다음 시작시간이 빠르면 같은 강의실을 사용할 수 없으므로 큐에 push합니다.

종료시간보다 다음 시작시간이 같거나 느리면 같은 강의실을 사용할 수 있으므로 큐를 pop하고 다음 종료시간을 push합니다.

 

이 과정을 반복하여 큐의 크기가 사용중인 강의실이며, 이를 출력하시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static int list[][];
    static int N;
 
    static void func() {
        q.add(list[0][1]);
        for (int i = 1; i < N; i++) {
            int s = list[i][0];
            int e = list[i][1];
 
            if (q.peek() <= s) {
                q.remove();
                q.add(e);
            } else
                q.add(e);
        }
 
        System.out.println(q.size());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] < b[0])
                    return -1;
                else if (a[0] == b[0]) {
                    if (a[1] < b[1])
                        return -1;
                    else
                        return 1;
                } else
                    return 1;
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

 

 

 

그리고.... Arrays.sort로 list배열을 정렬할 때 Comparator을 사용하여 시간 순으로 정렬하고자 하였습니다.

하지만 compare함수 if에 <=라는 기호를 넣으니 런타임에러가 떴습니다... 신기하게도 <로 바꾸니 AC를 받더라고요...

저번에도 이거때문에 시간좀 많이 날렸었는데 참 신기합니다.. 자바....

공부가 좀 더 많이 필요하겠다는 생각이 드는 하루네요..

'algorithm > data-structure' 카테고리의 다른 글

boj 5397 키로거  (0) 2021.02.02
boj 10866 덱  (0) 2021.02.02
boj 1966 프린터 큐  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01

www.acmicpc.net/problem/1966

 

1966번: 프린터 큐

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에

www.acmicpc.net

큐에 저장되어있는 중요도가 높은 순서대로 pop을 해야합니다.

저는 인덱스와 중요도 관리를 해주기 위해 큐에 배열(중요도, 인덱스)을 넣었습니다.

 

그리고 중요도가 입력되면 현재 최댓값을 저장하기 위해 몇번 나왔는지(num[])와 최댓값 (maxp)를 사용하였습니다.

그리고 다음과 같은 과정을 수행합니다.

1. 큐에서 원소하나를 pop

2. pop한 원소가 현재 최대 중요도인지 확인 -> 최대 중요도가 아니면 다시 큐에 push합니다.

3. 최대 중요도이면 인덱스가 M과 일치하는지 확인 -> 일치하면 그대로 출력하고 리턴합니다.

4. 인덱스가 맞지 않으면 num[x]을 1 내리고, 만약 num[x]이 0이 되었을 때 다음 최댓값을 꺼내옵니다.

 

이 과정을 반복하여 M번 인덱스가 몇 번째로 pop되는지 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Queue<int[]> q = new LinkedList<>();
    static int num[] = new int[10];
    static int N, M, maxp;
 
    static void func() {
        while (true) {
            int x = q.peek()[0];
            int idx = q.peek()[1];
 
            q.remove();
            if (x != maxp)
                q.add(new int[] { x, idx });
            else {
                if (idx == M) {
                    sb.append(N - q.size() + "\n");
                    return;
                }
                num[x]--;
                if (num[x] == 0) {
                    for (int i = x; i >= 1; i--) {
                        if (num[i] > 0) {
                            maxp = i;
                            break;
                        }
                    }
                }
            }
        }
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(st.nextToken());
            q.add(new int[] { x, i });
            num[x]++;
            maxp = Math.max(maxp, x);
        }
    }
 
    static void clear() {
        maxp = 0;
        for (int i = 1; i <= 9; i++)
            num[i] = 0;
        while (!q.isEmpty())
            q.remove();
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            func();
            clear();
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 10866 덱  (0) 2021.02.02
boj 11000 강의실 배정  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01

www.acmicpc.net/problem/2164

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

큐에 1부터 N까지 순서대로 push가 된 상태로 있습니다.

 

여기서 다음과 같은 동작을 카드가 하나 남을때까지 반복합니다.

1. 큐의 가장 위에있는 숫자를 버린다.

2. 큐의 가장 위에있는 숫자를 큐의 맨 뒤로 보내고 삭제한다.

 

큐의 크기가 1이 되면 break을 하고 남아있는 수를 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<Integer> q = new LinkedList<>();
    static int N;
 
    static void func() {
        while (true) {
            if (q.size() == 1)
                break;
            
            q.remove();
            q.add(q.peek());
            q.remove();
        }
        
        System.out.println(q.peek());
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            q.add(i);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 11000 강의실 배정  (0) 2021.02.01
boj 1966 프린터 큐  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31

www.acmicpc.net/problem/10845

 

10845번: 큐

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

www.acmicpc.net

큐의 여러가지 기능을 사용해 볼 수 있는 간단한 문제입니다.

 

입력으로 6개의 명령이 주어집니다.

push X : 정수 X를 push

pop : q.peek()를 출력 후 pop, 만약 큐가 비어있으면 -1 출력

size : 큐의 크기를 출력

empty : 큐가 비어있으면 1, 아니면 0 출력

front : q.peek()를 출력, 만약 큐가 비어있으면 -1 출력

back : 큐에 가장 최근에 push된 정수 출력, 만약 큐가 비어있으면 -1 출력

 

큐가 비어있으면 -1을 출력해야하는 예외 처리만 신경써주시면 되겠습니다.

 

 

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
80
81
82
83
84
85
86
87
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Queue<Integer> q = new LinkedList<>();
    static int N, last;
 
    static void push(int x) {
        q.add(x);
    }
 
    static void pop() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(q.peek() + "\n");
        q.remove();
    }
 
    static void size() {
        sb.append(q.size() + "\n");
    }
 
    static void empty() {
        if (q.isEmpty())
            sb.append("1\n");
        else
            sb.append("0\n");
    }
 
    static void front() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(q.peek() + "\n");
    }
 
    static void back() {
        if (q.isEmpty()) {
            sb.append("-1\n");
            return;
        }
 
        sb.append(last + "\n");
    }
 
    static void input() throws Exception {
        String type;
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = st.nextToken();
 
            if ("push".equals(type)) {
                x = Integer.parseInt(st.nextToken());
                push(x);
                last = x;
            } else if ("pop".equals(type))
                pop();
            else if ("size".equals(type))
                size();
            else if ("empty".equals(type))
                empty();
            else if ("front".equals(type))
                front();
            else
                back();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 1966 프린터 큐  (0) 2021.02.01
boj 2164 카드2  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31
boj 1927 최소 힙  (0) 2021.01.31

www.acmicpc.net/problem/1655

 

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

수빈이가 동생에게 숫자를 하나씩 부를 때마다 동생이 처음에 말한 수부터 현재 말한 수까지의 중간 값을 출력해야합니다.

 

이 문제는 우선순위 큐로 해결할 수 있습니다.

저는 우선순위 큐 2개(최대 힙, 최소 힙 각각 1개)를 사용하였습니다.

최대 힙에는 작은값들, 최소 힙에는 큰 값들을 저장합니다. 그리고 출력은 최대힙에서 가장 작은 수를 출력합니다.

 

출력을 최대 힙으로 사용하기 때문에 최대 힙의 크기를 더 크게 유지시킵니다.

하지만 중간 값을 구해야하기 때문에 최대 힙과 최소 힙의 크기를 같게 하거나 최대 힙의 크기가 1만큼 더 커야합니다.

 

우선 최대 힙이 비어있으면 최대 힙에 저장합니다.

그리고 최대 힙의 크기가 최소 힙과 같으면 최대 힙에 add

최소 힙의 크기가 더 작으면 최소 힙에 add를 해줍니다.

 

이 과정 이후에 최소 힙의 가장 작은 값이 최대 힙의 가장 큰 값보다 작으면 두 수를 교환합니다.

 

마지막에는 최대 힙에서 가장 큰 수를 출력하면 됩니다.

 

 

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.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[];
    static int N;
 
    static void func() {
        PriorityQueue<Integer> maxq = new PriorityQueue<>();
        PriorityQueue<Integer> minq = new PriorityQueue<>();
 
        for (int i = 0; i < N; i++) {
            int x = list[i];
 
            if (maxq.isEmpty()) {
                maxq.add(-x);
                sb.append(-maxq.peek() + "\n");
                continue;
            }
 
            if (maxq.size() == minq.size())
                maxq.add(-x);
            else
                minq.add(x);
 
            if (-maxq.peek() > minq.peek()) {
                int a = -maxq.peek();
                int b = -minq.peek();
                maxq.remove();
                minq.remove();
 
                maxq.add(b);
                minq.add(a);
            }
 
            sb.append(-maxq.peek() + "\n");
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 2164 카드2  (0) 2021.02.01
boj 10845 큐  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31
boj 1927 최소 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26

www.acmicpc.net/problem/1244

 

1244번: 스위치 켜고 끄기

첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩

www.acmicpc.net

1(남학생)일 경우 받은 번호의 모든 배수 번호의 스위치 상태를 바꿉니다.

2(여학생)일 경우 받은 번호를 중점으로 좌우 상태가 같은 스위치 상태를 바꿉니다.

 

1의 경우에는 x부터 N까지 x를 더하면서 상태를 변경하였고,

2의 경우에는 인덱스 두개를 사용하여 비교해가면서 상태를 변경하였습니다.

 

출력은 한 줄에 20개씩 해야합니다.

저는 문제를 제대로 안읽어서 WA를 받았습니다 ㅠㅠ

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], student[][];
    static int N, M;
 
    static void solve1(int x) {
        for (int i = x; i <= N; i += x) {
            list[i] = 1 - list[i];
        }
    }
 
    static void solve2(int x) {
        int l = x - 1;
        int r = x + 1;
        list[x] = 1 - list[x];
        while (l >= 1 && r <= N) {
            if (list[l] == list[r]) {
                list[l] = 1 - list[l];
                list[r] = 1 - list[r];
                l--;
                r++;
            } else
                break;
        }
    }
 
    static void func() {
        for (int i = 0; i < M; i++) {
            int type = student[i][0];
            int x = student[i][1];
 
            if (type == 1)
                solve1(x);
            else
                solve2(x);
        }
    }
 
    static void print() {
        for (int i = 1; i <= N; i++) {
            System.out.print(list[i] + " ");
            if (i % 20 == 0)
                System.out.println();
        }
        System.out.println();
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        student = new int[M][2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            student[i][0] = Integer.parseInt(st.nextToken());
            student[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

'algorithm > Implementation' 카테고리의 다른 글

boj 16918 봄버맨  (0) 2021.02.17
boj 16935 배열 돌리기 3  (0) 2021.02.10
boj 1914 하노이 탑  (0) 2021.02.07
boj 11729 하노이 탑 이동 순서  (0) 2021.02.07
boj 20127 Y-수열  (0) 2021.01.22

www.acmicpc.net/problem/15740

 

15740번: A+B - 9

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

자바 공부하다가 BigInteger라는 객체가 있는걸 알았습니다..

존재를 까먹기 전에 포스팅이라도 하려고 급하게 문제를 풀었습니다..

 

이 문제는 A+B를 출력하는 매우 간단한 문제이지만 입력으로 주어지는 수가 -10^10000 ~ 10^10000이라서

int, long으로는 해결할 수 없습니다. 그래서 BigInteger를 사용해야 합니다.

BigInteger는 일반적인 +, -와 같은 연산은 불가능하며,

add(덧셈), subtract(뺄셈), multiply(곱셈), divide(나눗셈), remainder(나머지)와 같은 내부 메소드를 사용해야합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static BigInteger A, B;
    
    static void input() throws Exception{
        st = new StringTokenizer(br.readLine());
        
        A = new BigInteger(st.nextToken());
        B = new BigInteger(st.nextToken());
    }
    
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(A.add(B));
    }
}
 cs

 

 

 

 

 

그리고... 파이썬 코드입니다.

1
2
3
4
x, y = input().split()
x = int(x)
y = int(y)
print(x + y)
 cs

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

너무 간단한데요;;

 

C++로 BigInteger를 직접 구현했던 때가 기억이 납니다 ㅎㅎ;;

 

'algorithm > Math' 카테고리의 다른 글

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 1837 암호제작  (0) 2021.02.04
boj 1002 터렛  (0) 2021.01.27

www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

우선순위 큐를 연습하기 위해 두번째 힙 문제를 풀어봤습니다.

 

앞에서 포스팅했던 PriorityQueue는 작은 값이 peek()으로 온다고 하였습니다.

하지만 이 문제는 최대 힙을 구하는 문제입니다.

 

입력으로 주어지는 값들을 음수화해서 큐에 넣어주면 가장 큰 값이 가장 작은 값이 됩니다.

출력할 때도 -peek()을 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static int N, x;
 
    static void solve() {
        if (x == 0) {
            if (q.isEmpty()) {
                sb.append("0\n");
                return;
            }
 
            sb.append(-q.peek() + "\n");
            q.remove();
            return;
        }
 
        q.add(-x);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
 
            solve();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 10845 큐  (0) 2021.02.01
boj 1655 가운데를 말해요  (0) 2021.02.01
boj 1927 최소 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26
boj 2504 괄호의 값  (0) 2021.01.26

www.acmicpc.net/problem/1927

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

우선순위 큐를 연습하기 위해 간단한 힙 문제를 풀어보았습니다.

 

최소힙은 PriorityQueue로 간단하게 해결할 수 있습니다.

PriorityQueue는 가장 작은 값이 peek()으로 오기때문에

0이 아니면 그대로 add,

0이 오면 peek() 값을 출력해주시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static int N, x;
 
    static void solve() {
        if (x == 0) {
            if (q.isEmpty()) {
                sb.append("0\n");
                return;
            }
 
            sb.append(q.peek() + "\n");
            q.remove();
            return;
        }
 
        q.add(x);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
 
            solve();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 1655 가운데를 말해요  (0) 2021.02.01
boj 11279 최대 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26
boj 2504 괄호의 값  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26

www.acmicpc.net/problem/15666

 

15666번: N과 M (12)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과M 마지막 문제입니다.

 

11번과 다른점은 수열을 비내림차순으로 골라야한다는 점입니다.

그래서 재귀함수를 돌릴 때 이전에 고른 인덱스 관리를 해주어야 합니다.

 

 

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.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list, ans;
    static Set<ArrayList<Integer>> s = new HashSet<>();
    static int N, M;
 
    static void dfs(int idx, int cnt) {
        if (cnt == M) {
            if (s.contains(ans))
                return;
 
            s.add(ans);
            for (int i = 0; i < ans.size(); i++) {
                sb.append(ans.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = idx; i < N; i++) {
            int x = list.get(i);
 
            ans.add(x);
            dfs(i, cnt + 1);
            ans.remove(cnt);
        }
    }
 
    static void input() throws Exception {
        list = new ArrayList<>();
        ans = new ArrayList<>();
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(st.nextToken());
            list.add(x);
        }
 
        Collections.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 1068 트리  (0) 2021.02.09
boj 9202 Boggle  (0) 2021.02.02
boj 15665 N과 M (11)  (0) 2021.01.30
boj 15664 N과 M (10)  (0) 2021.01.30
boj 15663 N과 M (9)  (0) 2021.01.28

+ Recent posts

티스토리툴바