프로그래밍

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

[난이도] Gold4
[유형] 투포인터

[풀이]
입력문자열의 앞부터 확인하면서 a[26] 배열에 각 문자를 몇개 사용했는지를 기록해줍니다.
그러다 N개의 문자를 넘게 사용하게 되면 현재 체크중인 문자열의 맨 앞 index부터 문자열에서
제거해주면서 a[26] 배열을 업데이트 해줍니다. a[k] > 0 이었다가 a[k] == 0 인 문자가 나타나면
이제 맨 뒤 쪽에 이어서 문자를 추가해줄 수 있기 때문에 뒤쪽에 다시 문자들을 붙혀줍니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,a[26],ans,v,start;
string s;
int main(){
    cin >> N >> s;
    string cur;
    for(int i=0;i<s.size();i++){
        int cnt=0;
        for(int j=0;j<26;j++) {
            if(a[j]>0) cnt++;
        }
        if(cnt<N || a[s[i]-'a']){
            v++;
            a[s[i]-'a']++;
            ans=max(ans,v);
            continue;
        }
        for(int j=start;j<=i;j++){
            v--;
            if(--a[s[j]-'a'] == 0){
                start=j+1;
                break;
            }
        }
        i--;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16472.cpp

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

[난이도] Silver3
[유형] 투 포인터

[풀이]
값들을 배열에 저장 후 sum과 left index를 의미하는 left 변수를 유지하면서
for문을 돌리면서 sum에 arr[i]를 더해준다.
더해준 뒤 sum이 m보다 크다면 arr[l]을 sum에서 빼주고 l을 1 증가시켜주기를 sum이 m보다 크지 않을때까지 반복한다.
위 과정을 끝낸 뒤 sum==m 이라면 ans에 1을 더해주고 다음으로 넘어간다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var input = readLine().split(' ')
    var n = input[0].toInt()
    var m = input[1].toInt()
    var arr = readLine().split(' ').map{it.toInt()}
    var ans=0
    var sum=0
    var l=0
    for(i in 0..arr.size-1) {
        sum += arr[i]
        if (sum > m) {
            while (l < i && sum > m) sum -= arr[l++]
        }
        if(sum == m) ans++
    }
    println(ans)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/2003.cpp

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

[난이도] Gold5
[유형] 투포인터

[풀이]
가장 작은 수의 index 0을 l, 가장 큰 수의 index N-1을 r로 설정한 뒤
a[l]+a[r]의 합이 양수이면 r--을 해주어 0과 가깝게 해주고
음수이면 l++을 해주어 0과 가깝게 해주는 방식으로 0과 가까운 후보들을 모두 훑을 수 있다.

#include <cstdio>
#include <cmath>
using namespace std;
int N,a[100000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    int l=0,r=N-1,ans=2e9+1;
    int al=l,ar=r;
    while(l<r){
        int v = a[l]+a[r];
        if(abs(v)<ans){
            al=l;
            ar=r;
            ans=abs(v);
        }
        if(v==0) break;
        else if(v>0) r--;
        else l++;
    }
    printf("%d %d",a[al],a[ar]);
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2467.cpp

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

[난이도] Gold5
[유형] 이분탐색,투포인터

[풀이]
음수인 용액, 양수인 용액을 각각 벡터에 저장한 뒤,
음수인 용액(v)을 고정해놓고 lower_bound를 이용해 양수인 용액 중에 -v와 가장 가까운 수를 찾으면
두 용액의 합이 0에 가장 가까운 수이다. 이 방식으로 O(NlogN)의 시간으로 답을 찾을 수 있다.

(투포인터를 이용하면 훨씬 쉽게 답을 찾을 수 있다.)

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int N,p,q,k=2e9+100;
vector<int> a,b;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(v>0) a.push_back(v);
        else b.push_back(v);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(a.size()>1){
        if(abs(a[0]+a[1]) < k){
            p=a[0];
            q=a[1];
            k=abs(p+q);
        }
    }
    int bsz = b.size();
    if(bsz>1){
        if(abs(b[bsz-2]+b[bsz-1]) < k){
            p=b[bsz-2];
            q=b[bsz-1];
            k=abs(p+q);
        }
    }
    if(!a.empty()){
        for(int v : b){
            int w;
            auto idx = lower_bound(a.begin(),a.end(),-v)-a.begin();
            if(idx>=a.size()){
                w=a[idx-1];
            }else{
                w=a[idx];
                if(idx>0 && abs(w+v) > abs(a[idx-1]+v)) w=a[idx-1];
            }
            if(abs(w+v) < k){
                p=v;
                q=w;
                k=abs(w+v);
            }
        }
    }
    printf("%d %d",p,q);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2470.cpp