프로그래밍

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

[난이도] level3
[유형] set

[풀이]
행의 최대 수가 100만이기 때문에 단순히 vector를 이용하면 삽입,삭제시 비용이 많이 들기 때문에
다른 자료구조를 이용해야 합니다. 물론 커서를 움직일 때는 배열의 경우 특정 index에 O(1)로 접근이 가능하기 때문에
유리하지만 문제 조건에서 모든 cmd의 커서를 움직이는 총 횟수의 합이 1000000 이하이기 때문에 삽입/삭제 연산을 효율적으로
하는 것이 더 중요합니다.

vector는 특정한 위치에 삽입,삭제시 그곳을 기준으로 모든 원소를 움직여 빈공간이 생기지 않도록 하기 때문에 삽입/삭제시 불리합니다.

그렇다고 stl list를 이용하면 복구 연산시 복구 되어야할 위치를 찾기가 어렵습니다.

그래서 set을 이용하였습니다. set은 balanced tree 형태로 되어있어 O(logN)으로 삽입/삭제가 가능하기 때문입니다.
커서의 이동도 iterator를 유지하면 위,아래로 자유롭게 할 수 있습니다.

삭제시에는 set에서 현재 iterator 위치의 원소를 삭제하고, 그 원소를 stack에 넣어주고 복원시에 꺼내서 set에 insert 해주기만 하면
자동으로 복구가 됩니다.
주의할 점이 삭제시 반환된 iterator가 end()인 경우(마지막 원소를 삭제한 경우) iterator를 한 칸 앞으로 (-- 연산) 옮겨주어야 합니다.
왜냐하면 end()는 마지막 원소의 한 칸 뒤를 가르키기 때문에 커서를 위로 올리는 연산시 (-- 연산) 한칸 덜 올라가게 되기 때문입니다.

#include <string>
#include <vector>
#include <set>
#include <stack>
using namespace std;
stack<int> st;
set<int> a;
string solution(int n, int k, vector<string> cmd) {
    string ans;
    for(int i=0;i<n;i++) {
        a.insert(i);
        ans+='X';
    }
    auto it = a.begin();
    while(k--) it++; 
    for(auto c : cmd){
        char q = c[0];
        int num;
        if(c.size()>1) num = stoi(c.substr(2));

        if(q=='U') while(num--) it--;
        else if(q=='D') while(num--) it++;
        else if(q=='Z') {
            a.insert(st.top()); st.pop();
        }
        else {
            st.push(*it);
            it = a.erase(it);
            if(it==a.end()) it--;
        }
    }
    for(auto v : a) ans[v]='O';
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/표_편집.cpp

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

[난이도] level3
[유형] DP

[풀이]
첫번째 스티커를 떼면 마지막 N번째 스티커는 절대로 뗄 수 없고,
첫번째 스티커를 떼지 않으면 마지막 N-1번째 스티커에 따라 뗄 수 있을수도 없을수도 있습니다.

이를 이용해 첫번째 스티커를 뗀 경우와 안뗀 경우를 나눠서 생각하면 편합니다.

dp[n][f] 배열에서 f가 0이면 첫번째 스티커를 뗀 경우, 1이면 떼지 않은 경우로 생각하여 문제를 풉니다.

dp[n][f] (sol(n,f)) 의 의미는 n~N-1까지만 고하고, n번째 스티커는 뗄수도 있을 때, 얻을 수 있는 최댓값입니다.

top-down으로 진행했을 때 점화식은 아래와 같습니다.
sol(n,f) = max(sticker[n]+sol(n+2,f),sol(n+1,f))

sticker[n]+sol(n+2,f) : n번째 스티커를 뗐을 때입니다. n번 스티커의 수에 n+1번째 스티커는 뗄 수 없으므로 sol(n+2,f)를 더해줍니다.
sol(n+1,f) : n번째 스티커를 떼지 않았을 때이므로 1 건너뛰어 sol(n+2,f) 입니다.

마지막으로 n이 N-1이 되었을 때, f가 1이면 N-1번 스티커는 떼지 못하므로 0을 return, 0이면 뗄 수 있으므로 sticker[N-1]를 return 해줍니다.

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N,dp[100002][2];
vector<int> sticker;
int sol(int n,int f){
    if(n>=N) return 0;
    if(n==N-1) return f ? 0 : sticker[N-1];
    int& ret = dp[n][f];
    if(ret!=-1) return ret;
    ret=max(sticker[n]+sol(n+2,f),sol(n+1,f));
    return ret;
}
int solution(vector<int> _sticker)
{
    sticker=_sticker;
    N=sticker.size();
    memset(dp,-1,sizeof(dp));
    return max(sol(1,0),sol(2,1)+sticker[0]);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스티커_모으기(2).cpp

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

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

[풀이]
브루트포스+BFS를 이용한 거리찾기가 결합된 복잡한 구현 문제입니다.
보드가 4x4이고, 나올수 있는 카드의 쌍이 최대 6개라는점을 보고 브루트포스라는 것을 의심해야 합니다.
4x4 맵의 경우 어지간한 문제는 무식하게 풀어도 시간내에 해결이 가능합니다.

이미 카드의 앞면을 알고 있기 때문에 조작 횟수를 최소로 하려면 쓸데없는 칸에 방문하지 않고
카드쌍을 바로바로 제거할 수 있도록 방문해야 합니다.
예를 들어 [1-1/1-2],[2-1/2-2],[3-1/3-2] 총 3쌍의 카드가 있을 때
1-1 -> 1-2 -> 2-2 -> 2-1 -> 3-1 -> 3-2 이런식으로 이동해야 효율적이며
1-1 -> 2-1 -> 1-2 .. 이런식으로 1번카드 갔다가 2번 카드갔다가 하면 불필요한 조작이 늘어납니다.

하지만 어떤 카드부터 지워야 할지는 알수 없기 때문에 모든 경우를 다해봐야 합니다.
next_permutation으로 모든 순서를 구할 수 있습니다.
여기서는 seq vector에 모든 카드 종류를 넣고 순열을 구하였습니다.

하지만 여기서 또 정해야 할것이 1->2->3 순서로 카드를 없애는 경우에서도
1-1 -> 1-2 순서로 방문해서 1을 없애는 경우, 1-2 -> 1-1 순서로 방문해서 1을 없애는 경우가
다른 경우입니다. 2와 3을 방문할때도 같은 종류의 두가지 카드중 어떤 것을 방문할지를 정해야 합니다.

위 과정은 sol(int n) 재귀함수를 통해 백트래킹으로 진행하였습니다.
입력을 받을 때, vector<pair<int,int>> table[7]를 이용해 table[카드 종류]에 같은 종류의 두개의 카드 좌표를 저장해두었습니다.

이를 이용해 vector<pair<int,int>> mseq 에
1->2->3 순서로 카드를 없애는 케이스에서는

(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-1의 좌표),(3-2의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-1의 좌표),(2-2의 좌표),(3-2의 좌표),(3-1의 좌표)
(1-1의 좌표),(1-2의 좌표),(2-2의 좌표),(2-1의 좌표),(3-1의 좌표),(3-2의 좌표)
...
...
와 같이 모든 케이스가

n==total(카드 종류의 개수) 이 될때 저장되게 됩니다.

이제 시작점 (r,c)를 시작으로 mseq에 저장된 좌표를 순서대로 방문하기만 하면 됩니다.
이제 순서가 정해졌기 때문에 카드의 종류 등은 생각할 필요가 없습니다.
위의 모든 케이스에서 조작 횟수를 구한 후 그것들중에 최솟값을 구하면 됩니다.

bfs(int fy,int fx,int ty,int tx) 함수를 통해 (fy,fx)에서 (ty,tx)로 갈때
드는 최소 조작 횟수를 구해주었습니다. end 함수는 ctrl+방향키 조작했을 때 도착하는
좌표를 구해주는 함수입니다.

mseq의 좌표를 순서대로 방문하면서 카드가 제거되는 순간 board에서 그 좌표의 값은 0으로
만들어 주어야 합니다. 그래서 매 시행마다 board를 복사해서 사용하였습니다.
제거되는 순간은 mseq의 index가 홀수인 순간입니다.
이유는 0,1,2,3,4,5 일때
1을 방문한 순간 0,1(1번카드)
3을 방문한 순간 2,3(2번카드)
5를 방문한 순간 4,5(3번카드)
가 각각 지워지기 때문입니다. 이 때 지워주지 않으면 ctrl+방향 조작시 지워져야 했던 카드에 막혀
올바르지 않은 곳으로 위치할 수 있습니다.

위 과정으로 구한 최솟값에 Enter 연산인 (카드의 종류*2) 를 더해준 것이 최종 정답입니다.

시험시간에 풀었다면 시간내에 풀지 못햇을 것 같은 복잡한 문제입니다.
최대한 과정을 쪼개서 간단한 문제로 만드는 것이 중요한 것 같습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
using namespace std;
int total,ans=987654321;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int R,C;
bool visit[4][4];
vector<pair<int,int>> table[7];
vector<int> seq;
vector<pair<int,int>> mseq;
vector<vector<int>> org_board,board;
bool inRagne(int y,int x){
    return y>=0&&x>=0&&y<4&&x<4;
}
pair<int,int> end(int y,int x,int k){
    while(1){
        y+=dy[k]; x+=dx[k];
        if(!inRagne(y,x)){
            y-=dy[k], x-=dx[k];
            break;
        }
        if(board[y][x]>0) break;
    }
    return {y,x};
}
int bfs(int fy,int fx,int ty,int tx){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    visit[fy][fx]=1;
    q.push({fy,fx});
    int ret=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto [y,x] = q.front(); q.pop();
            if(y==ty&&x==tx) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i],nx=x+dx[i];
                if(!inRagne(ny,nx)) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx]=1;
                }
                auto [ky,kx] = end(y,x,i);
                if(!visit[ky][kx]){
                    q.push({ky,kx});
                    visit[ky][kx]=1;
                }
            }
        }
        ret++;
    }
    return -1;
}
void sol(int n){
    if(n==total){
        board = org_board;
        int cy=R,cx=C,res=0;
        for(int i=0;i<mseq.size();i++){
            auto [ny,nx] = mseq[i];
            res+=bfs(cy,cx,ny,nx);
            if(i&1) board[ny][nx]=board[cy][cx]=0;
            cy=ny,cx=nx;
        }
        ans=min(ans,res);
        return;
    }
    int cur = seq[n];
    mseq.push_back(table[cur][0]); mseq.push_back(table[cur][1]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();

    mseq.push_back(table[cur][1]); mseq.push_back(table[cur][0]);
    sol(n+1);
    mseq.pop_back(); mseq.pop_back();
}
int solution(vector<vector<int>> board, int r, int c) {
    R=r, C=c;
    org_board = board;
    set<int> st;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++) {
            if(board[i][j]>0) {
                st.insert(board[i][j]);
                table[board[i][j]].push_back({i,j});
            }
        }
    total = st.size();
    for(auto v : st) seq.push_back(v);
    do{
        sol(0);
    }while(next_permutation(seq.begin(),seq.end()));
    return ans+st.size()*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/카드_짝_맞추기.cpp

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

[난이도] level3
[유형] DFS

[풀이]
트리의 리프노드에서부터 자신을 0으로 만들고, 나머지를 부모 노드로 전달했을 때,
최종으로 값을 전달받는 루트노드가 0이 된다면 조건을 만족하는 것입니다.
DFS를 통해 리프부터 값을 누적해갈 수 있으며 각 노드의 return 이전에 연산 횟수를 더해주면 됩니다.

import java.util.*
import kotlin.math.abs
const val mxN = 300000
var adj = Array(mxN){ mutableListOf<Int>()}
var b = LongArray(mxN)
var ans=0L
fun dfs(par:Int,n:Int):Long{
    var ret = b[n]
    for(i in 0..adj[n].size-1){
        if(adj[n][i]!=par) ret+=dfs(n,adj[n][i])
    }
    ans+=abs(ret)
    return ret
}
class Solution {
    fun solution(a: IntArray, edges: Array<IntArray>): Long {
        for(i in a.indices) b[i]=a[i].toLong()
        for((u,v) in edges){
            adj[u].add(v)
            adj[v].add(u)
        }
        if(dfs(-1,0)!=0L) ans=-1
        return ans
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/모두_0으로_만들기.cpp

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

[난이도] level3
[유형] 트리

[풀이]
칫솔 판매원(Leaf)부터 추천인을 거슬러 올라가면서 본인은 10%만큼, 추천인에게는 90%만큼 이익을 분배하면 됩니다.
전체 사람의 이름을 index로 매핑 시키면 쉽게 추천인을 찾을 수 있으므로 <String,Int> 타입의 맵을 선언하여
이름과 index를 매핑 하였습니다.

lateinit var answer:IntArray
lateinit var referral:Array<String>
var table = hashMapOf<String,Int>()
fun sol(name:String,v:Int){
    if(name=="-" || v==0) return
    var a = 0
    if(v%10!=0) a=1
    answer[table[name]!!]+=(0.9*v).toInt()+a
    sol(referral[table[name]!!],(0.1*v).toInt())
}
class Solution {
    fun solution(enroll: Array<String>, _referral: Array<String>, seller: Array<String>, amount: IntArray): IntArray {
        referral = _referral
        answer = IntArray(enroll.size)
        for(i in enroll.indices) table[enroll[i]]=i
        for(i in seller.indices) sol(seller[i],amount[i]*100)
        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/다단계_칫솔_판매.cpp

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

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

[풀이]
3차원 배열 map[202][202][2]를 선언하여
map[x][y][0] == true 이면 (x,y)~(x,y+1) 기둥이 설치된 것
map[x][y][1] == true 이면 (x,y)~(x+1,y) 보가 설치된 것
위와 같이 관리하도록 하였습니다.

이제 기둥과 보를 각각 설치할때 이것을 설치할 수 있는지와
제거할 때 제거할 수 있는지를 체크해야 합니다.

설치하는 할때 확인하는 것은 쉽습니다.
기둥의 경우 바닥인지, 아래 기둥이 있는지, 보가 있는지만 확인하면 설치가 가능하고
보의 경우 아래 기둥이 있는지, 양옆에 보가 있는지만 확인하면 됩니다.

하지만 제거할 때는 문제가 복잡해질 수도 있습니다.
특정 위치 (x,y)의 기둥이나 보를 제거한다고 할때,
"(x+b,y+b)에 기둥이나 보가 있으니까 (x,y)를 제거하면 안돼" 이렇게 생각하면 복잡해 지는 경우입니다.
단순하게
"(x,y)의 기둥(보) 를 지웠음에도 map의 모든 기둥과 보가 조건을 만족하고 있다면 (x,y)는 지워도 되겠네"
라고 생각하는 것이 좋습니다.

즉, (x,y)의 기둥(보)를 지워보고 nxn map의 모든 기둥봐 보를 2중 for문으로 체크해보면서 조건을 여전히 만족하는지를 체크하는 것입니다.

쿼리가 1000개이고 n이 최대 100이기 때문에 O(100x100x10000) 으로 충분히 시간내에 해결이 가능합니다.
만약 n이 좀더 큰수라면 지워야하는 (x,y)의 주변에 영향을 받을만한 (x+b,y+b)들만 체크해야 겠지만
n이 작아 생각할 필요가 없기 때문에 전체 점을 체크하였습니다.

(x,y) 위치의 기둥은 checkFunc[0](x,y), 보는 checkFunc[1](x,y) 로 체크할 수 있도록
lamda list를 만들었습니다 (0,1로 연결지을 수 있도록)

check 함수는 전체 점을 체크하는 함수입니다. 이곳에서 checkFunc를 사용하여 (x,y)를 제거했을 때 전체 점이
여전히 조건을 만족하면 true 아니면 false를 return합니다.

입력받은 x,y에 1씩 더하여 map을 +1,+1씩 평행이동 시켰다고 생각하고 풀면 index 범위 체크를 하지 않아도 됩니다.

var map = Array(202){Array(202){BooleanArray(2)}}
var checkFunc = listOf(
    {x:Int,y:Int -> y==1 || map[x][y-1][0] || map[x-1][y][1] || map[x][y][1]},
    {x:Int,y:Int -> (map[x-1][y][1] && map[x+1][y][1]) || map[x][y-1][0] || map[x+1][y-1][0] }
)
fun check(x:Int,y:Int,n:Int):Boolean{
    for(i in 1..n+1)
        for(j in 1..n+1){
            if(map[i][j][0] && !checkFunc[0](i,j)) return false
            if(map[i][j][1] && !checkFunc[1](i,j)) return false
        }
   return true
}
class Solution {
    fun solution(n: Int, build_frame: Array<IntArray>): Array<IntArray> {
        for((tx,ty,a,b) in build_frame){
            var x = tx+1
            var y = ty+1
            if(b==0){
                map[x][y][a]=false
                if(!check(x,y,n)) map[x][y][a]=true
            }else{
                if(checkFunc[a](x,y)) {
                    map[x][y][a]=true
                }
            }
        }
        var lst = mutableListOf<IntArray>()
        for(i in 1..n+1){
            for(j in 1..n+1){
                if(map[i][j][0]) lst.add(intArrayOf(i-1,j-1,0))
                if(map[i][j][1]) lst.add(intArrayOf(i-1,j-1,1))
            }
        }
        return lst.toTypedArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/기둥과_보_설치.cpp

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

[난이도] level3
[유형] 플로이드 워셜

[풀이]

s에서 어떤 점 k(1~n)까지 같이 타고 갔다고 가정했을 때 요금의 최솟값은
s~k까지의 최단거리 + k~a의 최단거리 + k~b의 최단거리 입니다.
k를 1에서 n까지 바꿔보면서 최단거리를 모두 구해봤을 때의 최솟값이 정답입니다.
모든 점 (i,j)간의 최단거리를 구해야 하므로 플로이드 워셜 알고리즘을 이용하였습니다.

import java.lang.Integer.min
import java.util.*
const val inf = 20000001
var cost = Array(201){IntArray(201){inf} }
class Solution {
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var answer = inf
        for(v in fares){
            cost[v[0]][v[1]]=v[2]
            cost[v[1]][v[0]]=v[2]
        }
        for(i in 1..n) cost[i][i]=0

        for(k in 1..n){
            for(i in 1..n){
                for(j in 1..n){
                    if(cost[i][j] > cost[i][k]+cost[k][j]){
                        cost[i][j] = cost[i][k]+cost[k][j]
                        cost[j][i] = cost[i][j]
                    }
                }
            }
        }
        for(i in 1..n) answer = min(answer, cost[i][s] + cost[i][a] + cost[i][b])

        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/합승_택시_요금.cpp

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

[난이도] Silver3
[유형] 백트래킹

[풀이]
수열이 오름차순이어야 하므로 배열을 정렬해주고
백트래킹을 해주면 됩니다.

import java.util.*
val bw = System.`out`.bufferedWriter()
var N=0
var M=0
lateinit var arr:List<Int>
fun sol(n:Int,s:String){
    if(s.filter { it==' ' }.length==M){
        bw.write(s.trim()+'\n')
        return
    }
        for(i in n until N){
        sol(i, "$s ${arr[i]}")
    }
}
fun main() = with(System.`in`.bufferedReader()){
    val ip = readLine().split(' ').map { it.toInt() }
    N=ip[0]
    M=ip[1]
    arr = readLine().split(' ').map{it.toInt()}
    arr = arr.sortedWith{a,b-> a.compareTo(b)}
    sol(0,"")
    bw.close()
}

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