프로그래밍

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

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

[풀이]
'a'의 index를 찾고 왼쪽 index l 오른쪽 index r을 유지하면서
'b','c','d'..가 순서대로 l,r 둘중 하나에 존재하는지를 체크해줍니다.
만약 지금 나와야하는 알파벳이 l,r 둘중 하나에 없다면 NO를 출력해주고,
모든 알파벳을 찾을 수 있다면 YES를 출력합니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int tc;
string s;

bool solve(){
    int cur=-1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='a') {
            cur=i;
            break;
        }
    }
    if(cur==-1) return false;
    int l=cur,r=cur;

    int sz = s.size()-1;
    char target='b';
    while(sz--){

        if(l-1>=0){
            if(s[l-1]==target){
                l--;
                target++;
                continue;
            }
        }
        if(r+1<s.size()){
            if(s[r+1]==target){
                r++;
                target++;
                continue;
            }
        }
        return false;
    }
    return true;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        cin >> s;
        string ret = solve()?"YES":"NO";
        cout << ret << '\n';
    }

}

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

https://codeforces.com/contest/1547/problem/A

[난이도] Div.3
[유형] 구현

[풀이]
tc가 10^4인걸 생각 못하고 BFS로 풀었다가 TLE를 맞았습니다.
A,B,F가 모두 다른 점이므로 O(1)에 계산이 가능하다는 것을 파악해야합니다.
만약 A,B,F가 일직선상에 있지 않다면 최단거리가 여러 가지이므로 F에 의해 한 경로가 막힌다 하더라도
다른 경로를 이용하면 되므로 무조건 dist(A,B) 만큼이 최단 거리가 됩니다.

만약 A,B,F가 일직선 상에 있고 A,B 사이에 F가 있다면 유일한 최단 거리 dist(A,B)가 막힌 것이므로
F를 피해서 가는 이동 2를 더해줘야 하므로 dist(A,B)+2가 정답이 됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int tc,sy,sx,ey,ex,fy,fx;
bool visit[1001][1001];

bool same(int a,int b,int c){
    return (a==b&&b==c);
}
bool between(int a,int b,int c){
    if(a>c) swap(a,c);
    return (a<b&&b<c);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&fx,&fy);
        int ans = abs(sx-ex)+abs(sy-ey);
        if(same(sx,fx,ex)&&between(sy,fy,ey) || same(sy,fy,ey)&&between(sx,fx,ex)){
            ans+=2;
        }
        printf("%d\n",ans);
    }
}

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

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

[난이도] Silver4
[유형] Set

[풀이]
Set,정렬

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
import kotlin.collections.HashSet
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N,M) = readLine().split(' ').map{it.toInt()}

    var st = HashSet<String>()
    var arr = mutableListOf<String>()
    while(N-->0) st.add(readLine())
    while(M-->0){
        var s = readLine()
        if(st.contains(s)) arr.add(s)
    }
    arr.sort()
    println(arr.size)
    for(a in arr) println(a)
}

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

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val mp = HashMap<Int,Int>() // 순서가 필요한 경우 TreeMap 사용

    mp[1]=1 // 데이터 삽입시
    mp[2]=2
    mp[3]=3

    mp[1]=(mp[1]?:0)+1 // 기존 데이터를 이용한 수정시 (예를 들어 1증가) null체크를 위해 엘비스 연산자 사용

    for((key,value) in mp){
        println("key:$key value:$value")
    }
//    출력
//    key:1 value:2
//    key:2 value:2
//    key:3 value:3
}

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val mp = HashMap<Int,Int>() // 순서가 필요한 경우 TreeMap 사용

    mp[1]=1 // 데이터 삽입시
    mp[2]=2
    mp[3]=3

    mp[1]=(mp[1]?:0)+1 // 기존 데이터를 이용한 수정시 (예를 들어 1증가) null체크를 위해 엘비스 연산자 사용

    for((key,value) in mp){
        println("key:$key value:$value")
    }
//    출력
//    key:1 value:2
//    key:2 value:2
//    key:3 value:3
}

코틀린에서 map을 사용하는 예시입니다.

C++처럼 mp[1]++ 이런 연산은 안되고 엘비스 연산자를 이용해

mp[1]=(mp[1]?:0)+1 이렇게 해주어야 하는것이 불편하네요. 

var default_pq = PriorityQueue<Int>()
default_pq.add(5)
default_pq.add(3)
default_pq.add(7)
println("default")
while(!default_pq.isEmpty()){
println(default_pq.poll())
}
// default
// 3
// 5
// 7

var reverse_pq = PriorityQueue<Int>{a,b-> b.compareTo(a)}
reverse_pq.add(5)
reverse_pq.add(3)
reverse_pq.add(7)

println("reverse")
while(!reverse_pq.isEmpty()){
println(reverse_pq.poll())
}
// reverse
// 7
// 5
// 3

var pq = PriorityQueue<T>()

와 같이 우선순위큐를 생성할 수 있습니다.

C++과 다르게 comparator 전달 없이 생성하면 pop시에 작은 수부터 나오게 됩니다.

 큰 수부터 나오게 하기 위해서는 두번째 예와 같이 람다 comparator를 전달해주면 됩니다.

sortWith + 사용자정의 comparator

    var arr1 = mutableListOf(5,4,2,7,1)
    arr1.sortWith{a,b-> b.compareTo(a)} // [7, 5, 4, 2, 1]


    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(1,3),Pair(2,5),Pair(2,4),Pair(6,2))
    arr2.sortWith{ a, b ->
        var k:Int = a.first.compareTo(b.first)
        when(k){
            0 -> a.second.compareTo(b.second)
            else -> k
        }
    } // [(1, 3), (2, 4), (2, 5), (6, 2)]
   
    println(arr1.toString())
    println(arr2.toString())

알고리즘 문제를 풀 때 문제에 따라 사용자 정의 comparator를 전달해서 정렬을 해야하는 경우가 종종 있습니다.

C++에서와 비슷하게 코틀린에서도 컬렉션 sortWith 메소드에 Comparator 구현체를 전달하면 사용자가 원하는 방식으로 정렬을 할 수 있습니다.

Pair도 역시 C++과 비슷한 방식으로 정렬이 가능합니다.

sortWith + compareBy / sortedBy

fun main(){

    var arr1 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    arr1.sortWith(compareBy({it.first},{it.second}))

    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    var parr2 = arr2.sortedBy{it.second}.sortedBy{it.first}

    println(arr1.toString())  // [(1, 3), (2, 4), (2, 5), (6, 2)]
    println(parr2.toString()) // [(1, 3), (2, 4), (2, 5), (6, 2)]
}

우와 같이 sortWith에 comparator를 return해주는 compareBy를 전달하는 방법도 있습니다.

compareBy({1순위로 비교할 프로퍼티},{2순위로 비교할 프로퍼티}....) 처럼 넣어주면 됩니다.

위 예제에서는 it.frst, it.second를 순서로 전달함으로써 first를 우선으로 비교하고, 같으면 second로 비교해서 오름차순으로 정렬하라는 의미입니다.

sortedBy를 이용하는 방법도 있습니다.

sortedBy{비교할 프로퍼티} 으로 써주면 적어준 프로퍼티 기준으로 오름차순 정렬합니다.

arr2에서 해주는 것과 같이 pair의 second부터 정렬해주고, first를 정렬하면 first를 1순위, second를 2순위로 비교해서 정렬하는 것과 같은 효과입니다.

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

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

[풀이]
N과 M제한이 30이지만 모든 점에서 4방향으로 가는 재귀함수를 호출하면 시간초과가 날 것이다.
하지만 현재 가고 있는 방향 d도 인자로 전달해서 d로 갈수 있다면 나머지 3 방향은 체크할 필요가 없이
d로 진행하면 된다.
즉, 방향을 바꿔야 하는 곳에서만 갈 수 있는 곳으로 재귀함수를 호출해주면 되므로
많은 케이스가 프루닝되어 시간내에 문제를 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dy[5]={-1,1,0,0,1000};
int dx[5]={0,0,1,-1,1000};
int N,M,total,ans,inf=987654321;
char map[31][31];
bool visit[31][31];
bool check(int y,int x,int d){
    int ny=y+dy[d];
    int nx=x+dx[d];
    return !(ny<0||nx<0||ny>=N||nx>=M||map[ny][nx]=='*'||visit[ny][nx]);
}
void sol(int y,int x,int d,int cnt,int t){
    visit[y][x]=1;
    if(t==total){
        ans=min(ans,cnt);
        visit[y][x]=0;
    }
    if(check(y,x,d)){
        sol(y+dy[d],x+dx[d],d,cnt,t+1);
    }else{
        for(int i=0;i<4;i++){
            if(check(y,x,i)){
                sol(y+dy[i],x+dx[i],i,cnt+1,t+1);
            }
        }
    }
    visit[y][x]=0;
}

int main(){
    int s=0;
    while(scanf("%d%d",&N,&M)!=-1){
        memset(map,0,sizeof(map));
        ans=inf;
        total=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++) {
                scanf(" %c",&map[i][j]);
                if(map[i][j]=='.') total++;      
            }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]=='.'){
                    memset(visit,0,sizeof(visit));
                    sol(i,j,4,0,1);
                }
            }
        }
        if(ans==inf) ans=-1;
        printf("Case %d: %d\n",++s,ans);
    }
}

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

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

[난이도] Gold2
[유형] Union-Find

[풀이]
어떤 비행기에게 g가 주어졌을 때 이 비행기는 1~g중 비어있는 아무 게이트에 도킹이 가능하다는 의미이다.
이때, g에 가까운 쪽에 도킹할수록 이후에 비행기들이 도킹하기에 유리하다는 것을 알 수 있다.
모든 비행기에 대해 g부터 1까지 검사하면서 빈 곳에 채우면 N이 10만이므로 O(N^2)이 되어 시간초과에 걸리게 된다.
이를 방지하기 위하여 union find 알고리즘을 이용해야 한다.
uf[G]를 선언한다. uf[i]의 의미는 어떤 비행기가 1~i번 게이트에 도킹해야할 때,
도킹해야하는 게이트의 index를 저장하는 배열로 생각할 수 있다.
만약 uf[i]!=i 라면 uf[i]는 root가 아니므로 uf[uf[i]]를 다시 탐색해야 한다.
이는 union find에서 흔히 사용하는 재귀를 이용한 find 함수로 구현할 수 있다.
재귀를 통해 uf[i]==i인 경우가 나오면 i를 return해준다.
uf[i]==i의 의미는 i에 도킹해야하는 비행기가 들어오면 i에 도킹하는것이 최적이라는 의미이다. 즉, i는 아직 도킹이 안되었다는 의미이다.
i가 return 되었으면 i에는 비행기가 도킹되게 되어 i에는 더이상 도킹할 수 있으므로
uf[i]를 i-1로 변경해준다.

만약 return된 i가 0이라면 도킹해야할 칸이 다 찼다는 의미이므로 반복문을 멈추고 지금까지 누적된 도킹 가능한 비행기 개수를 출력해주면 된다.

#include <cstdio>
const int mxN=1e5+1;
int uf[mxN],G,P;
int find(int n){
    if(n==uf[n]) return n;
    return uf[n]=find(uf[n]);
}
int main(){
    scanf("%d%d",&G,&P);
    for(int i=1;i<=G;i++) uf[i]=i;
    int ans=0;
    for(int i=1;i<=P;i++){
        int v;
        scanf("%d",&v);
        int k = find(v);
        if(k==0) break;
        uf[k]=k-1;
        ans++;
    }
    printf("%d",ans);
}

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