프로그래밍

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

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

[풀이]
nCm 은 n!/(m!x(n-m)!) 로 표현된다.

문제 https://www.acmicpc.net/problem/1676 에서 봤듯이 끝의 0의 개수는 어떤 수를 소인수분해 했을 때 5x2가 몇개나 있는지에 따라 결정된다.
n!/(m!x(n-m)!) 식에서 2와 5가 최종적으로 몇개 남는지를 구하고 둘중 최솟값을 출력하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min
fun get(p:Int,k:Int):Int{
    var cnt=0
    var n=p
    while(n>0){
        n/=k
        cnt+=n
    }
    return cnt
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val ip=readLine().split(' ')
    val N=ip[0].toInt()
    val M=ip[1].toInt()
    val a = get(N,2)-get(N-M,2)-get(M,2)
    val b = get(N,5)-get(N-M,5)-get(M,5)
    println(min(a,b))
}

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

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

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

[풀이]
모든 10은 2x5로 만들어지기 때문에 1~N 모든 수를 소인수 분해 했을 때 2와 5의 개수 중의 최솟값이 답이다.
항상 5가 더 적은 것이 보장되기 때문에 5의 개수만 구하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val N=readLine().toInt()
    var cnt:Int=0
    for(i in 1..N) {
        var j=i
        while(j>0 && j%5==0){
            cnt++
            j/=5
        }
    }
    println(cnt)
}

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

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

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

[풀이]
에라토스테네스의 체를 이용해 소수를 미리 구해준다

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.IndexOutOfBoundsException
import java.util.*
const val mxN = 1000000
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    var list = ArrayList<Int>()
    var nP = BooleanArray(mxN+1)
    nP[1]=true

    for(i in 2..mxN/2){
        if(nP[i]) continue
        var j=i*2
        while(j<=mxN){
            nP[j]=true
            j+=i
        }
    }
    for(i in 2..mxN) {
        if(!nP[i]) list.add(i)
    }
    while(true){
        var ip = readLine().toInt()
        if(ip==0) break

        for(a in list){
            if(!nP[ip-a]){
                println("$ip = $a + ${ip-a}")
                break;
            }
        }
    }
}

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

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

[난이도] Silver2
[유형] 에라토스테네스의 체

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ')
    var n=ip[0].toInt()
    var m=ip[1].toInt()
    var notPrime = BooleanArray(1000001)
    notPrime[1]=true
    for(i in 2..m){
        if (notPrime[i]) continue
        var j = i*2
        while(j<=m){
            notPrime[j]=true
            j+=i
        }
    }
    for(i in n..m) if(!notPrime[i]) println(i)
}

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

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

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

[풀이]
스택 문제이지만 스택을 사용하지 않아도 해결이 가능하다.

0~N-1 문자를 순회하면서
1) s[i]가 '(' 인 경우 s[i+1]이 ')' 이면 레이저이고 아니면 쇠막대기의 왼쪽끝이다.
쇠막대기인 경우, 현재 쌓여있는 막대 개수 cnt를 1 증가시켜준다
레이저인 경우, 현재 쌓인 막대기만큼 ans에 더해주고 index를 한칸 넘어간다 ( ')'를 스킵해야 하므로 )

2) s[i]가 ')' 인 경우
막대가 끝났으므로 cnt를 1 감소시키고
ans에 1을 더해준다. 왜나하면 막대의 맨 오른쪽 조각을 더해줘야 하므로

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var cnt=0
    var ans=0
    var i=0
    while(i<s.length){
        when(s[i]){
            '('->{
                if(s[i+1]==')') {
                    ans+=cnt
                    i++
                }
                else cnt++
            }
            else->{
                ans++
                cnt--
            }
        }
        i++
    }
    println(ans)
}

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

[20210510] 큐
[BOJ/백준][Silver4] 10845 : 큐 (Kotlin)

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

[난이도] Silver4
[유형] 큐

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var q:Queue<Int> = LinkedList<Int>()
    while(n-->0){
        var ip=readLine().split(' ')
        when(ip[0]){
            "push"->q.add(ip[1].toInt())
            "pop"-> println(if(q.isEmpty()) -1 else q.poll())
            "empty"->println(if(q.isEmpty()) 1 else 0)
            "front"->println(if(q.isEmpty()) -1 else q.peek())
            "back"->println(if(q.isEmpty()) -1 else q.last())
            else->println(q.size)
        }
    }
}

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

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

[난이도] Silver4
[유형] 큐

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var q:Queue<Int> = LinkedList<Int>()
    while(n-->0){
        var ip=readLine().split(' ')
        when(ip[0]){
            "push"->q.add(ip[1].toInt())
            "pop"-> println(if(q.isEmpty()) -1 else q.poll())
            "empty"->println(if(q.isEmpty()) 1 else 0)
            "front"->println(if(q.isEmpty()) -1 else q.peek())
            "back"->println(if(q.isEmpty()) -1 else q.last())
            else->println(q.size)
        }
    }
}

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

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

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

[풀이]
Left Stack와 Right Stack 두가지 스택을 이용하여 문제를 해결하면 된다.
커서를 우측으로 옮길때는 Left stack의 top을 Right stack으로,
그 반대는 Right stack의 top를 Left stack으로,
커서에 문자를 추가하거나 제거할때는 Left stack에 추가,제거

LinkedList를 이용해도 삽입,제거 연산이 O(1)이므로 문제를 시간내에 풀 수 있다.
Kotlin에서 List가 아닌 LinkedList를 사용해야한다.

[스택 풀이]

  
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    val lst = Stack<Char>()
    var rst = Stack<Char>()
    for(a in s) lst.push(a)
    for(i in 1..readLine().toInt()) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if(!lst.empty()) rst.push(lst.pop())
            "D" -> if(!rst.empty()) lst.push(rst.pop())
            "B" -> if(!lst.empty()) lst.pop()
            else -> {
                lst.push(ip[1][0])
            }
        }
    }
    println(lst.toCharArray()+rst.toCharArray().reversed())
}

[LinkedList 풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var list = LinkedList<Char>()
    for(a in s) list.add(a)
    var it = list.listIterator()
    while(it.hasNext()) it.next()
    var n = readLine().toInt()
    for(i in 1..n) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if (it.hasPrevious()) it.previous()
            "D" -> if (it.hasNext()) it.next()
            "B" -> {
                if (it.hasPrevious()) {
                    it.previous()
                    it.remove()
                }
            }
            else -> it.add(ip[1][0])
        }
    }
    println(list.toCharArray())
}

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