🍀
Aloo Coding

컴퓨터 공부/👨‍💻 모각코

모각코 2회차 - 약점체크

letzgorats 2022. 11. 10. 21:23

모각코 두번째 회의 후 PART2. 약점체크를 풀며 준비운동을 했습니다!

확실히 저번주보다는 난의도가 높은 문제들인 것을 체감했습니다.

✏️ 준비운동 PART2. 약점체크

 

1. 연산자 끼워넣기

import sys
from collections import deque
# import copy
from itertools import permutations
input = sys.stdin.readline

n = int(input())
number_list= list((map(int,input().split())))
operator = list(map(int,input().split()))
real_operator = deque([])
for idx,x in enumerate(operator):
    if(idx==0):
        real_operator.append('+'*x)
    if(idx==1):
        real_operator.append('-'*x)
    if(idx==2):
        real_operator.append('x'*x)
    if(idx==3):
        real_operator.append('/'*x)
real_operator = "".join(real_operator)
real_operator = list(real_operator)

real_operator = list((set(list(map(''.join,permutations(real_operator))))))

max_sum = float("-inf")
min_sum = float("inf")
for operators in real_operator:
    sum = number_list[0]
    for idx,o in enumerate(operators):
        if o == "+":
            sum +=number_list[idx+1]
        elif o == "-":
            sum -=number_list[idx+1]
        elif o == "x":
            sum *=number_list[idx+1]
        elif o == "/":
            if(sum>=0): 
                sum //=number_list[idx+1]
            else:
                sum = -sum
                (sum) //= number_list[idx+1]
                sum = -sum
    if(sum>max_sum):
        max_sum = sum
    if(sum<min_sum):
        min_sum = sum

# print(real_operator)
print(max_sum)
print(min_sum)

* 조금 더 효율적인 코드 * 

import sys
from collections import deque
# import copy
from itertools import permutations
input = sys.stdin.readline

n = int(input())
number_list= list((map(int,input().split())))
add,sub,mul,div = map(int,input().split())

# 최댓값 최솟값 초기화
max_value = -1e9
min_value = 1e9

# 깊이 우선 탐색 메서드

def dfs(i,now):
    global min_value, max_value, add, sub, mul, div
    # 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
    if i == n :
        min_value = min(min_value,now)
        max_value = max(max_value,now)
    else:
        # 각 연산자에 대하여 재귀적으로 수행
        if add > 0 :
            add-=1
            dfs(i+1, now+number_list[i])
            add+=1
        if sub > 0 :
            sub-=1
            dfs(i+1, now-number_list[i])
            sub+=1
        if mul > 0 :
            mul-=1
            dfs(i+1, now*number_list[i])
            mul+=1
        if div > 0 :
            div-=1
            dfs(i+1, int(now/number_list[i])) # 나눌때는 나머지를 제거
            div+=1

dfs(1,number_list[0]) # 현재 number_list 0번째 값부터 시작하고 1번째 number_list부터 보면 된다.

print(max_value)
print(min_value)

 

 

2. 괄호의 값

import sys
input = sys.stdin.readline

s = input().strip()
bracket = []
answer = 0
tmp = 1

# for i in s: 말고 인덱스형식으로 접근해야 한다.
for i in range(len(s)):
    if s[i] == "(":
        tmp *= 2
        bracket.append(s[i])

    elif s[i] == "[":
        tmp *=3
        bracket.append(s[i])
        
    elif s[i] == ")":
        # bracket이 비어있거나 짝이 안맞는 쌍일 경우 올바르지 않은 괄호문자열 
        if len(bracket) == 0 or bracket[-1] == "[":
            answer = 0 
            break
        # 직전의 괄호가 '('으로 쌍이 맞을 때만 answer에 tmp저장
        if s[i-1] == "(":
            answer += tmp
        tmp //= 2
        bracket.pop()
    
    elif s[i] == "]":
        if len(bracket) == 0 or bracket[-1] == "(":
            answer = 0 
            break
        # 직전의 괄호가 '['으로 쌍이 맞을 때만 answer에 tmp저장
        if s[i-1] == "[":
            answer += tmp
        
        tmp //= 3
        bracket.pop()

if bracket:
    print(0)
else:
    print(answer)

 

3. 빗물

import sys
input = sys.stdin.readline

height, width = map(int,input().split())

block_list = list(map(int,input().split()))
highest = max(block_list)
standard = block_list.index(highest)    # 기준점(가장 높은 블록 중 가장 앞 블록)


answer = 0

tmp = block_list[0]
# standard 기준으로 왼쪽 순회
for idx in range(standard+1):
    if block_list[idx] > tmp:
        tmp = block_list[idx]
    answer += tmp-block_list[idx]

tmp = block_list[-1]
# standard 기준으로 오른쪽 순회
for idx in range(width-1,standard,-1):
    if block_list[idx] > tmp:
        tmp = block_list[idx]
    answer += tmp-block_list[idx]


print(answer)

 

4. 가르침

import sys
input = sys.stdin.readline

least = ['a','n','t','i','c'] # 배워야만 하는 언어(최소 알아야 하는 알파벳)
learned = [0] * 26

n, k = map(int,input().split())
words = [set(input().strip()[4:-4]) for _ in range(n)]
answer = 0 

if k < 5:
    print(0)
    exit()
elif k == 26:
    print(n)
    exit()

for c in least:
    learned[ord(c)-ord('a')] = 1  # 배웠으면 1


def dfs(idx,cnt):   
        global answer
        
        if cnt == k :
            readcnt = 0
            # print(words)
            for word in words:
                check = True
                for w in word:
                    if not learned[ord(w) - ord('a')]:
                        check = False
                        break
                if check:
                    readcnt += 1
            answer = max(answer,readcnt)
            return 
    
        for i in range(idx,26):
            if not learned[i]:
                learned[i] = True	# 배웠다고 하고
                dfs(i, cnt+1)		# dfs 돌리기
                learned[i] = False	# 다시 백트래킹
    
    
dfs(0,5)    # idx 0 부터 시작, 최소 5개 아니까 5로 시작
print(answer)

 

5. 멀티탭 스케줄링

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


N, K = map(int,input().split()) # 멀티탭 구멍수 N, 전기용품 총 사용횟수 K
electronic = list(map(int,input().split())) # 전기용품 이름 사용 순으로 입력

powerbar = deque([])
answer = 0

for idx, elec in enumerate(electronic):
    if elec in powerbar:

        if elec in electronic[idx+1:]:
            continue # 유지

        elif elec not in electronic[idx+1:]:
            powerbar.rotate(-1)    # 코드 빼는 우선순위 뒤로

    elif elec not in powerbar:
        if len(powerbar) != N : # 길이가 꽉 차있지 않다면
            
            if elec not in electronic[idx+1:]:   # 사용하고자 하는 전기용품 살펴보고 없으면
                powerbar.appendleft(elec)        # 앞에다가 append
            elif elec in electronic[idx+1:]:     # 뒤에 또 있으면
                powerbar.append(elec)            # 뒤에다가 append

        elif len(powerbar) == N : # 길이가 꽉 차있으면
    
            powerbar.popleft() # 빼는 우선순위가 가장 높은 원소 빼고
            answer += 1        # answer + 1
            
            if elec not in electronic[idx+1:]:
                powerbar.appendleft(elec)
            elif elec in electronic[idx+1:]:
                powerbar.append(elec)
        
    
print(answer)

 

6. 부분합

import sys
input = sys.stdin.readline

N, S = map(int,input().split())
numbers = list(map(int,input().split()))

left, right = 0, 0	# 시작 위치, 끝 위치
sumVal = 0
answer = int(1e9)

while True:

    # left 부터 right 까지 합이 S 이상이라면
    if sumVal >= S:
        answer = min(answer,right-left) # 기존 answer와 right-legt 중에 작은 값 선택
        sumVal -= numbers[left] # left값 빼보고 
        left += 1   # 시작 위치인 left 값 1 증가

    # left 부터 right 까지 합이 S를 넘지 않는다면
    else:
        if right == N:  # 맨 끝의 위치가 N이 된다면 중단
            break
        sumVal += numbers[right]
        right += 1

if answer == int(1e9):
    print(0)
else:
    print(answer)

 

7. 최소비용 구하기

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
    queue = []
    # 시작노드로 가기 위한 최단 경로는 0으로 설정한 후, 큐에 삽입
    heapq.heappush(queue,(0,start))
    distance[start] = 0 
    while queue:
        dist, now = heapq.heappop(queue)
        # distance[now] 의 값이 큐에서 뽑아 낸 dist보다 이미 작은 경우는 무시
        if distance[now] < dist:
            continue
        else:
            # 현재 노드와 연결된 다른 인접한 노드들을 확인
            for i in graph[now]:
                cost = distance[now] + i[1]
                # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(queue,(cost,i[0]))

N = int(input())     # 도시 개수
M = int(input())    # 버스 개수

graph = [[] for _ in range(N+1)]
# print(graph)
INF = int(1e9)
distance = [INF] * (N+1)    # 최단 거리 테이블 (무한으로 초기값 설정)

for _ in range(M):
    a, b, c = map(int,input().split())  # 출발, 도착, 비용
    graph[a].append((b,c))

cityA, cityB = map(int,input().split())
dijkstra(cityA)
print(distance[cityB])

 

8. 최소 스패닝 트리

import sys
input = sys.stdin.readline

# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b :
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int,input().split())
parent = [0] * (v+1)  # 부모 테이블 초기화 

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a,b, cost = map(int,input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost,a,b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않은 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost

print(result)

 

9. 부분 문자열

import sys
input = sys.stdin.readline

S = input().strip()
P = input().strip()

if P in S:
    print(1)
else:
    print(0)

 

10. 줄 세우기

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

N, M = map(int,input().split()) # N은 학생 수, M은 키를 비교한 횟수

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (N+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for _ in range(N+1)]


for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b) # 학생 A 다음에 학생 B를 세워야 한다. 
    # 진입차수 1 증가
    indegree[b] += 1


# 위상 정렬 
def topology_sort():
    result = [] # 알고리즘 수행 결과를 담을 리스트
    q = deque() # 큐 기능을 하는 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)
    
    # 큐가 빌 때까지 반복
    while q : 
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
    
    # 위상 정렬을 수행한 결과 출력
    for i in result :
        print(i,end=" ")

topology_sort()

 

 

 

 

반응형
저작자표시

'컴퓨터 공부 > 👨‍💻 모각코' 카테고리의 다른 글

모각코 6회차 - 웹 스크래핑을 통한 정보 추출  (0) 2022.11.30
모각코 5회차 - DBMS 성능 개선 알고리즘 소개  (0) 2022.11.30
모각코 4회차 - SQLD 자격증 공부  (0) 2022.11.14
모각코 3회차 - 각자 문제풀이  (2) 2022.11.11
모각코 1회차 - 준비운동  (2) 2022.10.05

'컴퓨터 공부/👨‍💻 모각코'의 다른글

  • 현재글모각코 2회차 - 약점체크

관련글

댓글

티스토리툴바