문제

 

풀이

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

이 문제와 비슷한 방식으로 접근할 수 있습니다.

 

카드 주머니가 N개 있고, 주머니 안에는 각각 1 ~ Ai가 적힌 카드가 있습니다.

여기서 연속된 K개의 카드 주머니를 고르고, 그 카드 주머니에서 카드 하나씩 꺼내서

1, 2, 3, ...., K까지 하나씩 등장하도록 만들어야 하고, 이 때 K의 최댓값을 구하는 문제입니다.

 

이 문제는 고민만 하다가 끝났었는데 Two Pointer + Segment Tree Lazy로 풀리는 문제였습니다.

트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

만약 N = 5라면 1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있게 됩니다.

주머니의 크기가 5 5 5 5 5라면 크기가 5인 주머니를 5번 사용할 수 있으며, 5 5 5 5 5 5로는 6을 만들 수 없습니다.

 

그 다음에는 l = 0, r = 0으로 시작하여 해당 범위에 속한 K개를 모두 사용하여 1 ~ K까지 하나씩 만들 수 있는지 확인합니다.

r번째 주머니를 사용한게 되기 때문에 list[r] ~ maxValue의 범위에 -1씩 카운팅을 해줍니다.

이 과정에서 트리의 값이 음수가 되었다면 1 ~ K를 고르지 못한게 됩니다.

그래서 다시 음수에서 벗어날때까지 l을 오른쪽으로 이동시켜줍니다.

트리의 값이 음수인 것을 빠르게 캐치하려면 트리에 최솟값을 저장해야 합니다.

 

5
1 1 2 5 3

예시로 설명드리면

맨 처음 트리의 상태는 1 2 3 4 5이고, 최솟값은 1입니다. (l = 0, r = 0)

 

여기서 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 1)

값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.

그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0입니다.

 

다음 범위를 오른쪽으로 1칸 늘립니다. (l = 0, r = 2)

값이 1이기 때문에 1 ~ 5의 카운팅을 1씩 감소시킵니다.

그러면 트리의 상태는 -1 0 1 2 3이 되고, 최솟값은 -1입니다.

이때 음수가 되었기 때문에 l을 오른쪽으로 1칸씩 이동시킵니다. (l = 1, r = 2)

직전 l번째 수는 1이었기 때문에 1 ~ 5의 카운팅을 1씩 늘립니다.

그러면 트리의 상태는 0 1 2 3 4가 되고, 최솟값은 0이 되어 1 ~ K를 다시 만들 수 있게 됩니다.

 

다음 범위를 오른쪽으로 1칸 이동합니다. (l = 1, r = 3)

값이 2이기 때문에 2 ~ 5의 카운팅을 1씩 감소합니다.

트리의 상태를 0 0 1 2 3이 되고, 최솟값은 0이기 때문에 범위를 갱신할 수 있습니다.

 

이 과정을 끝까지 반복하여 l ~ r의 범위를 최대로 만들 수 있습니다.

 

코드

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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50001
using namespace std;
 
int list[MAX], tree[MAX << 2], lazy[MAX << 2];
int N, maxValue;
 
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) {
        tree[node] += diff;
        if (l != r) {
            lazy[node << 1] += diff;
            lazy[(node << 1) + 1] += diff;
        }
        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 1e9;
    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, maxValue, i, maxValue, 1);
    }
}
 
void func() {
    init();
    int ret = 1;
    int l = 0;
    int r = 0;
    while (r < N) {
        update(1, 1, maxValue, list[r], maxValue, -1);
 
        while (query(1, 1, maxValue, list[r], maxValue) < 0) {
            update(1, 1, maxValue, list[l], maxValue, 1);
            l++;
        }
        r++;
 
        ret = max(ret, r - l);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        maxValue = max(maxValue, list[i]);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

엘리스 코드 챌린지 Day 9 격자 위의 ELICE  (0) 2024.07.24
엘리스 코드 챌린지 Day 8 강림제  (0) 2024.07.23
엘리스 코드 챌린지 Day 7 계기판 조작하기  (0) 2024.07.23
엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22

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

 

1253번: 좋다

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

www.acmicpc.net

투 포인터를 이용하여 배열 내의 어떤 수를 다른 두개의 합으로 나타낼 수 있는지 확인합니다.

투 포인터 사용을 위해 배열을 오름차순으로 정렬하고, 0번 인덱스부터 N - 1번 인덱스까지 전부 확인합니다.

초기 값은 left = 0, right = N - 1이며, 합이 list[i]와 같으면 바로 break, 합이 더 크면 right를 1 감소, 합이 더 작으면 left를 1 증가시킵니다.

 

이 문제에서 주의할 점은 "수의 위치가 다르면 값이 같아도 다른 수이다" 부분입니다.

자기 자신과 0을 더하는 경우가 나올 수 있는 left 또는 right가 i와 일치한 경우만 제외하였습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 2000
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int l = 0;
        int r = N - 1;
        while (l < r) {
            if (l == i) {
                l++;
                continue;
            }
            if (r == i) {
                r--;
                continue;
            }
 
            int sum = list[l] + list[r];
            if (sum == list[i]) {
                ans++;
                break;
            }
            else if (sum > list[i]) {
                r--;
            }
            else {
                l++;
            }
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    sort(list, list + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Two-Pointer' 카테고리의 다른 글

boj 9024 두 수의 합  (0) 2021.10.21
boj 17609 회문  (0) 2021.03.29
boj 2559 수열  (0) 2021.02.12
boj 1806 부분합  (0) 2021.01.22
boj 2003 수들의 합 2  (0) 2021.01.22

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

 

9024번: 두 수의 합

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄

www.acmicpc.net

배열에서 합이 K에 가장 가까운 서로 다른 두 개의 정수 조합의 갯수를 구하는 문제입니다.

이 문제는 투 포인터를 이용하여 해결할 수 있습니다.

 

투 포인터 사용을 위해 배열을 오름차순으로 정렬합니다.

그리고 left = 0, right = N - 1에서 시작합니다.

 

두 정수의 합(list[l] + list[r])이 K에 더 가까우면 합(ans)을 갱신, 갯수를 의미하는 cnt를 1로 초기화합니다.

만약 두 정수의 합과 갱신된 합이 같으면 cnt를 1 증가합니다.

그리고 두 정수의 합이 K보다 크면 값을 작게 해야하므로 right를 1 감소,

두 정수의 합이 K보다 작으면 값을 크게 해야하므로 left를 1 증가시킵니다.

 

최종으로 K에 가장 가까운 두 정수의 조합의 갯수인 cnt를 출력합니다.

 

 

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 <algorithm>
#define MAX 1000000
using namespace std;
 
int list[MAX];
int N, K;
 
void func() {
    int l = 0;
    int r = N - 1;
    int ans = 2e8;
    int cnt = 0;
    while (l < r) {
        int sum = list[l] + list[r];
        if (abs(sum - K) < abs(ans - K)) {
            ans = sum;
            cnt = 1;
        }
        else if (abs(sum - K) == abs(ans - K)) {
            cnt++;
        }
 
        if (sum > K) r--;
        else l++;
    }
 
    cout << cnt << '\n';
}
 
void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    sort(list, list + N);
}
 
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 > Two-Pointer' 카테고리의 다른 글

boj 1253 좋다  (0) 2021.10.21
boj 17609 회문  (0) 2021.03.29
boj 2559 수열  (0) 2021.02.12
boj 1806 부분합  (0) 2021.01.22
boj 2003 수들의 합 2  (0) 2021.01.22

www.acmicpc.net/problem/17609

 

17609번: 회문

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

www.acmicpc.net

N이 10만개니 lcs로는 해결 못합니다..

 

투 포인터로 하나하나 확인해줍니다.

왼쪽 인덱스를 0, 오른쪽 인덱스를 ch.length - 1로 두고

문자열의 끝 단어끼리 비교를 합니다.

 

1. 끝 단어가 같을 때

- 왼쪽, 오른쪽 인덱스 모두 다음 인덱스를 확인합니다.

2. 끝 단어가 다를 때

- 왼쪽 인덱스를 옮겨줄 때와 오른쪽 인덱스를 옮겨줄 때를 각각 확인합니다.

저는 투포인터를 두번 사용하여 왼쪽 인덱스를 옮길 때, 오른쪽 인덱스를 옮길 때 다른 값의 min값으로 답을 출력하였습니다.

 

 

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
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 StringBuffer sb = new StringBuffer();
    static char ch[];
 
    static void func() {
        int l = 0;
        int r = ch.length - 1;
        int ans = 0;
        int cnt = 0;
        while (l < r) {
            if (ch[l] == ch[r]) {
                l++;
                r--;
            } else {
                cnt++;
                l++;
            }
 
            if (cnt == 2)
                break;
        }
        ans = cnt;
 
        l = 0;
        r = ch.length - 1;
        cnt = 0;
        while (l < r) {
            if (ch[l] == ch[r]) {
                l++;
                r--;
            } else {
                cnt++;
                r--;
            }
 
            if (cnt == 2)
                break;
        }
 
        ans = Math.min(ans, cnt);
        sb.append(ans).append("\n");
    }
 
    static void input() throws Exception {
        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();
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > Two-Pointer' 카테고리의 다른 글

boj 1253 좋다  (0) 2021.10.21
boj 9024 두 수의 합  (0) 2021.10.21
boj 2559 수열  (0) 2021.02.12
boj 1806 부분합  (0) 2021.01.22
boj 2003 수들의 합 2  (0) 2021.01.22

www.acmicpc.net/problem/2559

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

모든 연속적인 K일 간의 최대 온도의 합을 출력하는 문제입니다.

우선 dp를 이용하여 N일 간 측정한 모든 온도의 연속합을 저장합니다.

그 다음 투 포인터 방식으로 l = 1, r = K으로 시작하여 dp[r] - dp[l - 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
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], dp[];
    static int N, K, ans = Integer.MIN_VALUE;
 
    static void func() {
        int l = 1;
        int r = K;
 
        while (r <= N) {
            ans = Math.max(ans, dp[r] - dp[l - 1]);
 
            r++;
            l++;
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + list[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > Two-Pointer' 카테고리의 다른 글

boj 1253 좋다  (0) 2021.10.21
boj 9024 두 수의 합  (0) 2021.10.21
boj 17609 회문  (0) 2021.03.29
boj 1806 부분합  (0) 2021.01.22
boj 2003 수들의 합 2  (0) 2021.01.22

+ Recent posts

티스토리툴바