문제

 

풀이

입력에서 주어지는 N과 숫자의 구성이 같으면서 더 큰수 라고 한다면 순열 조합 문제라는 것을 떠올리실 수 있습니다.

숫자 구성을 모두 사용해야 하므로 이 문제는 순열입니다.

 

정답이 반드시 있는 경우만 입력으로 주어지므로 54321 처럼 다음 순열이 없는 경우는 없습니다.

따라서 예외 처리 없이 다음 순열을 구해주시기만 하면 됩니다.

C++에는 algorithm 라이브러리에서 next_permutation 메소드를 지원해주기 때문에 편하게 해결할 수 있었습니다.

 

코드

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string N;
 
void func() {
    next_permutation(N.begin(), N.end());
    cout << N << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22

https://www.acmicpc.net/problem/8330

 

수열이 a1, a2, ..., an 으로 주어졌을때 1 ~ ai 범위의 숫자를 적절하게 골라서 1 ~ N의 수가 하나씩 등장하도록 만들어야 합니다.

 

5
3 4 3 2 5

즉 이런 수열이 주어졌을 때

a1은 1 ~ 3 중에서 2

a2는 1 ~ 4 중에서 4

a3은 1 ~ 3 중에서 3

a4는 1 ~ 2 중에서 1

a5는 1 ~ 5 중에서 5

이렇게 골라서 1 ~ N까지 하나씩 등장하도록 순열을 만들 수 있습니다.

그리고 수열을 M번 수정하여 각각 수정된 수열에서도 위처럼 1 ~ N을 만들 수 있는지 구하는 문제입니다.

 

이 문제에서 저는 Segment Tree Lazy를 사용했고, 트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

1 ~ 5가 있다면

1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있습니다.

5 5 5 5 5가 입력된다면 5에서 수를 5번 고른다는 뜻입니다.

만약 4 4 4 4 4가 입력된다면 5개의 4에서 1 ~ 5를 하나씩 만들 수가 없게 되는거죠.

그렇게 i ~ N을 +1씩 업데이트를 해주고, 각각 노드에서의 최솟값으로 갱신하도록 합니다.

 

그 다음에는 최초로 주어진 수열에서 1 ~ N을 만들 수 있는지 먼저 확인합니다.

list[i]를 사용한게 되기 때문에 list[i] ~ N의 범위에 -1로 업데이트를 시켜줍니다.

트리를 최솟값으로 저장한 이유는 이 연산 과정에서 해당 값의 카운트가 음수인 경우를 빠르게 캐치하기 위해서입니다.

수열의 모든 수를 대상으로 업데이트가 끝난다면 query 함수를 이용하여 트리의 최솟값을 가져옵니다.

최솟값이 0 이상이면 순열을 만들 수 있고, 음수면 만들 수 없습니다.

 

다음 할 작업은 idx번째 수를 x로 변경하는 것입니다.

처음에는 위에서 -1로 업데이트를 한걸 되돌려야 하는지 고민했었는데 결과적으로 시간초과가 뜨더라고요!

N은 20만, M은 50만이기 때문에 시간초과가 당연한거였습니다.

20만개의 수를 50만번 업데이트 해야되니까요.. ㅎ

 

좀더 고민했을때는 트리에는 수열에 대한 카운팅이 각각 진행된 상태였고,

어차피 업데이트되는 idx번째 수에 대해서만 카운팅을 바꿔주면 된다는 결론이 나왔습니다.

그래서 수를 업데이트 하기 전에 기존 list[idx]의 범위에 대한 업데이트를 +1로 진행해주고,

새로운 값인 x의 범위에 대한 업데이트를 -1으로 진행해주면 새로운 수열에서의 카운팅 작업이 완료되는 것입니다.

마지막에는 업데이트된 트리의 최솟값을 가져와서 0 이상이면 `TAK`을, 음수면 `NIE`를 출력해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
 
int list[MAX];
int tree[MAX << 2];
int lazy[MAX << 2];
int N, M;
 
void lazyUpdate(int node, int l, int r) {
    if (!lazy[node]) return;
    tree[node] += lazy[node];
    if (l != r) {
        lazy[node << 1] += lazy[node];
        lazy[(node << 1) + 1] += lazy[node];
    }
    lazy[node] = 0;
}
 
int update(int node, int l, int r, int s, int e, int diff) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return tree[node];
    if (s <= l && r <= e) {
        lazy[node] += diff;
        lazyUpdate(node, l, r);
        return tree[node];
    }
 
    int m = (l + r) >> 1;
    return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
 
int query(int node, int l, int r, int s, int e) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return 0;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        update(1, 1, N, i, N, 1);
    }
 
    for (int i = 0; i < N; i++) {
        update(1, 1, N, list[i], N, -1);
    }
}
 
void print() {
    if (query(1, 1, N, 1, N) >= 0) cout << "TAK\n";
    else cout << "NIE\n";
}
 
void func() {
    init();
    print();
 
    int idx, x;
    while (M--) {
        cin >> idx >> x;
        update(1, 1, N, list[idx - 1], N, 1);
        update(1, 1, N, x, N, -1);
        list[idx - 1] = x;
        print();
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    cin >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 4442 빌보의 생일  (0) 2024.08.01
boj 1517 버블 소트  (0) 2024.06.16
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

https://www.acmicpc.net/problem/9081

 

9081번: 단어 맞추기

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알

www.acmicpc.net

문자열이지만 순열에 더 가까운 문제입니다.

주어진 단어의 사전 순으로 바로 다음 단어를 출력하는 문제로, next_permutation을 이용하였습니다.

next_permutation으로 다음 순열을 구하고, 출력하면 됩니다.

만약 마지막 단어라서 다음 순열을 구하지 못하더라도 주어진 단어를 유지하므로 그냥 출력해줍니다.

c++ 내장의 next_permutation을 사용하면 됐지만 직접 구현해보았습니다.

 

 

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
#include <iostream>
#include <string>
using namespace std;
 
string str;
int N;
 
bool nextPermutation() {
    int i = N - 1;
 
    while (i > 0 && str[i - 1] >= str[i]) {
        i--;
    }
 
    if (!i) return false;
 
    int j = N - 1;
    while (str[i - 1] >= str[j]) j--;
 
    swap(str[i - 1], str[j]);
 
    int k = N - 1;
    while (i < k) swap(str[i++], str[k--]);
 
    return true;
}
 
void func() {
    nextPermutation();
 
    cout << str << '\n';
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

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

boj 10453 문자열 변환  (0) 2024.07.24
boj 10096 세 친구  (0) 2021.01.29

https://www.acmicpc.net/problem/1849

 

1849번: 순열

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라

www.acmicpc.net

사탕 상자 문제와 비슷한 방법인 구간합을 이용하여 해결하였습니다.

https://emoney96.tistory.com/93 (사탕 상자 문제풀이)

 

먼저 1 ~ N 만큼의 리프노드가 모두 1로 이루어진 세그먼트 트리를 구합니다.

입력으로는 1 ~ N 까지 자신보다 왼쪽에 있는 수 중에 자신보다 큰 수의 갯수가 주어집니다.

 

가장 작은 숫자인 1부터 입력으로 주어진 자신보다 큰 수의 갯수 + 1이 되는 자리를 찾습니다.

만약 cnt[1] = 5면 1의 자리는 6이 됩니다.

자리를 찾게 되면 해당 자리의 리프노드의 값을 0으로 하고 구간 값도 갱신합니다.

이 과정을 반복한 후에 결과를 출력해주시면 됩니다.

 

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
#include <iostream>
#define MAX 100000
using namespace std;
 
int list[MAX + 1], tree[(MAX + 1) * 4];
int cnt[MAX + 1];
int N;
 
int init(int node, int s, int e) {
    if (s == e) {
        return tree[node] = 1;
    }
 
    int m = (s + e) / 2;
    return tree[node] = init(node * 2, s, m) + init(node * 2 + 1, m + 1, e);
}
 
void query(int node, int s, int e, int idx, int k) {
    if (s == e) {
        tree[node] = 0;
        list[s] = idx;
        return;
    }
 
    int m = (s + e) / 2;
    if (k <= tree[node * 2]) query(node * 2, s, m, idx, k);
    else query(node * 2 + 1, m + 1, e, idx, k - tree[node * 2]);
 
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
void func() {
    for (int i = 1; i <= N; i++) {
        query(1, 1, N, i, cnt[i] + 1);
    }
 
    for (int i = 1; i <= N; i++) {
        cout << list[i] << '\n';
    }
}
 
void input() {
    cin >> N;
    init(1, 1, N);
    for (int i = 1; i <= N; i++) {
        cin >> cnt[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 16993 연속합과 쿼리  (0) 2022.08.29
boj 12846 무서운 아르바이트  (0) 2022.08.19
boj 14719 빗물  (0) 2021.03.15
boj 2304 창고 다각형  (0) 2021.02.25
boj 14438 수열과 쿼리 17  (0) 2021.02.21

+ Recent posts

티스토리툴바