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

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

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

연속된 수들의 부분합이기 때문에 two pointer로 해결할 수 있습니다.

저는 two pointer와 dp를 사용하였습니다.

 

우선 dp에 연속합을 저장해놓고

l~r의 합이 S보다 작으면 r++

l~r의 합이 S보다 크거나 같으면 ans을 갱신하고 l++

이 과정을 반복하여 ans을 출력하였습니다.

 

예외처리로 모든 값을 더해도 S보다 작다면 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
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[], dp[];
    static int N, S, ans = 100000;
 
    static void func() {
        int l = 1;
        int r = 1;
 
        while (r <= N) {
            if (dp[r] - dp[l - 1] < S) {
                r++;
            } else {
                ans = Math.min(ans, r - l + 1);
                l++;
            }
        }
 
        if (ans == 100000)
            ans = 0;
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = 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 2559 수열  (0) 2021.02.12
boj 2003 수들의 합 2  (0) 2021.01.22

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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

dp로 list의 연속 합을 구현하였고 two pointer로 인덱스를 조정해가며 M과 비교하였습니다.

l~r의 합이 M과 같으면 정답인 경우이므로 ans++

l~r의 합이 M보다 작으면 수를 더해야하므로 r++

l~r의 합이 M보다 크면 수를 빼야하므로 l++

이 과정을 반복하여 r이 list.length와 같아지면 중지하면 됩니다.

 

 

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.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], dp[];
    static int N, M, ans;
 
    static void func() {
        int l = 1;
        int r = 1;
        while (r < list.length) {
            if (dp[r] - dp[l - 1] == M) {
                ans++;
                l++;
            } else if (dp[r] - dp[l - 1] > M) {
                l++;
            } else
                r++;
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = 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 2559 수열  (0) 2021.02.12
boj 1806 부분합  (0) 2021.01.22

+ Recent posts

티스토리툴바