bright

programmers.co.kr/learn/courses/30/lessons/12909#

from collections import deque 

def solution(s):
    
    q = deque()
    q.append(0)
    ans = 1
    
    for i in range(len(s)):
        if s[i] == '(' :
            q.append('(')
        else :
            ans = q.pop()
        
        if ans == 0 : 
            return False 
            
    if len(q) > 1 :
        return False 
    return True

만약 '(' 로 시작하지 않거나, '(' 보다 ')' 가 많으면 ans = 0 이 된다 => False 

for 문이 끝난 다음 q에 뭔가 남아 있으면 '(' 가 ')' 보다 많았다는 것이다 => False 

www.acmicpc.net/problem/1715

import heapq
import sys 
input = sys.stdin.readline 

n = int(input())
data = [] 
for i in range(n) : data.append(int(input()))
heapq.heapify(data)
result = 0 

while data:
  first = heapq.heappop(data)

  if len(data)<=0:   # 원소가 1개 이하일 때 
    break 
  
  second = heapq.heappop(data)
  heapq.heappush(data, first+second )
  result += first + second 

for i in data : 
  result += i 

print(result)

처음 더한 값들이 반복되어 더해지므로, 가장 작은 값부터 더해야한다. 

우선순위 큐를 이용해서 작은 값을 꺼낸다. 

programmers.co.kr/learn/courses/30/lessons/42842

def solution(brown, yellow):
    answer = []
    total = brown + yellow 
    
    p = set()
    for i in range(1,total+1):
        if total % i == 0 : 
            p.add( (i, total//i))
        
    for i,j in p :
        if i >= j :
            if (i-2)*(j-2) ==yellow:
                answer.append(i)
                answer.append(j)
                break 
    
    return answer

www.acmicpc.net/problem/1238

import heapq
import sys
input = sys.stdin.readline 

n, m, x = map(int,input().split())
# n 명, 도로 m 개 , x 마을에서 

graph= [ [] for i in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a].append((b,c))

def dij(start):
  q = []
  heapq.heappush(q, (0,start))
  dist = [1e9]*(n+1)
  dist[start] = 0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now]<d : continue 
    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q,(cost,i[0]))
  return dist 

result = [0]
dist_x = dij(x)
for i in range(1,n+1):
  result.append( dij(i)[x] + dist_x[i] ) 

print ( max(result) )

programmers.co.kr/learn/courses/30/lessons/64061

def solution(board, moves):
    
    doll = [0] # 쌓이는 인형 
    answer = 0

    for m in moves:
        for i in range(len(board)):
            if board[i][m-1] != 0 :

                if board[i][m-1] == doll[-1]:
                    answer += 2 
                    doll.pop()
                else: 
                    doll.append(board[i][m-1])
                board[i][m-1] = 0 
                break
        
    return answer

www.acmicpc.net/problem/9465

def sticker(n,data):

  data[0][1] += data[1][0] 
  data[1][1] += data[0][0] 

  for j in range(2,n):
    data[0][j] += max( data[1][j-2],  data[1][j-1] )
    data[1][j] += max ( data[0][j-2], data[0][j-1] )
  
  return max(data[0][n-1], data[1][n-1])

t = int(input())
t_print = []

for i in range(t):
  n = int(input())
  data = []
  for _ in range(2):
    data.append(list(map(int,input().split())))

  t_print.append ( sticker(n,data) )

for i in range(t):
  print( t_print[i] )

index 2 이상부터 2칸 전 대각선과 1칸 전 대각선 비교해서 더하기가 가능! 

# 11725

from collections import deque 

n = int(input()) # 노드의 수 

tree = [ [] for _ in range(n+1) ]
for i in range(n-1):
  a, b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)

def bfs():

  q = deque()
  q.append(1)
  visited = [0] * (n+1)
  visited[1] = 1

  while q :
    x = q.popleft()
    for i in tree[x]:

      if visited[i] == False:
        visited[i] = x
        q.append(i)
  
  return visited
    
result = bfs()

for i in range(2,len(result)):
  print(result[i])

visited 리스트에 부모 노드를 저장함. 

1 -> 1과 연결된 것의 부모를 1로 설정하고 방문 처리한 뒤, queue에 넣음 -> 반복.. 

# (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 

year = list(map(int,input().split()))

for result in range(1,7981):
  if result % 15 == year[0] or ( result%15 == 0 and year[0] == 15 ) :
    if result % 28 == year[1] or (result%28 == 0 and year[1] == 28 ) :
      if result % 19 == year[2] or ( result%19 == 0 and year[2] == 19) :
        print(result)

문제에 보면 주어진 시간이 2초로 긴 편이다. 

완전 탐색으로 접근해서 풀어도 무방하다. 

주의! 15/28/19 로 나누어 떨어지면 나머지는 0 이지만 표현되는 수는 15 임을 조심! 

# 난쟁이 키 합이 100 
from itertools import combinations 

height = [] 
for i in range(9):
  height.append(int(input()))

height.sort() 

combi = list(combinations(height,7))

for i in combi : 
  h_sum = 0 
  for k in range(7):
    h_sum += i[k]
  
  if h_sum == 100 : 
    result = i 
    break 

for k in range(7):
  print(result[k])

조합 ( combination ) 모듈을 통해 완전 탐색으로 풀이한다. 

조합의 결과는 튜플로 나옴에 유의한다. 

from itertools import combinations 

combi = list( combinations( 조합을 사용할 list , 조합할 단위 )) 

+ ) 순열은 순서가 의미 있는 조합이며, permutations 로 사용한다. 

S = input()
count = 1
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        count += 1
print( count//2 )

바뀌는 것을 세면, 실제 바뀐 것은 1번 인데 앞, 뒤로 카운트 되기 때문에 마지막에 2로 나누어 준다. 

처음 시작 할 때 바뀌는 것은 1 번만 카운트 되므로 count = 1 부터 시작한다.