프로그래밍

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

[난이도] Silver2
[유형] 브루트포스

[풀이]
N 제한이 10밖에 되지 않기 때문에 v[N] 배열에 1부터 N까지 순서대로 저장 한 뒤
순열을 이용해 정답이 될 수 있는 모든 경우의 수를 만들어 보며 조건을 만족하지는지 체크해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[11],v[11];
bool check(){
    for(int i=1;i<=N;i++){
        int cnt=0;
        for(int j=1;j<i;j++){
            if(v[j]>v[i]) cnt++;
        }
        if(a[v[i]] != cnt) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        v[i]=i;
    }
    do{
    }while(!check() &&next_permutation(v+1,v+1+N));
    for(int i=1;i<=N;i++) printf("%d ",v[i]);
}

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

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

[난이도] Silver2
[유형] 리스트

[풀이]
STL list를 선언한 뒤 iterator를 커서로 취급하여 문제를 해결하면 됩니다.
insert나 erase시 return 되는 iterator의 위치는 헷갈릴 수 있기 때문에 몇가지 예시를 해보면서
iterator의 위치를 파악해야 합니다.

#include <iostream>
#include <list>
#include <string>
using namespace std;
int N;
string s;
int main(){
    cin >> N;
    while(N--){
        cin >> s;
        list<char> li;
        auto it = li.begin();
        for(auto c : s){
            if(c=='-'){
                if(it==li.begin()) continue;
                it--;
                it = li.erase(it);
            }else if(c=='<'){
                if(it==li.begin()) continue;
                it--;
            }else if(c=='>'){
                if(it!=li.end()) it++;
            }else{
                li.insert(it,c);
            }
        }
        for(auto v : li) cout << v;
        cout << "\n";
    }
}

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

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

[난이도] Silver1
[유형] 우선순위큐

[풀이]
우선순위 큐에 모든 원소들을 넣고 가장 작은 두 수를 뽑아서 계산해서 다시 넣어주고 반복하면 됩니다.

#include <cstdio>
#include <queue>
using namespace std;
int n,m;
using ll = long long;
int main(){
    scanf("%d%d",&n,&m);
    priority_queue<long long> pq;
    while(n--) {
        int v;
        scanf("%d",&v);
        pq.push(-v);
    }
    while(m--){
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        pq.push(a+b);
        pq.push(a+b);
    }
    ll ans=0;
    while(!pq.empty()) ans+=pq.top(), pq.pop();
    printf("%lld",-ans);
}

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

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

[난이도] Silver1
[유형] 이분탐색

[풀이]
가능한 블루레이 크기의 최솟값은 길이가 가장 짧은 강의의 길이
이고 최댓값은 100000(N의 최댓값) * 10000 (강의 길이의 최댓값) = 10^9
입니다.

범위가 너무 크기 때문에 이분탐색을 이용해서 최솟값을 찾아주면 됩니다.

mid 값을 블루레이의 크기라고 가정 했을 때, bool check(int k) 함수를 이용해서 조건을 만족하는지 체크해주며
범위를 좁혀갈 수 있습니다.

#include <cstdio>
int n,m,a[100000];
bool check(int k){
    int cnt=1,sum=0;
    for(int i=0;i<n;i++){
        if(sum+a[i]>k) {
            sum=0;
            cnt++;
        }
        sum+=a[i];
    }
    return cnt <= m;
}
int main(){
    scanf("%d%d",&n,&m);
    int lo=1,hi=1e9+1;
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        if(a[i]>lo) lo=a[i];
    }
    lo--;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    printf("%d",lo+1);
}

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

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

[난이도] Gold5
[유형] 정렬

[풀이]
각 열 문자로 만든 문자열을 뒤집고 vector에 넣고 정렬해줍니다.
정렬을 해주면 다음과 같은 입력이 주어졌을 때,

mrvica
mrvica
marica
mateja

아래와 같이 정렬이 됩니다.
0:aaaa
1:aarr
2:eiii
3:jccc
4:mmmm

문제의 조건은 결국 위 vector에서 인접한 문자열 두 문자열을 앞에서부터 비교했을 때,
같은 부분이 가장 긴 문자열의 길이를 찾으면 됩니다.

위의 예에서 0번과 1번을 비교했을 때, aa 이므로 이 값을 행의 길이에서 빼주고 1을 빼주면 됩니다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int r,c,k,mv;
string s[1000];
int main(){
    cin >> r >> c;
    for(int i=0;i<r;i++) cin >> s[i];
    vector<string> st(c);
    for(int j=0;j<c;j++)
        for(int i=r-1;i>=0;i--) st[j].push_back(s[i][j]);

    sort(st.begin(),st.end());
    for(int i=0;i<c-1;i++){
        int k=0;
        for(int j=0;j<r;j++){
            if(st[i][j]==st[i+1][j]) k++;
            else break;
        }
        mv=max(k,mv);
    }
    cout << r-mv-1;
}

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

https://school.programmers.co.kr/learn/courses/30/lessons/118667

[난이도] level2
[유형] 구현

[풀이]
전체 합의 절반 값이 t일 때, queue1의 값을 t로 만들면 됩니다.
실제로 큐 두개를 선언하여 queue1,queue2에 넣고 현재 queue1 값들의 합을 sum이라고 했을 때,
sum의 값이 t보다 크면 queue1 에서 pop, t보다 작으면 queue2에서 pop 하는 방식으로 sum이 t가 될때까지 진행해줍니다.
최대 연산 횟수는 queue1,queue2의 초기 사이즈를 N이라고 했을 때,
queue1의 값을 모두 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1으로 옮기는 경우 이므로 N+2*N = 3*N 이 됩니다.
연산 과정에서 무한히 반복될 수 있으므로 최대 3*N만큼만 루프를 돌려줍니다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
ll sum,sum2;
queue<int> q1,q2;
int N;
int solution(vector<int> a, vector<int> b) {
    for(int i=0;i<a.size();i++){
        sum+=a[i];
        sum2+=b[i];
        q1.push(a[i]);
        q2.push(b[i]);
    }

    if((sum+sum2)%2)return -1;
    ll t = (sum+sum2)/2;

    int i=0,j=0,ans=0,n=a.size()*3;
    while(n--){
        if(sum>t){
            ans++;
            int v = q1.front();
            sum-=v;
            q2.push(v);
            q1.pop();
        }else if(sum<t){
            ans++; 
            int v = q2.front();
            sum+=v;
            q1.push(v);
            q2.pop();            
        }else{
            return ans;
        }
    }
    return -1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/두_큐_합_같게_만들기.cpp

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

[난이도] Silver1
[유형] 수학

[풀이]
1의 개수끼리 최대 공약수를 구한 뒤,
이 수만큼 1을 출력해주면 정답이라고 합니다.
증명은 못하겠어서 gcd 구하는 연습용으로 풀었습니다..

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll a,b;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    while(b!=0){
        ll c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int main(){
    scanf("%lld%lld",&a,&b);
    for(int i=0;i<gcd(a,b);i++) printf("1");
}

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

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

[난이도] Silver1
[유형] 스택

[풀이]
실버1치고 발상이 어려워서 다른 분들의 풀이를 참고했습니다.
(()[[]]) = 2 * (2+3*3) = 2*2 + 2*3*3 이 되는 분배법칙을 이용합니다.
cur 변수를 1로 초기화 해놓고
- 여는 괄호 ( 가 나오면 2를 [가 나오면 3을 곱해줍니다.
- 닫는 괄호가 나오면 해당 괄호가 cur에 미치는 영향은 끝났으므로 2 또는 3으로 나눠줍니다.
  예를 들어, (()[[]]) = 2 * (2+3*3) 에서 두번 째 첫 번째 ) 가 나왔을 때, cur은 2*2에서 2*2/2 가 되어 다시 2가 됩니다.
  그래야, 3*3에 2만 곱해줄 수 있기 때문입니다.
- () 혹은 [] 모양의 인접한 올바른 문자열이라면 2*2 + 2*3*3 에서 한 덩어리의 값이 끝남을 의미하므로 나누기 전에 cur의 값을 total에 더해 줍니다.
- 중간중간 올바른 문자열이 아닌 경우를 체크하여 0을 return 해줍니다.
- 모든 문자열을 순회하고도 stack에 값이 남아있다면 올바른 문자열이 아니므로 0을 return 해줍니다.

#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
string s;
int sol(){
    stack<char> st;
    int total=0,cur=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            cur*=2;
            st.push(s[i]);
        }else if(s[i]=='['){
            cur*=3;
            st.push(s[i]);
        }else{
            if(st.empty()) return 0;
            if(s[i]==')') {
                if(st.top()!='(') return 0;
            }else{
                if(st.top()!='[') return 0;
            }
            st.pop();
            if(s[i-1]=='('||s[i-1]=='[') total+=cur;
            if(s[i]==')') {
                cur/=2;
            }else{
                cur/=3;
            }
        }
    }
    if(!st.empty()) return 0;
    return total;
}
int main(){
    cin >> s;
    cout << sol();
}

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