알고리즘

백준(수업)

• 2042 구간 합 구하기 3

import sys
input=sys.stdin.readline

n,m,k=map(int,input().split())
treeheight=0
length=n

while length !=0:
    length//=2
    treeheight+=1

treesize=pow(2,treeheight+1)
leftnodestartindex=treesize//2-1
tree=[0]*(treesize+1)

for i in range(leftnodestartindex+1,leftnodestartindex+n+1):
    tree[i]=int(input())

def settree(i):
    while i!=1:
        tree[i//2]+=tree[i]
        i-=1

settree(treesize-1)

def changeval(index,value):
    diff=value-tree[index]
    while index>0:
        tree[index]=tree[index]+diff
        index=index//2

def getsum(s,e):
    partsum=0
    while s<=e:
        if s%2==1:
            partsum+=tree[s]
            s+=1
        if e%2==0:
            partsum+=tree[e]
            e-=1
        s=s//2
        e=e//2
    return partsum

for _ in range(m+k):
    question,s,e=map(int,input().split())
    if question==1:
        changeval(leftnodestartindex+s,e)
    elif question==2:
        s=s+leftnodestartindex
        e=e+leftnodestartindex
        print(getsum(s,e))

백준(자습)

• 2941 크로아티아 알파벳

  
  

croatia=['c=','c-','dz=','d-','lj','nj','s=','z=']
alpha=list(str('abcdefghijklmnopqrstuvwxyz'))

mystr=str(input())

cnt=0
mod=[]

for i in range(len(croatia)):
    if croatia[i] in mystr:
        mystr=mystr.replace(croatia[i],'0')
        #c=c= 00

for i in range(len(alpha)):
    if alpha[i] in mystr:
        mystr=mystr.replace(alpha[i],'1')

mod=list(mystr) # ['0' '1'...]
for i in range(len(mod)):
    if mod[i]=='0' or '1':
        cnt+=1

print(cnt)

1) croatia 알파벳 / 전체 알파벳을 list에 집어넣고
2) croatia 알파벳이 입력한 문자열에 있으면 해당 크로아티아 알파벳을 0으로 바꿈
3) 전체 알파벳이 입력한 문자열에 있으면 알파벳을 1로 바꿈
4) 0 또는 1로 변경되어있는 mystr을 만들어둔 list에 넣고
5) list 길이만큼 반복하면서 0과1의 개수를 세서 cnt에 누적해서 더한 후 출력

위 방법처럼 안짜고 count 사용하면 훨씬 편하게 짤 수 있음,,

croatia=['c=','c-','dz=','d-','lj','nj','s=','z=']
alpha=list(str('abcdefghijklmnopqrstuvwxyz'))

mystr=str(input())

cnt=0

for i in range(len(croatia)):
    if croatia[i] in mystr:
        k=mystr.count(croatia[i])
        mystr=mystr.replace(croatia[i],'0')
        cnt+=k
for i in range(len(alpha)):
    if alpha[i] in mystr:
        k=mystr.count(alpha[i])
        cnt+=k

print(cnt)

• 1316 그룹 단어 체커

  
  

n=int(input())
cnt=n
for i in range(n):
    mystr=input()
    prev_str=''
    mystr_set=set()

    for j in mystr:
        if j not in mystr_set:
            mystr_set.add(j)
            prev_str=j
        elif prev_str==j:
            continue
        else:
            cnt-=1
            break

print(cnt)

1) 바로 전에 입력한 문자를 확인하기위한 prev_str
2) 내가 입력한 문자열을 집합의 형태로 받을 mystr_set
3) cnt = 내가 입력한 단어의 전체 개수
4) mystr 문자만큼 반복하면서 mystr_set에 해당 문자가 없다면 문자를 더해주고
prev_str에 없었던 문자를 받아옴 ex)abbba 면 prev_str에 a,b 순서대로 들어가서 다음 a를 만날때까지 prev_str이란 변수에는 b가 저장되어있음
5) prev_str을 만나면 즉 abbba일때 b가 연속되는 경우를 잡은것, 이 때는 continue로 그냥 for문 계속 반복
6) 그 외는 이전에 입력한 문자를 다시 만났기 때문에 cnt를 1 감소시켜줌 --> 전체에서 그룹단어가 아닌 단어를 찾으면 찾을때마다 줄이겠다는 뜻

코딩테스트

• 프로그래머스 LV1 카드 뭉치

  
  

def solution(cards1, cards2, goal): 
    for i in goal: # i = 'i'/'want'/'to'/'drink'/'water' 
        if len(cards1)>0 and i==cards1[0]: # i want to drink water을 cards1,cards2을 연속시켜 조합해서 만들수있는지 확인해야하기에 cards1과cards2의 첫번째 원소랑 계속 같아야 연속해서 만들수있는거임
            cards1.pop(0)#cards1.pop(0)으로 제일 앞에있는 원소를 계속 뽑아옴 
        elif len(cards2)>0 and i==cards2[0]: # len(cards)>0 없이 구현했는데 index 오류나면서 터짐 pop으로 다 뽑아서 cards2=[] 가 되었는데 if문 만족안해서 elif로 들어오고 i==cards2[0]으로 비교하려고 하니까 터짐
            cards2.pop(0)
        else:
            return 'No'
    return 'Yes'
>
cards1 = ["i", "drink", "water"] 
cards2 = ["want", "to"] 
goal = ["i", "want", "to", "drink", "water"]
>
print(solution(cards1, cards2, goal)) 
>
cards1 = ["i", "water", "drink"]
cards2 = ["want", "to"]
goal = ["i", "want", "to", "drink", "water"]
>
print(solution(cards1, cards2, goal)) 

• 프로그래머스 LV1 체육복

  
  

def solution2(n, lost, reserve):#(전체학생수,도난당한애들,빌려줄수있는애들)
    #마지막 조건 안읽어서 계속 코드 오류났음 --> 여벌이 있는애도 도둑맞을수 있어서 다음과 같이 집합처리
    reserve_set=set(reserve)-set(lost)
    lost_set=set(lost)-set(reserve)
    for i in reserve_set: #빌려줄 수 있는애들중에 
        front=i-1 #앞에있는애 ex.빌려줄 수 있는애가 3번이면 2번 
        back=i+1 #뒤에있는애 ex. 빌려줄 수 있는애가 3번이면 4번
        if front in lost_set: # ex. lost 애들중에 2번 즉 잃어버린애들중에 2번이 있으면
            lost_set.remove(front) # 3번애가 빌려줄수있는거니까 잃어버린 애들 목록에서 삭제해주고
        elif back in lost_set: # ex. lost 애들중에 4번 즉 잃어버린 애들중에 4번이 있으면
            lost_set.remove(back) # 3번애가 빌려줄 수 있으니까 목록에서 삭제해주고
    return n-len(lost_set) # 전체 길이에서 여분 있는애들이 다 빌려줬는데도 못받아서 없는애들만 빼주면 됨 



n = 5
lost = [2, 4]
reserve = [1,3,5]

print(solution2(n, lost, reserve)) # return 5


n = 5
lost = [2, 4]
reserve = [3]

print(solution2(n, lost, reserve)) # return 4


n = 3
lost = [3]
reserve = [1]

print(solution2(n, lost, reserve)) # return 2