코딩하는 eroke

문제

문자열에서 금지된 단어 (banned)를 제외한 단어들 중 가장 빈도수가 높은것을 출력하는 문제이다.

입출력

#Case 1
Input: s = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"

#Case 2
Input: s = "a.", banned = []
Output: "a"

#Case 3
Input: s = "Bob", banned = []
Output: "bob"

풀이

class Solution:
    def mostCommonWord(self, s: str, banned: List[str]) -> str:
        
        word = []       
        dic = collections.defaultdict(int)
        s = s.lower()
        
        for x in s : 
            if x.isalpha() == True:
                word.append(x)
            
            else:
                w = "".join(word) #list > str
                if w not in banned and w != '': 
                    dic[w]+=1
                word=[]
        
        #for문에서 else문 안 탄 경우 딕셔너리 추가 
        w = "".join(word)  
        if w not in banned and w != '': 
            dic[w]+=1
                    
        res = collections.Counter(dic)
        
        #Couter 객체의 가장 빈도수가 높은 key값(단어) return
        return res.most_common(1)[0][0]

문제

팰린드롬 : 앞뒤가 똑같은 단어/문장
주어진 문자열이 팰린드롬인지 검증하는 문제이다. 대소문자는 구분하지 않고, 영문자와 숫자만 해당된다.

#예제
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

풀이

#1 deque 사용 
class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        s = s.lower()
        dq = collections.deque()
        
        for x in s:
            if x.isalnum():
                dq.append(x)
                
        while len(dq) > 1 : 
            if dq.popleft() != dq.pop():
                return False
            
        return True

#2 슬라이딩 사용 
class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        s = s.lower()
        result = []
        
        for x in s:
            if x.isalnum():
                result.append(x)
                
        if result == result[::-1] :    
            return True
       
        return False

결과

문제

(코딩테스트 연습 > 2021 카카오 채용연계형 인턴십 > 숫자 문자열과 영단어)

입출력 (s : str, result : int) 예시대로 영단어는 숫자로 변환하면 된다.

풀이

def solution(s: str) -> int: #인자 자료형, 메소드 반환형 명시
    result = s
    dict = {'zero': '0', 'one': '1', 'two': '2', 'three': '3', 'four': '4',
            'five': '5', 'six': '6', 'seven': '7', 'eight': '8', 'nine': '9'}

    for item in dict.items():
        result = result.replace(item[0], item[1])

    return int(result)

파이썬 딕셔너리와 items()을 이용해 풀이했다.

문제

0~23시간 동안 시간 별로 집계된 입양 횟수 조회하기 

Solution (MySQL)

with recursive num(h) as (
    select 0 as h
    union all
    select h+1
    from num
    where h<23
)

select t1.h as HOUR, count(HOUR(t2.datetime)) as COUNT
from num as t1
left join animal_outs as t2
on t1.h=hour(t2.datetime)
group by t1.h

결과

'SQL에서 재귀는 처음 써봤당 신기,,

문제

Solution (MySQL)

SELECT id,name,p2.host_id from places as p1
inner join (
    select host_id, count(host_id) as cnt from places
    group by host_id
    having cnt>=2
)as p2
on p1.host_id=p2.host_id
order by ID

결과

문제 : 

오랜만에 그리디 문제도 풀어봤다.

그리디로 풀어야되는데 감잃고 고냥 조합으로 구하다가 메모리 초과로 실패 한번 띄우고 정렬해서 다시 풀었다.. (반성중)

그리디와 정렬은 뗄 수 없다는 사실!!! 잊지말자!!!!

풀이 1

N=int(input())
t=list(map(int,input().split()))
G=[]

for i in range(N):
    G.append((i+1,t[i]))
G.sort(key=lambda x: x[1])
#print(G)
tmp=res=0
for x,y in G:
    tmp+=y
    res+=tmp
print(res)

파이썬 sort()는 lamba를 이용해서 정렬 조건을 추가할 수 있다.

다중 조건일 때는 튜플을 이용하자  G.sort(key = lambda x : (x[0], -x[1]))

풀이 2

n=int(input())
p = list(map(int,input().split()))
p.sort()

res=[0]*n
res[0]=p[0]
for i in range(1,n):
    res[i] = res[i-1]+p[i]

print(sum(res))

나중에 보니 굳이 튜플로 풀지 않아도 되는 문제여서 다시 풀었다. (속도도 개선됨!)

문제 : 

Solution

import sys
from collections import deque
dq=deque()
op=deque()

N=int(input())
x=int(input())

for i in range(1,x+1):
    dq.append(i)
    op.append('+')

maxx=dq[-1]
dq.pop()
op.append('-')

for i in range(N-1):
    x=int(input())
    while x>maxx:
        maxx+=1
        dq.append(maxx)
        op.append('+')
    if len(dq)==0:
            print("NO")
            sys.exit(0)
    while x<dq[-1]:   
        dq.pop()
        op.append('-')    
    dq.pop()
    op.append('-')

for x in op:
    print(x)

자기 자신도 빼주는게 중요하당

1년 전 C++로 풀었을 땐 틀렸는데 올해 파이썬 시작하고 다시 풀어보니 맞았다,,8ㅅ8

꾸준히 공부하니 조금씩 성장하는게 느껴진다 무야호 ~

문제 :

한 달 전까지 못 풀던 문제를 다시 도전해보았다.

단순 위상정렬로만 접근해서는 틀린다고 나온다 ㅠㅠ 

건물들은 동시에 여러 개를 지을 수 있으므로 의존성 있는 건물 중 오래 걸리는 시간으로 갱신하며 계산되어야 한다..

Solution 1 : 2차원 배열

from collections import deque
N=int(input())
val=[0]*N

G=[[0]*N for _ in range(N)]
degree=[0]*N
dq=deque()

for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[i][tmp[j]-1]=1
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for i in range(N):
        if G[i][x]==1:
            degree[i]-=1
            res[i]=max(res[i],res[x]+val[i])
            if degree[i]==0:dq.append(i)        

for x in res:
    print(x)

res[i]=max(res[i],res[x]+val[i]) << 이 부분이 핵심이다

첫 번째 풀이는 2차원 배열에 연결성을 부여해 접근하였다.

파이썬의 defaultdict 을 이용하면 선행되어야 하는 건물에 의존적인 건물들을 추가하여 풀이할 수 있다.

개인적으로 첫 번째 풀이가 맘에 들지만 아래처럼 접근해야 하는 경우도 있을 것 같아 추가한다.

Solution 2 : defaultdict

from collections import deque, defaultdict
N=int(input())
val=[0]*N

G=defaultdict(list)
degree=[0]*N
dq=deque()


for i in range(N):
    tmp=list(map(int,input().split()))
    val[i]=tmp[0]
    for j in range(1,len(tmp)-1):
        G[tmp[j]-1].append(i)
        degree[i]+=1

res=[0]*N
for i in range(N):
    if degree[i]==0:
        dq.append(i)
        res[i]=val[i]        

while dq:
    x=dq.popleft()
    for y in G[x]:
        res[y]=max(res[y], res[x]+val[y])
        degree[y]-=1
        if degree[y]==0:
            dq.append(y)

for x in res:
    print(x)

이런식으로 선행되어야하는 건물: [의존건물들] 로 딕셔너리가 형성된다. 

(defaultdict는 딕셔너리를 리스트처럼 사용할 수 있게 해주는 라이브러리)

백준 수 찾기 에 이어 백분 이분탐색 카테고리의 문제를 풀려했는데

'수 찾기' 문제랑 너무 비슷해서 그냥 이것도 딕셔너리로 풀어버렸다..

문제 

Solution

#숫자카드 2
N=int(input())
A={}
a=map(int,input().split())

for x in a:
    if x not in A:
        A[x]=1
    else: A[x]+=1

M=int(input())
b=map(int,input().split())

for x in b:
    if x not in A: print(0,end=' ')
    else: print(A[x],end=' ')

다음은 진짜진짜 이분탐색으로 풀어야지...

이분탐색 연습 좀 하려고 간만에 백준 사이트에 들어갔다.

문제:

웬걸 연습하려는 이분탐색은 안쓰고 딕셔너리로 풀었다.. 

Solution

N=int(input())
A={}
a=map(int,input().split())

for x in a:
    if x not in A:
        A[x]=1

M=int(input())
b=map(int,input().split())

for x in b:
    if x not in A: print(0)
    else: print(1)

랜선자르기나 풀러 가야지,.