[백준] 알고리즘 기초 1/2

200 - 자료구조 1

1) 1406번 에디터

• 2개의 stack을 활용하여 cursor의 위치 나타내고, append(), pop()만을 사용하여 시간 복잡도 줄이기

import sys
input=sys.stdin.readline
from collections import deque

x=list(input().rstrip()) # stack1
n=int(input())
stack=deque([]) # stack2
cursor=len(x) # stack1 x의 개수

for _ in range(n):
    say=input().rstrip()
    if say[0]=='L':
        if cursor==0:
            continue
        stack.appendleft(x.pop())
        cursor-=1
    elif say[0]=='D':
        # x와 stack의 길이 합이 x에 있는 원소 개수와 동일하면 x에 모두 존재한다는 뜻(cursor 맨 뒤)
        if cursor==len(x)+len(stack):
            continue
        x.append(stack.popleft())
        cursor+=1
    elif say[0]=='B':
        if cursor==0:
            continue
        x.pop()
        cursor-=1
    else:
        x.append(say[2])
        cursor+=1
print(''.join(x)+''.join(stack))

 

2) 17298번 오큰수

• 오큰수 : arr[i]보다 큰 수 중 가장 왼쪽에 있는 수

import sys
input=sys.stdin.readline
from collections import deque

n=int(input())
arr=list(map(int,input().split()))
result=[-1]*(n)
stack=[0]

for i in range(1,n):
    while stack and arr[stack[-1]]<arr[i]:
        result[stack.pop()]=arr[i]
    stack.append(i)
print(*result)

 

3) 17299번 오등큰수

import sys
input=sys.stdin.readline
from collections import deque

n=int(input())
arr=list(map(int,input().split()))
count_arr=[0]*1000001
result=[-1]*(n)
stack=[0]

for i in arr:
    count_arr[i]+=1

for i in range(1,n):
    while stack and count_arr[arr[stack[-1]]]<count_arr[arr[i]]:
        result[stack.pop()]=arr[i]
    stack.append(i)

print(*result)

 

GORI 대회

1) 1418번 K-세준수

import sys
input=sys.stdin.readline
import math

n=int(input())
k=int(input())
arr=[0]*(n+1) # 소수는 0
arr[1]=1
for i in range(2,int(math.sqrt(n))+1):
    if arr[i]==0:
        for j in range(i+i,n+1,i):
            arr[j]=1
            
result=[1]*(n+1)
for i in range(2,n+1):
    if arr[i]==0 and i>k:
        for j in range(i,n+1,i):
            result[j]=0
print(sum(result)-1)

 

300 - 수학 1

1) 2004번 조합 0의 개수

• 2와 5의 개수에 관한 규칙 사용

1. x2의 개수 : 짝수곱마다 증가
2. x5의 개수 : 5의 배수 곱마다 증가
3. if n==36, 5의 배수인 5,10,15,20,25,30,35에 counting+1씩 해주고, 25의 배수인 25에 counting+1

        if n==260, 260//5로 5^^1인 부분에 counting+1, 260//25로 5^^2부분에 counting+1

        즉, 25에는 counting+2

import sys
input=sys.stdin.readline

def countnum(n,num):
    count=0
    while n>0:
        count+=n//num
        n//=num
    return count
        
n,m=map(int,input().split())
print(min(countnum(n,2)-countnum(m,2)-countnum(n-m,2),countnum(n,5)-countnum(m,5)-countnum(n-m,5)))