출처
: Programmers
문제
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 $k(0 \le k \le 9)$들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). $X$, $Y$의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. $X$, $Y$의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
(생략)
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
'''
x, y 각각을 딱 O(n)으로 읽은 뒤에
그걸 리스트에 해시맵으로 하기
=> 각 숫자별로 개수 카운트하기
'''
def solution(x, y):
x_hash_cnt_list = [0 for _ in range(10)]
y_hash_cnt_list = [0 for _ in range(10)]
x_len = len(x)
y_len = len(y)
# x가 길이 작으면
# x, y 서로 교환(편의상)
if (x_len < y_len):
temp = [x, x_len]
x, x_len = y, y_len
y, y_len = temp[0], temp[1]
# 더 길이 긴 걸 범위로 삼기
iter_range = x_len if x_len >= y_len else y_len
# 0부터 9까지만 할당!!
for i in range(iter_range):
x_temp = int(x[i])
x_hash_cnt_list[x_temp] += 1
if (i < y_len):
y_temp = int(y[i])
y_hash_cnt_list[y_temp] += 1
# 개수가 0이 아닌 것만 찾기
# 그리고 그중 idx 최댓값인 것
not_zeros_x = [[i, [x_hash_cnt_list[i], y_hash_cnt_list[i]]]
if (x_hash_cnt_list[i] != 0
and y_hash_cnt_list[i] != 0)
else [i, -1]
for i in range(9, -1, -1)]
str_merge = ""
for i in range(10):
# 개수가 적은 쪽 선택
try:
min_num = min(not_zeros_x[i][1])
except:
min_num = -1
if min_num == -1:
continue
add_val = not_zeros_x[i][0]
for j in range(min_num):
if (add_val == 0
and str_merge == "0"):
continue
str_merge += str(add_val)
if (str_merge == ""):
answer = "-1"
else:
answer = str_merge
return answer
기본 아이디어는
첫 번째 주석에 적혀있는 대로다.
두 숫자를 $O(N)$만큼 순차로 읽으면서
각 숫자에 대한 카운트를 해시 매핑하고,
두 개의 매핑 리스트에 대하여 비교를 하는 것이다.
근데, 지금 생각해보니
이 코드를 바꾸는 게 나았었다는 생각이 든다.
먼저 짧은 것에서 다 센 것이 무조건
가능한 최댓값이 되므로
길이가 긴 것을 나중에 세는 게 더 낫다.
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(X, Y):
xList = list(X.count(str(x)) for x in range(10))
yList = list(Y.count(str(y)) for y in range(10))
answer = ""
for i in range(9, -1, -1):
answer += str(i) * min(xList[i], yList[i])
if answer == "":
return "-1"
elif answer[0] == "0" and answer[len(answer) - 1] == "0":
return "0"
else:
return answer
(출처: 프로그래머스 스쿨 다른사람 풀이)
교훈
파이썬을 쓴다면
파이썬의 기본 라이브러리를 잘 활용하자…!