๋ฌธ์ ์ค๋ช
๊ฐ๋ฐํ ๋ด์์ ์ด๋ฒคํธ ๊ฐ๋ฐ์ ๋ด๋นํ๊ณ ์๋ "๋ฌด์ง"๋ ์ต๊ทผ ์งํ๋ ์นด์นด์ค์ด๋ชจํฐ์ฝ ์ด๋ฒคํธ์ ๋น์ ์์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ๋น์ฒจ์ ์๋ํ ์๋ชจ์๋ค์ ๋ฐ๊ฒฌํ์์ต๋๋ค. ์ด๋ฐ ์๋ชจ์๋ค์ ๋ฐ๋ก ๋ชจ์ ๋ถ๋ ์ฌ์ฉ์๋ผ๋ ์ด๋ฆ์ผ๋ก ๋ชฉ๋ก์ ๋ง๋ค์ด์ ๋น์ฒจ ์ฒ๋ฆฌ ์ ์ ์ธํ๋๋ก ์ด๋ฒคํธ ๋น์ฒจ์ ๋ด๋น์์ธ "ํ๋ก๋" ์๊ฒ ์ ๋ฌํ๋ ค๊ณ ํฉ๋๋ค. ์ด ๋ ๊ฐ์ธ์ ๋ณด ๋ณดํธ์ ์ํด ์ฌ์ฉ์ ์์ด๋ ์ค ์ผ๋ถ ๋ฌธ์๋ฅผ '*' ๋ฌธ์๋ก ๊ฐ๋ ค์ ์ ๋ฌํ์ต๋๋ค. ๊ฐ๋ฆฌ๊ณ ์ ํ๋ ๋ฌธ์ ํ๋์ '*' ๋ฌธ์ ํ๋๋ฅผ ์ฌ์ฉํ์๊ณ ์์ด๋ ๋น ์ต์ ํ๋ ์ด์์ '*' ๋ฌธ์๋ฅผ ์ฌ์ฉํ์์ต๋๋ค.
"๋ฌด์ง"์ "ํ๋ก๋"๋ ๋ถ๋ ์ฌ์ฉ์ ๋ชฉ๋ก์ ๋งคํ๋ ์๋ชจ์ ์์ด๋๋ฅผ ์ ์ฌ ์์ด๋ ๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ก ํ์์ต๋๋ค.
์๋ฅผ ๋ค์ด, ์ด๋ฒคํธ์ ์๋ชจํ ์ ์ฒด ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ค์๊ณผ ๊ฐ๋ค๋ฉด
์๋ชจ์ ์์ด๋
frodo |
fradi |
crodo |
abc123 |
frodoc |
๋ค์๊ณผ ๊ฐ์ด ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ์ ๋ฌ๋ ๊ฒฝ์ฐ,
๋ถ๋ ์ฌ์ฉ์
fr*d* |
abc1** |
๋ถ๋ ์ฌ์ฉ์์ ๋งคํ๋์ด ๋น์ฒจ์์ ์ ์ธ๋์ด์ผ ์ผ ํ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์์ ์ ์์ต๋๋ค.
์ ์ฌ ์์ด๋
frodo |
abc123 |
์ ์ฌ ์์ด๋
fradi |
abc123 |
์ด๋ฒคํธ ์๋ชจ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด user_id์ ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด banned_id๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋น์ฒจ์์ ์ ์ธ๋์ด์ผ ํ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ช๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ๊ฐ๋ฅํ ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ ์ฌํญ
- user_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 8 ์ดํ์ ๋๋ค.
- user_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ค์ ์๋ก ์ค๋ณต๋์ง ์์ต๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์๋ก๋ง์ผ๋ก ๊ตฌ์ฑ๋์ด ์์ต๋๋ค.
- banned_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ user_id ๋ฐฐ์ด์ ํฌ๊ธฐ ์ดํ์ ๋๋ค.
- banned_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์, ๊ฐ๋ฆฌ๊ธฐ ์ํ ๋ฌธ์ '*' ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ '*' ๋ฌธ์๋ฅผ ํ๋ ์ด์ ํฌํจํ๊ณ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ํ๋๋ ์๋ชจ์ ์์ด๋ ์ค ํ๋์ ํด๋นํ๊ณ ๊ฐ์ ์๋ชจ์ ์์ด๋๊ฐ ์ค๋ณตํด์ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ๋ ์์ต๋๋ค.
- ์ ์ฌ ์์ด๋ ๋ชฉ๋ก๋ค์ ๊ตฌํ์ ๋ ์์ด๋๋ค์ด ๋์ด๋ ์์์ ๊ด๊ณ์์ด ์์ด๋ ๋ชฉ๋ก์ ๋ด์ฉ์ด ๋์ผํ๋ค๋ฉด ๊ฐ์ ๊ฒ์ผ๋ก ์ฒ๋ฆฌํ์ฌ ํ๋๋ก ์ธ๋ฉด ๋ฉ๋๋ค.
์ ์ถ๋ ฅ ์
user_id | banned_id | result |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "abc1**"] | 2 |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["*rodo", "*rodo", "******"] | 2 |
["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "*rodo", "******", "******"] | 3 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์ ์ถ๋ ฅ ์ #1
๋ฌธ์ ์ค๋ช ๊ณผ ๊ฐ์ต๋๋ค.
์ ์ถ๋ ฅ ์ #2
๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์์ต๋๋ค.
์ ์ฌ ์์ด๋
frodo |
crodo |
abc123 |
์ ์ฌ ์์ด๋
frodo |
crodo |
frodoc |
์ ์ถ๋ ฅ ์ #3
๋ค์๊ณผ ๊ฐ์ด ์ธ ๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์์ต๋๋ค.
์ ์ฌ ์์ด๋
frodo |
crodo |
abc123 |
frodoc |
์ ์ฌ ์์ด๋
fradi |
crodo |
abc123 |
frodoc |
์ ์ฌ ์์ด๋
fradi |
frodo |
abc123 |
frodoc |
ํ์ด
- ๋ญ ์ด๋ป๊ฒ ํด์ผ๋๋๊ฑฐ์ผ?
- ์ผ๋จ ์ ๊ท ํํ์์ผ๋ก id๋ฅผ ๊ณจ๋ผ๋ด๊ณ ,
- ์ ์ฌ ๋ชฉ๋ก ์ ๋งํผ id๋ฅผ ๊ณจ๋ผ์ผ ํ๋๋ฐ... ๋ญ์ง ๊น์ด ํ์์ธ๊ฐ?
- ์ง์ง ๊ฒฝ์ฐ์ ์ ์ซ๋ค. ๊ท์ฐฎ์ ใ .ใ
import re
from itertools import permutations
def solution(user_id, banned_id):
answer = 0
banned_id_list = []
for ban_id in banned_id:
b_id = ban_id.replace('*','.')
p = re.compile(b_id)
_tmp = set()
for u_id in user_id:
z = p.findall(u_id)
if len(z) != 0: _tmp.add(z[0])
banned_id_list.append(list(_tmp))
notice = []
Comb = permutations(user_id,len(banned_id_list))
for i, users in enumerate(Comb):
_true = 1
_tmp = []
for j, user in enumerate(users):
if user not in banned_id_list[j]:
_true = 0
break
else:
_tmp.append(user)
if _true == 1:
_tmp.sort()
if _tmp not in notice:
notice.append(_tmp)
return len(notice)
- ์๋ฒฝ ์ฝ์ง์ ํ์ ใ
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.05ms, 10.3MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.37ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.19ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.18ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (65.05ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (11.74ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.65ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.42ms, 10.2MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.37ms, 10.3MB)
ํ
์คํธ 10 ใ ํต๊ณผ (12.32ms, 10.3MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.98ms, 10.3MB)
- ๊ณ ์์ ํ์ด. ๊ฐ๊ฒฐํ๊ณ ๋น ๋ฅธ๋ฐ ํ ์ผ 5๋ฒ๋ง ์์ฒญ ๋๋ฆฌ๋ค.
import re
import itertools
def solution(user_id, banned_id):
answer = 0
banned_id = ["'" + _.replace('*', '\w') + "'" for _ in banned_id]
possible_list = [re.findall(_, str(user_id)) for _ in banned_id]
possible_list = list(itertools.product(*possible_list))
possible_list = [frozenset(p) for p in possible_list if len(set(p)) == len(banned_id)]
possible_list = set(possible_list)
# possible_list = [set(_) for _ in possible_list if len(set(_)) == len(banned_id)]
return len(possible_list)
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.09ms, 10.3MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.19ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.16ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.19ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (9078.26ms, 1.94GB)
ํ
์คํธ 6 ใ ํต๊ณผ (2.45ms, 10.6MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.19ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.23ms, 10.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.31ms, 10.2MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.40ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.25ms, 10.1MB)
- ๋๋ ํ์ด์ฌ re ๊ธฐ๋ฅ์ ๋ง์ด ์จ๋ด์ผํ ๋ฏ...
import re
from itertools import permutations
def solution(user_id, banned_id):
banned_id = [banned.replace("*", ".") for banned in banned_id]
len_banned_id = len(banned_id)
blocked = set()
for users in permutations(user_id, len_banned_id):
all_banned = True
if len(users) == len(set(users)):
for banned, user in zip(banned_id, users):
if not re.fullmatch(banned, user):
all_banned = False
break
if all_banned:
blocked.add(tuple(sorted(users)))
return len(blocked)
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.05ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (1.38ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.41ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.29ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (255.44ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (37.99ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (2.44ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.19ms, 10.2MB)
ํ
์คํธ 9 ใ ํต๊ณผ (4.63ms, 10.2MB)
ํ
์คํธ 10 ใ ํต๊ณผ (47.91ms, 10.3MB)
ํ
์คํธ 11 ใ ํต๊ณผ (3.52ms, 10.3MB)
- ์ด๊ฒ๋ ์ ๊ท์, ์๋๋ ๋ ๋น ๋ฆ.
def solution(user_id, banned_id):
from re import fullmatch
from itertools import permutations
bans = '/'.join(banned_id).replace('*','.')
res = set()
for per in permutations(user_id, len(banned_id)):
if fullmatch(bans, '/'.join(per)):
res.add(''.join(sorted(per)))
return len(res)
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.05ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.58ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.21ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.16ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (57.51ms, 10.1MB)
ํ
์คํธ 6 ใ ํต๊ณผ (14.90ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (1.41ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.66ms, 10.2MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.20ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (28.55ms, 10.1MB)
ํ
์คํธ 11 ใ ํต๊ณผ (1.79ms, 10.1MB)
- ์ ๊ท ํํ์ ์์ฐ๊ณ ๋ง๋ ๊ฑฐ, ํ
์ผ5๋ฒ ๋นผ๊ณ ์์ ๋น ๋ฆ.
- ์ฒ์์ ๋จธ๋ฆฌ์์ผ๋ก ๋ ์ฌ๋ ธ๋ ๋ฐฉ์์ด ์ด๋ฐ ๋ฐฉ์์ด์๋๋ฐ
- ๋ฌธ์์ด ์ ์ฒ๋ฆฌํ๋๊ฑฐ๋ ํผ๋ฎคํ ์ด์ ์ฝ์งํ๋ค๊ฐ ๊ทธ๋ฅ ๋ค ํฌ๊ธฐํ๊ณ ํต์ง๋ก for๋ฌธ ๋๋ ค๋ฒ๋ ธ...
def combi(temp, number, calculate):
global result
if len(temp) == len(calculate):
temp = set(temp)
if temp not in result:
result.append(temp)
return
else:
for j in range(len(calculate[number])):
if calculate[number][j] not in temp:
temp.append(calculate[number][j])
combi(temp, number+1, calculate)
temp.pop()
result = []
def solution(user_id, banned_id):
global result
calculate = []
for ban in banned_id:
possible=[]
for user in user_id:
if len(ban) != len(user):
continue
else:
count = 0
for i in range(len(ban)):
if user[i] == ban[i]:
count+=1
if count == len(ban)-ban.count('*'):
possible.append(user)
calculate.append(possible)
combi([], 0, calculate)
return len(result)
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.04ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (115.12ms, 10.4MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.96ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 8 ใ ํต๊ณผ (0.04ms, 10.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (0.05ms, 10.2MB)
ํ
์คํธ 10 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (0.05ms, 10.2MB)