프로그래밍

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=392

[난이도] level3
[유형] Greedy

[풀이]
강의 종료 시간을 기준으로 정렬하고 0번 강의는 무조건 선택한 뒤,
그 다음 추가가 가능한 강의를 index가 낮은 순서부터 탐색하면서 선택해주면 가장 많은 수의 강의를 추가할 수 있습니다.
현재 선택한 강의의 종료시간보다 다음 강의의 시작시간이 더 늦거나 같으면 선택할 수 있는 강의입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
pair<int,int> a[1000000];
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].second,&a[i].first);
    sort(a,a+N);
    for(int i=0;i<N;i++){
        int end = a[i].first;
        ans++;
        bool ok=0;
        for(int j=i+1;j<N;j++){
            if(end<=a[j].second){
                i=j-1;
                ok=1;
                break;
            }
        }
        if(!ok) break;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/강의실_배정.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=414&sw_prbl_sbms_sn=18270

[난이도] level3
[유형] Greedy

[풀이]
로봇과 부품의 index를 각각 저장한 뒤,
앞쪽 로봇부터 부품을 할당할때 가능하면 앞쪽 부품을 할당하는 것이 가장 유리합니다.
이를 위해 부품의 index는 queue에 저장해서 앞쪽 부터 순차적으로 꺼내면서 사용해주면 됩니다.

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int N,K;
vector<int> p;
queue<int> q;
string s;
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) {
        char c;
        scanf(" %c",&c);
        if(c=='P') p.push_back(i);
        else q.push(i);
    }
    int ans=0;
    for(auto r : p){
        while(!q.empty()){
            int i = q.front(); 
            if(abs(r-i)<=K) {
                ans++;
                q.pop();
                break;
            }else if(r>i) q.pop();
            else break;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/스마트_물류.cpp

https://programmers.co.kr/learn/courses/30/lessons/77886

[난이도] level3
[유형] Greedy

[풀이]

나올 수 있는 모든 110을 뽑아서 남은 문자열에서 가장 뒤에 있는 0 뒤에 모든 110을 붙혀주면 되는 문제입니다.

이게 가능한 이유는 문자열에 있는 존재하는 모든 110을 제거했다면,
1이 연속으로 2개 이상 나오는 경우는 "111111"과 같이 0이 존재하지 않는 경우밖에 없습니다.
왜냐하면 0이 붙는 순간 "110"이 되어 제거되기 때문입니다.

결국 남은 문자열은
1만 남은 경우 또는 "1001010"과 같이 1 다음에는 무조건 0이 나오는 형태 두가지 경우일 수밖에 없습니다.

1만 남은 경우에는 사전순으로 작은 문자가 되려면
110들을 문자열의 앞에다가 붙혀야 합니다. ex) "110110+11111"

1과 0이 같이 나오는 "10010100" 같은 경우에는
11이 연속으로 나오는 "110"을 무조건 맨 마지막 0 뒤에 넣어야 합니다.
앞쪽에 넣게 되면 연속된 "11"에 의해 사전순으로 뒤로 밀리게 되기 때문입니다.

위 두가지 케이스를 한번에 처리하기 위해 0을 남은 문자열 앞에 더해주었습니다.
이러면 마지막 0의 위치만 찾아서 제거한 "110"들을 넣기만 하면 됩니다.

#include <string>
#include <vector>
using namespace std;
string sol(string str){
    string ret,ans;
    int cnt=0;
    for(auto c : str){
        if(c=='0' && ret.size()>=2 && ret.substr(ret.size()-2,2)=="11"){            
            ret.pop_back();ret.pop_back();
            cnt++;
        } else ret.push_back(c);
    }
    ret='0'+ret;
    int idx;
    for(int i=ret.size()-1;i>=0;i--){
        if(ret[i]=='0') {
            idx=i;
            break;
        }
    }
    for(int i=0;i<=idx;i++) ans+=ret[i]; 
    while(cnt--) ans+="110";
    for(int i=idx+1;i<ret.size();i++) ans+=ret[i];
    return ans.substr(1);
}
vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(auto str : s) answer.push_back(sol(str));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/110_옮기기.cpp

https://programmers.co.kr/learn/courses/30/lessons/70130

[난이도] level3
[유형] Greedy

[풀이]
a배열의 최대 길이가 50만이기 때문에 한번 배열을 스캔하면서 최대 길이의 스타수열을 찾아야합니다.

"a의 모든 수는 0 이상 (a의 길이) 미만입니다."
위의 조건에 의해 나올 수 있는 수도 50만 미만이기 때문에 두개의 배열을 이용해 문제를 풀 수 있습니다.
cnt[500000],idx[500000] 두 배열을 선언하여

cnt[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 최대길이
idx[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 마지막 index

위와 같은 값을 저장하는 용도로 사용합니다.

이제 a배열을 0부터 순회하면서
i번째 원소를 확인중일 때, 조건을 만족한다면 cnt[a[i]], idx[a[i]]를 업데이트 할 수 있습니다.

i번째 원소의 왼쪽에 짝이 있는 경우와, 오른쪽에 짝이 있는 경우가 있을 수 있습니다.

왼쪽에 짝이 있으려면,
idx[a[i]] 즉, a[i]를 교집합으로 하는 스타 수열의 마지막 index보다는 i-1이 작아야하며 (idx[a[i]] < i-1)
a[i] != a[i-1]을 만족해야 합니다. (서로 값이 달라야 하기 때문에)

i-1만 검사해도 되는 이유는 만약 a[i] == a[i-1] 이고 a[i-1] != a[i-2] 라면 (예를 들어 a[i]가 1일때 [...2,1,1] 이런 형태)
idx[a[i]]가 i-1일 것이므로 idx[a[i]] < i-1 에서부터 조건을 만족하지 못하여 a[i] != a[i-1]는 검사할 필요가 없어집니다.

왼쪽에 짝이 있다면 i가 이제 마지막 index가 되므로 idx[a[i]]=i로 업데이트 해주고
짝이 한개 추가되었기 때문에 cnt[a[i]]++를 해주고 다음 index를 검사합니다.

만약 왼쪽에 짝이 없다면 오른쪽에 있는지 검사해야 합니다.
오른쪽에 a[j] != a[i] 를 만족하는 j가 있다면 idx[a[i]]=j 로 업데이트 해주면 됩니다.

for문을 돌때마다
먼저 if(i<=idx[a[i]]) continue 를 추가해줍니다.
위 조건에 걸렸다는 것은 스타 수열의 index가 i 뒤에 있다는 것이기 때문에 i는 스타 수열에 포함될 수 없어 검사할 필요가 없습니다.

최종적으로 cnt[i] (0<=i<(a의 길이)) 중에 최댓값을 구하고, 쌍의 개수이므로 그 값에 2배를 해주면 됩니다.

알고리즘 분류가 애매하지만 매 루프마다 최적의 index를 고르는 것이기 때문에 Greedy 문제로 생각됩니다.

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int mxN=5e5;
int cnt[mxN],idx[mxN],ans;
int solution(std::vector<int> a) {
    memset(idx,-1,sizeof(idx));
    for(int i=0;i<a.size();i++){
        if(i<=idx[a[i]]) continue;
        if(i>0&& idx[a[i]] < i-1 && a[i]!=a[i-1]){
            cnt[a[i]]++, idx[a[i]]=i;
            continue;
        }
        int j=i;
        while(++j<a.size() && a[j] == a[i]);
        if(j<a.size()) cnt[a[i]]++, idx[a[i]]=j;
    }
    for(int i=0;i<a.size();i++) ans=std::max(ans,cnt[i]);
    return ans*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스타_수열.cpp

https://codeforces.com/contest/1549/problem/B

[난이도] Div.2
[유형] Greedy

[풀이]
폰의 앞이 비어있다면 무조건 앞으로 전진이 가능하기 때문에
폰이 있으면 앞이 비어있는 폰은 빼주면서 정답에 이 폰의 개수를 더해줍니다.

그다음 좌측 폰부터 확인하면서
좌측 윗쪽에 폰이 있다면 이쪽으로 먼저 보내주고, 없으면 우측 윗쪽에 폰이 있는지 체크해서
폰이 있으면 이쪽으로 보내고 정답에 1을 더해줍니다.

좌측부터 검사하기 때문에 대각선 앞의 적 폰이 있는지 검사할 때 좌측->우측 순으로 검사해서 사용해 주는것이 제일 유리합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,N;
string me,enemy;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> tc;
    while(tc--){
        cin >> N >> enemy >> me;

        int ans=0;
        for(int i=0;i<N;i++){
            if(enemy[i]=='0' && me[i]=='1'){
                ans++;
                me[i]='0';
            }
        }

        for(int i=0;i<N;i++){
            if(me[i]=='0') continue;
            if(i!=0 && enemy[i-1]=='1'){
                ans++;
                continue;
            }
            if(i!=N-1 && enemy[i+1]=='1'){
                ans++;
                enemy[i+1]='0';
            }
        }
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round736-Div.2/B.cpp

https://codeforces.com/contest/1551/problem/C

[난이도] Div.3
[유형] Greedy

[풀이]
n개의 a~e로 이루어진 문자열중에 i개의 문자열을 골랐을 때,
i개의 문자열에 포함된 한 문자(a~e 중 하나)가 나머지 문자들보다 많으면
이것을 Interesting story라고 합니다.

문제에서는 Interesting story를 만들 수 있으면서 i를 최대로 할때의 i값을 출력해야 합니다.

n제한 20만이기때문에 O(n)으로 해결해야 합니다.
Greedy 방식으로 해결이 가능합니다.

예를들어 n이 3이고 아래와 같이 문자열이 주어졌을 때,
bac
aaada
e

일단 알파벳이 a~e 5개밖에 안되기때문에
a가 제일 많은 경우, b가 제일 많은 경우 ... e가 제일 많은 경우
총 5가지의 경우를 가정하여 5가지를 모두 해보는 방식으로 접근합니다.

5가지 경우에 대해 문자열을 가장 많이 선택할 수 있는 경우의 문자열 갯수를 구하고
이중 최댓값이 정답이 됩니다.

bac [ a:1 , 나머지 :2]
aaada [ a:4 , 나머지 :1]
eaeeeb [ a:1 , 나머지 :5]
여기서 a가 가장 많은 경우를 구하면,
3개를 모두 선택하게 되면, a 6개, 나머지 8개로 Interesting story를 만족하지 못합니다.

그러므로 Interesting story가 될때까지 문자열을 한개씩 빼줘야 합니다.
여기서 Interesting story를 만들기 가장 유리한 순서로 문자열을 빼줍니다.
당연하게도 a의 개수보다 나머지 문자의 수가 많을수록 우선적으로 빼주는것이 유리합니다.
그말은 즉, Diff : (a의 개수) - (나머지 문자의 수) 가 작은 수부터 빼주는것이 유리하다는 말이됩니다.

위의 Diff를 각 문자열에 계산해보면
bac -> -1
aaada -> 3
eaeeeb -> -4
이므로 eaeeeb , bac 순으로 빼주는 것이 유리합니다.
vector에 Diff 값들을 넣어주고 정렬하면 순서대로 빼주는 것이 가능합니다.

3개의 문자를 포함했을때는 Diff가 -2였지만 eaeeeb를 빼줌으로써 +2가 됩니다.
전체 Diff가 양수가 되면 Interesting story를 만족하는 것이므로
a가 가장 많은 경우에 선택할 수 있는 문자열의 최대 수는 bac,aaada를 선택한 2가 됩니다.

b,c,d,e에 대해서도 위와 같은 연산을 해주고 이중 최댓값을 선택하면 됩니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n;
string arr[200001];

int getCnt(char target){
    int total_diff=0;

    vector<int> diff; // diff
    for(int i=0;i<n;i++){
        int cnt=0;
        for(char c : arr[i]){
            if(c==target){
                cnt++;
            }
        }
        int other = (int)arr[i].size()-cnt;
        diff.push_back(cnt-other);
        total_diff+=(cnt-other);
    }
    sort(diff.begin(),diff.end());
    for(int i=0;i<diff.size();i++){
        if(total_diff>0) {
            return n-i;
        }
        total_diff -= diff[i];
    }
    return 0;
}

void solve(){
    int ret=0;
    for(int i=0;i<5;i++){
        ret=max(ret,getCnt('a'+i));
    }
    cout <<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> tc;
    while(tc--){
        cin >> n; 
        for(int i=0;i<n;i++) cin >> arr[i];
        solve();
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/C.cpp

https://codeforces.com/contest/1551/problem/B1

[난이도] Div.3
[유형] Greedy

[풀이]
어떤 알파벳이라 2개 이상이라면 레드,그린 각각 1개씩 밖에 들어갈수 없고,
1개만 있는 알파벳들은 어디든지 들어갈 수 있습니다.
이것을 이용하면
답은 (2개 이상인 알파벳의 개수)+(1개만 있는 알파벳의 개수)/2 인것을 알 수 있습니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n,a,b,cnt[26];
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        memset(cnt,0,sizeof(cnt));

        for(char c : s){
            cnt[c-'a']++;
        }

        int ans=0,remain=0;
        for(int i=0;i<26;i++){
            if(cnt[i]>=2) ans++;
            else if(cnt[i]==1) remain++;
        }
        printf("%d\n",ans+remain/2);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/B-1.cpp

https://codeforces.com/contest/1550/problem/B

[난이도] Div.2
[유형] Greedy

[풀이]
길이 n의 string s가 주어질때 총 지워지는 길이는 n이므로
a*l + b에서 a*l은 결국 a,b 값에 무관하게 정답에 포함되게 됩니다.
Deletion이 일어나는 횟수만큼 b가 추가되게 되므로
b가 음수인지, 양수인지에 따라 deletion 횟수를 최소화 할지, 최대화 해야할지를 정해야합니다.

b가 양수이면
deletion이 최대한 많이 일어나야 하므로 모든 원소를 1씩 지우게 되면
b*n만큼이 정답에 더해지게 됩니다.
결국 a*n+b*n이 b가 양수일때는 cost를 높이는 최적의 값입니다.

b가 음수이면
deletion이 최대한 적게 일어나야 하므로 지울 수 있는 안쪽의 문자열부터 직접 지워봐서 몇번 지워지는지 확인해봅니다.

"000111000111000" -> "000000111000" -> "000000000" -> ""

예를 들어 위와같이 3번 지우면 deletion을 최소로 지울 수 있습니다.

(tutorial을 보면 직접 해보지 않고도 수식으로 간단하게 답을 구하는 풀이가 있습니다.)

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,n,a,b;
int main(){
    cin >> tc;
    while(tc--){
        string s;
        cin >> n >> a >> b >> s;
        int ans = n*a;
        if(b>0){
            ans+=b*n;
        }else if(b<0){

            int l=0;
            while(1){
                bool ok=1;
                int sidx=-1,eidx=-1;
                for(int i=1;i<s.size();i++){
                    if(s[i]!=s[i-1]){
                        sidx=i;
                        eidx=i;
                        ok=0;
                        for(int j=i+1;j<s.size()&&s[j]==s[i];j++){
                            eidx=j;
                        }
                        break;
                    }
                }
                if(ok) {
                    if(!s.empty()) l++;
                    break;
                }
                l++;
                s.erase(sidx,eidx-sidx+1);
            }

            ans+=l*b;
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU111-Div.2/B.cpp