완전탐색 part에서는 크게 까다로웠던 문제는 없었던 것 같다. 이번 part에서는 다른 사람의 풀이 중 인상 깊었던 풀이가 있던 문제에 대해서 리뷰 하겠다.
[문제 설명]
코딩테스트 연습 - 소수 찾기
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이
programmers.co.kr
먼저 이 문제가 요구하는 게 무엇이고, 어떻게 접근할 지 생각해보자. 해당 문제는 '주어진 숫자들을 조합하여 만들 수 있는 소수의 개수를 반환' 하는 것을 요구하고 있다. 그렇다면 이를 어떻게 풀어나가야할까? 해당 문제는 최적의 방법으로 소수의 개수를 구할 수 없다. 즉, 주어진 숫자들을 통해 만들 수 있는 모든 경우의 수를 구하고 이 들 중 소수의 개수를 세는 방법으로 접근해야 한다. 그럼 이제 코드를 확인하자.
[문제 풀이]
from itertools import permutations # 순열을 구해주는 method
# 소수 확인
def check(num):
for i in range(2,num): # 2부터 자기 자신 직전의 수까지
if num % i == 0: # 나누어서 나누어 떨어진다면
return False # 소수가 아님
else: # 나누어 떨어지지 않는다면
return True # 소수
# 메인함수
def solution(numbers):
numbers = list(numbers) #받아온 문자열을 문자로 분리하여 list로 변환
per = [] # 만들 수 있는 모든 숫자의 조합 생성 (중복을 포함하여 순서 고려) -> 순열
for i in range(1,len(numbers)+1): # 모든 자릿수를 고려
per.extend(list(permutations(numbers, i))) # 해당 자릿수에 대한 순열 반환
result_nums = set() # 중복을 피하기 위해 집합생성
# 순열의 결과를 int형으로 변환하기 위한 반복문
for i in range(len(per)):
temp = ''
for j in range(len(per[i])):
temp += per[i][j]
result_nums.add(int(temp))
# 소수 개수 확인
cnt = 0
for num in result_nums:
if num >1 and check(num): #2부터 체크, 소수라면
cnt+=1 # 개수 증가
return cnt
여기서 permutation이라는 method를 모른 상태에서 구현하게 된다면 좀 까다로운 문제일 수도 있다. 항상 생각하는 것이지만 이렇게 파이썬에서 제공되는 툴과 method들은 알면 알수록 코딩테스트에 이득인 것 같다. 하지만 항상 이득인 것은 아니다. 이렇게 모든 경우의 수를 구해야 하는 경우 보통 시간복잡도까지 고려하는 문제들은 아니지만, 시간 복잡도를 고려하는 문제라면 permuation은 그야 말로 최악의 시간복잡도를 제공할 수도 있다.
[다른 사람의 풀이]
from itertools import permutations
def solution(n):
a = set()
for i in range(len(n)):
# 입력받은 문자열을 한 문자씩 리스트로 변형, map과 ''.join을 사용하여 permutations의 결과의 문자들을 다시 문자열로 병합 후 int형으로 다시 변환, 그 후 집합a에 or 연산을 통해 더해줌
a |= set(map(int, map("".join, permutations(list(n), i + 1))))
a -= set(range(0, 2)) # 0,1 제거 (소수 판단 시 제외해주기 위함)
for i in range(2, int(max(a) ** 0.5) + 1): # 가장 큰수의 제곱근까지의 범위로 설정함으로써 시간복잡도 Down
a -= set(range(i * 2, max(a) + 1, i)) # 소수가 아닌 수들을 기존 집합a에서 제거해줌
return len(a) # 결과
해당 문제를 리뷰하는 것은 이 코드를 소개하기 위함이였다. 물론 좀 더 효율적인 코딩이라기 보다는 숏코딩에 가깝다고 할 수 있지만, 그럼에도 매력적인 접근방식과 코드여서 소개한다. 해당 코드에서 중요하게 볼 부분은 먼저, 모든 반복되는 객체를 집합으로 표현하여 연산해 나갔다는 점이다. 또, '입력받은 문자열을 한 문자씩 리스트로 변형' 하는 부분이다. map과 join과 같은 내장함수를 적절히 사용하여 풀어나갔다. 또한, '소수체크' 부분이다. 해당 부분은 소수의 정의를 말그대로 잘 표현한 부분이다. 만약 시간복잡도까지 고려하는 문제였다면 해당 코드는 더욱 중요했을 것이다.
[마무리]
코딩테스트를 준비하면 준비할 수록 느끼는 것은 '푼다고 끝나는게 아닌, 풀고 나서 내가 푼 방법과 다른 사람의 풀이를 참고할 때 비로소 공부가 시작된다' 라는 것이다. 1일1코딩을 목표로 삼으면서 1코딩이 완료된다고 바로 끝내는 것이 아닌 내가 풀었던 방법을 리뷰하고, 다른 사람의 더 나은 코드도 리뷰하며 하루하루 공부를 해 나가야겠다고 생각한다.
'코딩 테스트 > 코테 문제 리뷰' 카테고리의 다른 글
프로그래머스 코딩테스트 고득점 Kit : 정렬 - (프로그래머스 42746번 : 가장 큰 수) (0) | 2021.09.01 |
---|---|
프로그래머스 코딩테스트 고득점 Kit : 힙 part - (프로그래머스 42627번 : 디스크 컨트롤러) (0) | 2021.08.24 |
프로그래머스 코딩테스트 고득점 Kit : 스택/큐 (0) | 2021.08.23 |
프로그래머스 코딩테스트 고득점 Kit : 해시 (0) | 2021.08.19 |
삼성 SW 역량 테스트 : 치킨 배달 (백준 15686번) (0) | 2021.08.16 |