99클럽 코테 스터디
99클럽 오픈카톡방에서 한줄코딩 얘기가 나와서 나도 도전해보았다. 별로 해본 적 없는 방식이라 흥미로웠기 때문이다.
비기너, 미들러 두 문제는 한줄코딩에 성공하긴 했으나, 내 스타일은 아닌 것 같다. 일단 너무 힘들다... TIL을 자세히 쓸 기력이 안 날 만큼. 그래도 최대한 열심히 적어보았다.
내일부턴 그냥 평범하게 실행시간 효율성을 추구하는 코드로 다시 풀어야겠다.
비기너 문제 모의고사 : https://school.programmers.co.kr/learn/courses/30/lessons/42840
미들러 문제 소수 찾기 : https://school.programmers.co.kr/learn/courses/30/lessons/42839
챌린저 문제 전력망을 둘로 나누기 : https://school.programmers.co.kr/learn/courses/30/lessons/86971
출처 : 프로그래머스
비기너 문제 : 모의고사
풀이 접근
수포자 1은 길이 5, 수포자 2는 길이 8, 수포자 3은 길이 10의 찍기 패턴을 반복한다. 따라서, 문제 번호를 5,8,10으로 각각 나눈 나머지에 따라서 맞았는지 틀렸는지 확인 가능하다.
코드(Python3, 통과, 최대 10.58ms, 10.5MB, 한줄코딩)
len([0 for i in range(len(answers)) if i%5+1 == answers[i]]),
len([0 for i in range(len(answers)) if (2, 1, 2, 3, 2, 4, 2, 5)[i%8] == answers[i]]),
len([0 for i in range(len(answers)) if (3, 3, 1, 1, 2, 2, 4, 4, 5, 5)[i%10] == answers[i]])
는 각각 수포자 1,2,3이 맞춘 문제의 수이다. 원래 얘를 만들어서 리스트나 튜플로 두고 참조하면 그만인데, 한줄로 쓰려다 보니 이걸 반복해서 쓰지 않는 방법이 빠르게 떠오르지 않아서 그냥 두 번 써버렸다.
개인적으로 이런 비효율은 취향이 아니라서, 한줄코딩에 숙달돼서 세련된 방식을 쓸 줄 알게 되기 전까진 마음에 들지 않을 것이다...
def solution(answers):
return [index + 1 for index, val in enumerate([len([0 for i in range(len(answers)) if i%5+1 == answers[i]]),len([0 for i in range(len(answers)) if (2, 1, 2, 3, 2, 4, 2, 5)[i%8] == answers[i]]),len([0 for i in range(len(answers)) if (3, 3, 1, 1, 2, 2, 4, 4, 5, 5)[i%10] == answers[i]])]) if val == max([len([0 for i in range(len(answers)) if i%5+1 == answers[i]]),len([0 for i in range(len(answers)) if (2, 1, 2, 3, 2, 4, 2, 5)[i%8] == answers[i]]),len([0 for i in range(len(answers)) if (3, 3, 1, 1, 2, 2, 4, 4, 5, 5)[i%10] == answers[i]])])]미들러 문제 : 소수 찾기
풀이 접근
7개의 숫자 카드로 만들 수 있는 수의 개수는 최대 7! * (1/0! + 1/1! + 1/2! + 1/3! + 1/4! + 1/5! + 1/6!)이다. 괄호 안에 있는 7가지는 각각 카드 7장,6장,5장,...,1장을 써서 만드는 경우이다. 그리고 이는 대충 5000e(자연상수 e이다)로 15000가지 정도가 나온다. 만드는 방식은, 정직하게 재귀 등으로 만들거나, permutation이 가능한 라이브러리를 쓰면 된다. (나는 한줄코딩을 위해서 라이브러리를 썼다. 라이브러리를 안 쓰고는 한줄코딩으로 숫자의 조합을 다 만드는 방법을 찾아내지 못해서)
그리고 7자리 수는 1천만 미만(9999999 이하)이므로, 소수인지 판별하기 위해서는 sqrt(1천만), 즉 3162 미만의 소수로만 나누어 보면 판별할 수 있다. 몇 갠진 몰라도 천개쯤 될까? 그러므로 시간복잡도는 최악의 경우에도 1500만 정도 된다는 것을 알 수 있다(하지만 실제로 합성수들은 금방 걸러지기 때문에 이렇게까지 되진 않는다).
따라서 3162 미만의 소수들을 만들어 놓고(이 때도 3162 미만의 수들을 sqrt(3162) 미만의 수들로만 나누어 봄으로 알 수 있어서 3162의 제곱인 천만번 연산할 필요까진 없으므로 시간이 절약된다), 최대 15000가지의 가능한 수들을 3162 미만의 소수들로 나누어 보면서 소수인지 판별해서 그 개수를 return하면 된다.
다만, 나는 한줄코딩을 위해서 3162 미만의 소수 리스트를 만들지 않고(리스트 컴프리헨션을 이중으로 쓸 때 소수 리스트를 만들면 for문이 한번 돌때마다 반복해서 만들어서 지옥의 시간복잡도가 나오는데, 이를 해결할 방법을 찾지 못함), 그냥 3162까지 모든 자연수로 나누어보았다. 그리고 이래도 시간복잡도 최악 5천만이고, 실제로 합성수들이 빠르게 걸러져서 그 정도까지 오래걸리지 않는다.
그냥 풀면 슥슥슥슥 푸는건데, 한줄코딩하려니까 챌린저보다 훨씬 오래걸렸다. 그리고 굉장히 어렵다.
코드(Python3, 통과, 최대 79.93ms, 10.5MB, 한줄코딩(라이브러리 제외))
{int(''.join(p)[:k+1]) for p in permutations(numbers) for k in range(len(numbers))}는 numbers에 있는 숫자 카드들로 만들 수 있는 모든 자연수들의 집합이다. 집합(set)이므로 011과 11을 서로 다른 수로 취급하지 않고 중복은 제거된다.
if all(number%n for n in range(2,min(3162,number)))는 만든 숫자 카드가 2 이상 3162(또는 그 숫자 본인) 미만의 모든 자연수로 나누어떨어지지 않는 경우(= 만든 숫자 카드가 소수인 경우)이다.
0과 1은 소수가 아닌데 위의 퍼뮤테이션 생성 및 소수 판별 과정상 들어갈 수도 있어서 집합에서 제외해 준다. 집합에서 discard 메서드로 삭제하면 O(1)인 것을 차집합 연산으로 삭제하면 효율이 떨어지는데, 한줄코딩을 위해 어쩔 수 없이 썼다. 역시 썩 맘에 드는 방식은 아니다.
from itertools import permutations
def solution(numbers):
return len({number for number in {int(''.join(p)[:k+1]) for p in permutations(numbers) for k in range(len(numbers))} if all(number%n for n in range(2,min(3162,number)))} - {0,1})챌린저 문제 : 전력망을 둘로 나누기
풀이 접근
이 문제는 한줄코딩이 아니라 그냥 평범하게 풀었다(챌린저-미들러-비기너 순으로 푸는데, 챌린저 풀 때는 한줄코딩 얘기를 보기 전이었다). 그리고 아마 풀기 전에 봤어도 이 문제는 한줄코딩으로는 포기했을 것이다.
이 문제는 dfs(에 의한 트리 순회)가 반드시 필요하고, 더 효율적으로 풀려면 백트래킹도 필요하다.
모든 간선을 한 번씩 잘라 보면서 잘라진 한 쪽 트리를 dfs 순회해서 개수를 세어보는 게 dfs+브루트포스 방식이고(송전탑이 100개뿐이므로 이 방법으로도 쉽게 풀릴 것이다), 백트래킹을 이용하면 재귀함수 실행 한번으로 답을 바로 구할 수 있다. 송전탑이 10만개쯤 된다면, 전자의 방식(O(n^2))으론 풀지 못하므로, 후자(O(n))으로 풀어야 한다.
코드(Python3, 통과, 최대 0.15ms, 10.3MB)
아래 connected를 정의한 방식은 내가 자주 쓰는 방식인데, 그래프의 정보를 connected[i]에 j가 들어있으면 i와 j가 연결되어있음을 의미한다.
visited 리스트를 만들어 방문처리를 해준다.
dfs는 임의의 한 점(여기서는 1번 송신탑)에서 출발하고, dfs 방식으로 순회하는데, 매 간선을 이동할 때마다 '해당 간선을 지나가면서 잘랐을 때 도착한 지점을 포함한 트리의 크기', 그리고 '방금 지나온 간선을 포함해서 해당 트리 내부에 있는 모든 간선 중 하나를 잘랐을 때 잘린 두 트리의 크기의 차이의 최소값(문제에서 구하는 값)' 두 가지를 return한다. 이렇게 안 하려면 그냥 smallest_diff(문제에서 구하는 값)를 dfs 함수 밖에 선언하고 global 선언해서 수정하면 된다.
def solution(n, wires):
connected = [set() for _ in range(n + 1)]
for v1, v2 in wires:
connected[v1].add(v2)
connected[v2].add(v1)
visited = [False] * (n + 1)
def dfs(v):
visited[v] = True
size = 1
smallest_diff = n
for c in connected[v]:
if not visited[c]:
c_size, c_diff = dfs(c)
smallest_diff = min(smallest_diff, c_diff, abs(n - 2 * c_size))
size += c_size
return size, smallest_diff
answer = dfs(1)[1]
return answer