문제 설명 두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.) 두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
제한사항 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다. X, Y는 0으로 시작하지 않습니다. X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
(다양한 방법의 풀이가 있으나) 여기서는 dictionary 타입으로 각 문자의수를 저장하고, 유일한 키값 해시를 이용하여 문자의 수를 하나씩 차감함으로써 문제를 해결한다.
각 테스트 데이터에 대한 H 는 다음과 같다.
- 테스트 데이터 1: H = {'2': 1, '3': 1, '4': 1, '5': 1}
-테스트 데이터 2: H = {'2': 1, '0': 2, '3': 1, '4': 1, '5': 1}
- 테스트 데이터 3: H = {'1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '0': 1}
-테스트 데이터 4: H = {'4': 1, '2': 1, '5': 1, '3': 1, '1': 1}
- 테스트 데이터 5: H = {'1': 1, '2': 1, '5': 2}
def solution(X, Y):
answer = ''
H = {}
for i in Y:
if i not in H:
H[i] = Y.count(i)
for i in X:
if i in H and H[i] > 0:
answer += i
H[i] -= 1
answer = "".join(sorted(list(answer),reverse=True))
if len(answer)==0: return "-1"
elif len(answer)==answer.count("0"): return "0"
return answer
이때 시간초과로 인한 실패가 많은데 해결하기 위해서는 더이상 플레이어가 없을때(n==0)는 계산 없이 바로 실패율을 0으로 만든다.
def solution(N, stages):
answer = []
n = len(stages)
for i in range(N):
if n==0:#플레이어가 없을때 계산없이 0으로 추가함
answer.append(0)
else:
c = stages.count(i+1)
answer.append(c/n)
n -= c
answer = sorted(range(1,N+1), key=lambda k: answer[k-1], reverse=True)
return answer
실행결과
테스트 1 〉
통과 (0.01ms, 9.99MB)
테스트 2 〉
통과 (0.26ms, 10.1MB)
테스트 3 〉
통과 (80.91ms, 10.2MB)
테스트 4 〉
통과 (434.18ms, 10.7MB)
테스트 5 〉
통과 (1687.00ms, 15.1MB)
테스트 6 〉
통과 (0.83ms, 10.4MB)
테스트 7 〉
통과 (11.96ms, 10.3MB)
테스트 8 〉
통과 (385.14ms, 10.8MB)
테스트 9 〉
통과 (1593.72ms, 14.9MB)
테스트 10 〉
통과 (149.76ms, 10.9MB)
테스트 11 〉
통과 (444.06ms, 10.8MB)
테스트 12 〉
통과 (450.53ms, 11.1MB)
테스트 13 〉
통과 (514.34ms, 11.3MB)
테스트 14 〉
통과 (0.04ms, 10.1MB)
테스트 15 〉
통과 (13.92ms, 10.7MB)
테스트 16 〉
통과 (5.73ms, 10.4MB)
테스트 17 〉
통과 (17.65ms, 10.5MB)
테스트 18 〉
통과 (6.00ms, 10.3MB)
테스트 19 〉
통과 (1.26ms, 10.2MB)
테스트 20 〉
통과 (20.84ms, 10.4MB)
테스트 21 〉
통과 (18.46ms, 10.8MB)
테스트 22 〉
통과 (1373.85ms, 18.3MB)
테스트 23 〉
통과 (10.45ms, 11.6MB)
테스트 24 〉
통과 (62.01ms, 11.6MB)
테스트 25 〉
통과 (0.01ms, 10.2MB)
테스트 26 〉
통과 (0.01ms, 10.1MB)
테스트 27 〉
통과 (0.01ms, 10.1MB)
테스트 3, 4, 8, 9 등 몇몇 테스트의 경우 큰 시간이 필요하다. 그래서 좀 더 효율적으로 시간을 줄이기 위해서 아래와 같이 count() 함수를 사용하지 않고 미리 계산된 결과만 불러오도록 수정하였다.
def solution(N, stages):
answer = []
n = len(stages)
temp =[0]*N #count 를 미리 계산
for v in stages:
if v<=N:
temp[v-1] += 1
for i in range(N):
if n==0:
answer.append(0)
else:
c = temp[i] # count 값만 호출함
answer.append(c/n)
n -= c
answer = sorted(range(1,N+1), key=lambda k: answer[k-1], reverse=True)#리스트 인덱스 정렬
return answer
실행결과: 아래와 같이 시간이 많이 단축됨을 확인할 수 있다.
테스트 1 〉
통과 (0.01ms, 10.1MB)
테스트 2 〉
통과 (0.18ms, 10.1MB)
테스트 3 〉
통과 (1.14ms, 10.3MB)
테스트 4 〉
통과 (9.74ms, 10.8MB)
테스트 5 〉
통과 (20.49ms, 14.8MB)
테스트 6 〉
통과 (0.12ms, 10.3MB)
테스트 7 〉
통과 (0.84ms, 10.3MB)
테스트 8 〉
통과 (9.54ms, 10.8MB)
테스트 9 〉
통과 (20.53ms, 15MB)
테스트 10 〉
통과 (10.58ms, 10.8MB)
테스트 11 〉
통과 (9.36ms, 10.9MB)
테스트 12 〉
통과 (14.67ms, 11.3MB)
테스트 13 〉
통과 (20.32ms, 11.3MB)
테스트 14 〉
통과 (0.02ms, 10.2MB)
테스트 15 〉
통과 (4.08ms, 10.5MB)
테스트 16 〉
통과 (3.23ms, 10.3MB)
테스트 17 〉
통과 (6.43ms, 10.4MB)
테스트 18 〉
통과 (3.26ms, 10.4MB)
테스트 19 〉
통과 (0.64ms, 10.2MB)
테스트 20 〉
통과 (5.68ms, 10.3MB)
테스트 21 〉
통과 (19.67ms, 10.8MB)
테스트 22 〉
통과 (21.01ms, 18.3MB)
테스트 23 〉
통과 (19.02ms, 11.7MB)
테스트 24 〉
통과 (18.49ms, 11.6MB)
테스트 25 〉
통과 (0.01ms, 10.1MB)
테스트 26 〉
통과 (0.01ms, 10.1MB)
테스트 27 〉
통과 (0.01ms, 10.1MB)
dictionary가 list 보다 데이터 접근이 빠르다고 하여 아래와같이 answer 타입을 list 에서 dictionary 로 변경하여 속도를 확인하였다.
def solution(N, stages):
answer = {}
n = len(stages)
temp =[0]*N
for v in stages:
if v<=N:
temp[v-1] += 1
for i in range(N):
if n==0:
answer[i+1]= 0
else:
c = temp[i]
answer[i+1]= c/n
n -= c
answer = sorted(answer, key=lambda k: answer[k], reverse=True)
return answer
실행결과: 처리 과정은 저장후 정렬이 대부분이며, 저장된 데이터를 찾는 경우가 작다. 그래서 아래와 같이 결과가 비슷하거나 데이터에 따라 약간 차이가 있음을 확인할 수 있다.
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
2. 입출력 예
nums
result
[1,2,3,4]
1
[1,2,7,6,4]
4
입출력 예 설명
입출력 예 #1 [1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2 [1,2,4]를 이용해서 7을 만들 수 있습니다. [1,4,6]을 이용해서 11을 만들 수 있습니다. [2,4,7]을 이용해서 13을 만들 수 있습니다. [4,6,7]을 이용해서 17을 만들 수 있습니다.
3. 문제 풀이
서로 다른 3개를 골라야 되기 때문에 3중 for 문을 쓰던 combinations를 import 시켜서 조합을 만들어내야된다.
작성된 코드 설명은 다음과 같다
(1) 코드는 단순하게 3중 for 문을 써서 조합을 만들다.
(2) 조합중 2,3 으로 나누어 떨어지는 수들을 먼저 제외시킨다.
(3) 나머지 수들 중 1을 제외한 홀수로 나누어 떨어짐을 검사해서 소수를 찾음
def solution(nums):
answer = 0
l = len(nums)
for i in range(l-2):
for j in range(i+1,l-1):
for q in range(j+1,l):
s = nums[i]+nums[j]+nums[q]
if s%2==0 or s%3==0:
continue
else:
prime = True
for r in range(3,int(s**0.5)+1,2):
if s%r==0:
prime = False
break
if prime:
answer += 1
return answer
1,2,3번의 수포자의 답 순서들을 리스트에 저장하고 반복문안에서 문제의 해답들이 수포자가 찍은 답과 맞는 지 차례로 비교한다. 이때 index 는 나머지 연산자(%)를 이용하여 반복적으로 수포자 답을 접근한다.
def solution(answers):
c = [0,0,0]
a0 = [1,2,3,4,5]
a1 = [2,1,2,3,2,4,2,5]
a2 = [3,3,1,1,2,2,4,4,5,5]
for i in range(len(answers)):
if a0[i%len(a0)]==answers[i]:
c[0] += 1
if a1[i%len(a1)]==answers[i]:
c[1] += 1
if a2[i%len(a2)]==answers[i]:
c[2] += 1
m = max(c)
answer = []
for i in range(3):
if c[i] ==m:
answer.append(i+1)
return answer
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 두 번째(1번), 세 번째(2번) 폰켓몬을 선택 두 번째(1번), 네 번째(3번) 폰켓몬을 선택 세 번째(2번), 네 번째(3번) 폰켓몬을 선택 이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.
