지금까지는 코테에 익숙해지기 위해 python으로 풀이해왔는데 내가 원하는 백엔드 개발자는 java, node, kotlin으로 코테를 쳐야한다. 실제로 지원하려는 회사가 저 3개의 언어만으로 쳐야한다고 한다. 언어를 kotlin으로 바꿔야겠다.

14889번 스타트 vs 링크 축구팀 나누기

두 팀의 능력치가 최소가 되도록 해야함. 어제 1시간 30분 걸렸나? 1시간 걸렸나… 기억이 안나네. dp는 절대 아니고 dfs 밖에 없다고 생각했음. 그런데 20C10 이 경우의 수라 dfs 하면 백퍼 시간초과 날 것 같았는데 백트래킹이 살림… 20C10이면 10^10 / 10! 이어서 들어올 수 있엇나보다.

import sys
sys.setrecursionlimit(10**8)

n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
whole = set([i for i in range(1, n+1)])
start = set()


def dfs(m):
    global ans

    if len(start) == n / 2:
        link = whole - start 
        sumS = 0
        sumL = 0
        # s[i][i] = 0 이므로 더해져도 상관 없다.
        for a, c in zip(start, link):
            for b, d in zip(start, link):
                sumS += s[a-1][b-1]
                sumL += s[c-1][d-1]        

        ans = min(ans, abs(sumS - sumL))
        return

    for i in range(m, n+1):
        if i not in start:
            start.add(i)
            dfs(i+1)
            start.discard(i)

dfs(1)
print(ans)

집합은 요소 삭제할 때 remove가 아닌 discard를 쓰고 O(1)이다. 굿~ for i in range(m, n+1) 요 부분의 백트래킹(가지치기)가 주요했음. 이거 아니면 시간초과 남. N과 M 문제로 훈련한 덕분에 잘 풀 수 있었다. 고맙다! 이렇게 하면 중복으로 고르는 경우를 없앨 수 있음. 다른 사람들은 combiantions 를 많이 썼네. set 쓴 것도 여집합 때문에 주요했다.

from itertools import combinations, permutations
combi_lst = []
for i in combinations(team_lst, int(n/2)):
    combi_lst.append(i)

# 능력치 구하기
def get_sum(team): 
    team_sum = 0 
    for i in permutations(team, 2):
        team_sum += matrix[i[0]][i[1]]
        # print(i, matrix[i[0]][i[1]])
    return team_sum
    
min_ = 100
for i in range(int(len(combi_lst)/2)):
    start_team = combi_lst[i]
    link_team = (set(team_lst)-set(start_team))

    start_sum = get_sum(start_team)
    link_sum = get_sum(link_team)
    diff = abs(start_sum-link_sum)
    if diff < min_ :
        min_ = diff
print(min_)

팀 나눌 때는 combinations 쓰고 능력치 더할때는 그 팀을 permutaions 2 해서 더한게 매력 있는 코드. 남들꺼 다봤는데 솔직히 내가 젤 섹시하게 짰다ㅋ_ㅋ 하하하하

1991 이진트리 3종 순회 구현하기

1시간 걸렸나? 2시간 걸렸나? 리스트로 풀려고 했는데 방법을 모르겠어서 진짜 구현함;; 내가 짠 코드 중에서 역대급으로 이상하게 찐따같이 짰다.ㅠ_ㅠ 이진 트리 소스 다시 공부해야지…

import sys
sys.setrecursionlimit(10**8)

class Node(object):
    def __init__(self, val = '', left = None, right = None):
        self.value = val
        self.left = left
        self.right = right
    
    def __str__(self):
        return self.value
    
class Tree(object):
    def __init__(self, root = None):
        self.root = root     

    def preorder(self, visit = None):
        print(visit.value, end='')

        if visit.left != '.':
            self.preorder(visit.left)
        if visit.right != '.':            
            self.preorder(visit.right)
    
    def inorder(self, visit = None):
        if visit.left != '.':
            self.inorder(visit.left)
        
        print(visit.value, end='')
        
        if visit.right != '.':
            self.inorder(visit.right)

    def postorder(self, visit = None):
        if visit.left != '.':
            self.postorder(visit.left)
        if visit.right != '.':
            self.postorder(visit.right)
        
        print(visit.value, end='')

n = int(input())
nodes = []

for _ in range(n):
    parent, left, right = map(str, input().split()) 
    node = Node(parent, left, right)
    nodes.append(node)

    if parent == 'A':
        binaryTree = Tree(node)
        
for parent in nodes:
    for child in nodes:
        if parent.left == child.value:
            parent.left = child
        if parent.right == child.value:
            parent.right = child

binaryTree.preorder(nodes[0])
print()
binaryTree.inorder(nodes[0])
print()
binaryTree.postorder(nodes[0])

오마이갓 이거 리스트로 짜게 되면 자식노드 주소값을 어떻게 저장하나 했는데 딕셔너리로 짜면 되는거였어!!

N = int(input())
graph = {}
for _ in range(N):
    node, *child_nodes = input().split()
    graph[node] = child_nodes

def preorder(node):
    if node == '.': return
    print(node, end='')
    preorder(graph[node][0])
    preorder(graph[node][1])
    return ''

def inorder(node):
    if node == '.': return
    inorder(graph[node][0])
    print(node, end='')
    inorder(graph[node][1])
    return ''

def postorder(node):
    if node == '.': return
    postorder(graph[node][0])
    postorder(graph[node][1])
    print(node, end='')
    return ''

print(preorder('A'))
print(inorder('A'))
print(postorder('A'))

내가 이진트리 구현했다는 걸 위안으로 삼자… 연습연습!

2468번 장마철 안전 영역 최대 개수 구하기

분명 쉬운 섬 개수 구하기 문제였는데… 틀려서 멘붕이었는데 rain의 범위가 문제였다. 노트를 보면 아무 지역도 물에 잠기지 않을 수 있다. 이 말은 곧 비가 안 올수도(rain = 0) 있다는 뜻이었는데 너무 늦게 알아차렸다. 이거 찾느라 너무 오래걸렸다. 채점 중 50퍼에서 틀렸기 때문에 어떤 특정 케이스만 찾아내면 맞을 수 있다는 생각에 답지를 보기 싫어서 계속 고민했고 결국 찾아냈다! 행복해~

import sys
from collections import deque

n = int(input())
region = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = -float('inf')

def bfs(i, j):
    visited[i][j] = True
    q = deque([(i, j)])
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while q:
        x, y = q.popleft()
        
        for dx, dy in d:
            if 0 <= x + dx < n and 0 <= y + dy < n:
                if visited[x+dx][y+dy] == False and region[x+dx][y+dy] > rain:
                    visited[x+dx][y+dy] = True
                    q.append((x+dx, y+dy))


for rain in range(100):
    visited = [[False for _ in range(n)] for _ in range(n)]
    cnt = 0
    
    for i in range(n):
        for j in range(n):
            if visited[i][j] == False and region[i][j] > rain:
                bfs(i, j)
                cnt += 1

    ans = max(ans, cnt)

print(ans)

dfs든 bfs든 다 똑같이 풀었는데. 남들보다 3배 빠른 코드가 있다.

for i in range(N):
    hap += sum(A[i])
    high = max(high,max(A[i]))
mean = hap//(N**2)

cnt = 0
for i in range(mean-1,high):
    visited = [[False]*N for _ in range(N)]
    ans = 0
    for j in range(N):
        for k in range(N):
            if A[j][k] > i and not visited[j][k]:
                BFS(j,k,i)
                ans +=1
    cnt = max(cnt,ans)

print(cnt)

바로 n을 제곱한 수로 전체의 합을 나눠 그 수 전부터 시작해서 탐색하게끔 하였다. 만약 n이 2고 모든 수가 1이라면 4/4 = 1인데 -1을 해줘서 0부터 시작하게함!