๋ฌธ์ ์ค๋ช
๋ ์คํ ๋์ ์ด์ํ๋ ์ค์นดํผ๋ ์ฝ๋ก๋19๋ก ์ธํ ๋ถ๊ฒฝ๊ธฐ๋ฅผ ๊ทน๋ณตํ๊ณ ์ ๋ฉ๋ด๋ฅผ ์๋ก ๊ตฌ์ฑํ๋ ค๊ณ ๊ณ ๋ฏผํ๊ณ ์์ต๋๋ค.
๊ธฐ์กด์๋ ๋จํ์ผ๋ก๋ง ์ ๊ณตํ๋ ๋ฉ๋ด๋ฅผ ์กฐํฉํด์ ์ฝ์ค์๋ฆฌ ํํ๋ก ์ฌ๊ตฌ์ฑํด์ ์๋ก์ด ๋ฉ๋ด๋ฅผ ์ ๊ณตํ๊ธฐ๋ก ๊ฒฐ์ ํ์ต๋๋ค. ์ด๋ค ๋จํ๋ฉ๋ด๋ค์ ์กฐํฉํด์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๋ฉด ์ข์ ์ง ๊ณ ๋ฏผํ๋ "์ค์นดํผ"๋ ์ด์ ์ ๊ฐ ์๋๋ค์ด ์ฃผ๋ฌธํ ๋ ๊ฐ์ฅ ๋ง์ด ํจ๊ป ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๊ธฐ๋ก ํ์ต๋๋ค.
๋จ, ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ ์ต์ 2๊ฐ์ง ์ด์์ ๋จํ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๋ ค๊ณ ํฉ๋๋ค. ๋ํ, ์ต์ 2๋ช
์ด์์ ์๋์ผ๋ก๋ถํฐ ์ฃผ๋ฌธ๋ ๋จํ๋ฉ๋ด ์กฐํฉ์ ๋ํด์๋ง ์ฝ์ค์๋ฆฌ ๋ฉ๋ด ํ๋ณด์ ํฌํจํ๊ธฐ๋ก ํ์ต๋๋ค.
์๋ฅผ ๋ค์ด, ์๋ 6๋ช
์ด ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค์ ์กฐํฉ์ด ๋ค์๊ณผ ๊ฐ๋ค๋ฉด,
(๊ฐ ์๋์ ๋จํ๋ฉ๋ด๋ฅผ 2๊ฐ ์ด์ ์ฃผ๋ฌธํด์ผ ํ๋ฉฐ, ๊ฐ ๋จํ๋ฉ๋ด๋ A ~ Z์ ์ํ๋ฒณ ๋๋ฌธ์๋ก ํ๊ธฐํฉ๋๋ค.)
์๋ ๋ฒํธ | ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด ์กฐํฉ |
1๋ฒ ์๋ | A, B, C, F, G |
2๋ฒ ์๋ | A, C |
3๋ฒ ์๋ | C, D, E |
4๋ฒ ์๋ | A, C, D, E |
5๋ฒ ์๋ | B, C, F, G |
6๋ฒ ์๋ | A, C, D, E, H |
๊ฐ์ฅ ๋ง์ด ํจ๊ป ์ฃผ๋ฌธ๋ ๋จํ๋ฉ๋ด ์กฐํฉ์ ๋ฐ๋ผ "์ค์นดํผ"๊ฐ ๋ง๋ค๊ฒ ๋ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด ๊ตฌ์ฑ ํ๋ณด๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ฝ์ค ์ข ๋ฅ | ๋ฉ๋ด ๊ตฌ์ฑ | ์ค๋ช |
์๋ฆฌ 2๊ฐ ์ฝ์ค | A, C | 1๋ฒ, 2๋ฒ, 4๋ฒ, 6๋ฒ ์๋์ผ๋ก๋ถํฐ ์ด 4๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค. |
์๋ฆฌ 3๊ฐ ์ฝ์ค | C, D, E | 3๋ฒ, 4๋ฒ, 6๋ฒ ์๋์ผ๋ก๋ถํฐ ์ด 3๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค. |
์๋ฆฌ 4๊ฐ ์ฝ์ค | B, C, F, G | 1๋ฒ, 5๋ฒ ์๋์ผ๋ก๋ถํฐ ์ด 2๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค. |
์๋ฆฌ 4๊ฐ ์ฝ์ค | A, C, D, E | 4๋ฒ, 6๋ฒ ์๋์ผ๋ก๋ถํฐ ์ด 2๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค. |
์ ํ ์ฌํญ
๊ฐ ์๋๋ค์ด ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค์ด ๋ฌธ์์ด ํ์์ผ๋ก ๋ด๊ธด ๋ฐฐ์ด orders, "์ค์นดํผ"๊ฐ ์ถ๊ฐํ๊ณ ์ถ์ดํ๋ ์ฝ์ค์๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๋จํ๋ฉ๋ด๋ค์ ๊ฐฏ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด course๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, "์ค์นดํผ"๊ฐ ์๋ก ์ถ๊ฐํ๊ฒ ๋ ์ฝ์ค์๋ฆฌ์ ๋ฉ๋ด ๊ตฌ์ฑ์ ๋ฌธ์์ด ํํ๋ก ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
- orders ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 2 ์ด์ 20 ์ดํ์ ๋๋ค.
- orders ๋ฐฐ์ด์ ๊ฐ ์์๋ ํฌ๊ธฐ๊ฐ 2 ์ด์ 10 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ๊ฐ ๋ฌธ์์ด์ ์ํ๋ฒณ ๋๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๊ฐ ๋ฌธ์์ด์๋ ๊ฐ์ ์ํ๋ฒณ์ด ์ค๋ณตํด์ ๋ค์ด์์ง ์์ต๋๋ค.
- course ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 10 ์ดํ์
๋๋ค.
- course ๋ฐฐ์ด์ ๊ฐ ์์๋ 2 ์ด์ 10 ์ดํ์ธ ์์ฐ์๊ฐ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์์ต๋๋ค.
- course ๋ฐฐ์ด์๋ ๊ฐ์ ๊ฐ์ด ์ค๋ณตํด์ ๋ค์ด์์ง ์์ต๋๋ค.
- ์ ๋ต์ ๊ฐ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด์ ๊ตฌ์ฑ์ ๋ฌธ์์ด ํ์์ผ๋ก ๋ฐฐ์ด์ ๋ด์ ์ฌ์ ์์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํด์ return ํด์ฃผ์ธ์.
- ๋ฐฐ์ด์ ๊ฐ ์์์ ์ ์ฅ๋ ๋ฌธ์์ด ๋ํ ์ํ๋ฒณ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด์ผ ํฉ๋๋ค.
- ๋ง์ฝ ๊ฐ์ฅ ๋ง์ด ํจ๊ป ์ฃผ๋ฌธ๋ ๋ฉ๋ด ๊ตฌ์ฑ์ด ์ฌ๋ฌ ๊ฐ๋ผ๋ฉด, ๋ชจ๋ ๋ฐฐ์ด์ ๋ด์ return ํ๋ฉด ๋ฉ๋๋ค.
- orders์ course ๋งค๊ฐ๋ณ์๋ return ํ๋ ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ 1 ์ด์์ด ๋๋๋ก ์ฃผ์ด์ง๋๋ค.
์ ์ถ๋ ฅ ์
orders | course | result |
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] | [2,3,4] | ["AC", "ACDE", "BCFG", "CDE"] |
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] | [2,3,5] | ["ACD", "AD", "ADE", "CD", "XYZ"] |
["XYZ", "XWY", "WXA"] | [2,3,4] | ["WX", "XY"] |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์ ์ ์์์ ๊ฐ์ต๋๋ค.
์
์ถ๋ ฅ ์ #2
AD๊ฐ ์ธ ๋ฒ, CD๊ฐ ์ธ ๋ฒ, ACD๊ฐ ๋ ๋ฒ, ADE๊ฐ ๋ ๋ฒ, XYZ ๊ฐ ๋ ๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค.
์๋ฆฌ 5๊ฐ๋ฅผ ์ฃผ๋ฌธํ ์๋์ด 1๋ช
์์ง๋ง, ์ต์ 2๋ช
์ด์์ ์๋์๊ฒ์ ์ฃผ๋ฌธ๋ ๊ตฌ์ฑ๋ง ์ฝ์ค์๋ฆฌ ํ๋ณด์ ๋ค์ด๊ฐ๋ฏ๋ก, ์๋ฆฌ 5๊ฐ๋ก ๊ตฌ์ฑ๋ ์ฝ์ค์๋ฆฌ๋ ์๋ก ์ถ๊ฐํ์ง ์์ต๋๋ค.
์
์ถ๋ ฅ ์ #3
WX๊ฐ ๋ ๋ฒ, XY๊ฐ ๋ ๋ฒ ์ฃผ๋ฌธ๋์ต๋๋ค.
3๋ช
์ ์๋ ๋ชจ๋ ๋จํ๋ฉ๋ด๋ฅผ 3๊ฐ์ฉ ์ฃผ๋ฌธํ์ง๋ง, ์ต์ 2๋ช
์ด์์ ์๋์๊ฒ์ ์ฃผ๋ฌธ๋ ๊ตฌ์ฑ๋ง ์ฝ์ค์๋ฆฌ ํ๋ณด์ ๋ค์ด๊ฐ๋ฏ๋ก, ์๋ฆฌ 3๊ฐ๋ก ๊ตฌ์ฑ๋ ์ฝ์ค์๋ฆฌ๋ ์๋ก ์ถ๊ฐํ์ง ์์ต๋๋ค.
๋, ๋จํ๋ฉ๋ด๋ฅผ 4๊ฐ ์ด์ ์ฃผ๋ฌธํ ์๋์ ์์ผ๋ฏ๋ก, ์๋ฆฌ 4๊ฐ๋ก ๊ตฌ์ฑ๋ ์ฝ์ค์๋ฆฌ ๋ํ ์๋ก ์ถ๊ฐํ์ง ์์ต๋๋ค.
ํ์ด
- ์ด๊ฒ๋ ์กฐํฉ ๋ฌธ์ ๋ค. ๊ทธ๋ฆฌ๊ณ ์นด์ดํฐ.
import collections
import itertools
def solution(orders, course):
answer = []
people = len(orders)
for c in course: # ์ ์ฒ๋ฆฌ
setmenu = collections.Counter()
for order in orders:
order = list(order)
order.sort()
menu_comb = list(itertools.combinations(order,c))
for menu in menu_comb:
menu = ''.join(menu)
if menu in setmenu:
setmenu[menu] += 1
else:
setmenu[menu] = 1
sm = setmenu.most_common() # ์ ๋ ฌ
cnt_menu = -1
for menu in sm: # print(menu)
if cnt_menu == -1 and menu[1] > 1: #print("์ธํ
",menu)
cnt_menu = menu[1]
answer.append(menu[0])
elif cnt_menu == menu[1]: #print("์ถ๊ฐ",menu)
answer.append(menu[0])
else:
cnt_menu = -1 #print("๋ฆฌ์
",menu)
break
answer.sort()
return answer
- ๊ตฌํ ๋ฌธ์ ์ ์ข ๋ ๊ฐ๊น์ด ๋ฏ ํ๋ค.
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.09ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.10ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.17ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.11ms, 10.3MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.47ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.49ms, 10.3MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.41ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.58ms, 10.3MB)
ํ
์คํธ 10 ใ ํต๊ณผ (1.93ms, 10.6MB)
ํ
์คํธ 11 ใ ํต๊ณผ (1.06ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (1.25ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (3.15ms, 10.7MB)
ํ
์คํธ 14 ใ ํต๊ณผ (1.23ms, 10.4MB)
ํ
์คํธ 15 ใ ํต๊ณผ (1.72ms, 10.6MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.44ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.23ms, 10.3MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.20ms, 10.2MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.04ms, 10.1MB)
ํ
์คํธ 20 ใ ํต๊ณผ (0.32ms, 10.2MB)
- ์ ๋จธ์ง? ์ฝ๋ ๊ธธ์ด ๋๋ฐ ใ
ใ
ใ
- ์ด๋ ๊ฒ ์ฝ๊ฒ ํ๋ฆฌ๋ ๊ฑฐ์์ด?
- ์ด๊ฒ์ด ํ์ด์ฌ์ธ๊ฐ... ใ
ก.ใ
ก;
- ๋ ์ ์ C์ธ์ด ์ธ ๋ ์ฒ๋ผ ์ฝ๋ฉํ๋ ๋๋์ด๋ค.
- ์ด๊ฒ์ด ํ์ด์ฌ์ธ๊ฐ... ใ
ก.ใ
ก;
- ์ด๋ ๊ฒ ์ฝ๊ฒ ํ๋ฆฌ๋ ๊ฑฐ์์ด?
import collections
import itertools
def solution(orders, course):
result = []
for course_size in course:
order_combinations = []
for order in orders:
order_combinations += itertools.combinations(sorted(order), course_size)
most_ordered = collections.Counter(order_combinations).most_common()
result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]
return [ ''.join(v) for v in sorted(result) ]
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.14ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.12ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.14ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.15ms, 10.2MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.16ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.30ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.33ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.81ms, 10.5MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.62ms, 10.6MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.58ms, 10.7MB)
ํ
์คํธ 11 ใ ํต๊ณผ (1.28ms, 10.4MB)
ํ
์คํธ 12 ใ ํต๊ณผ (1.62ms, 10.5MB)
ํ
์คํธ 13 ใ ํต๊ณผ (2.18ms, 10.4MB)
ํ
์คํธ 14 ใ ํต๊ณผ (1.62ms, 10.7MB)
ํ
์คํธ 15 ใ ํต๊ณผ (2.36ms, 10.7MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.62ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.39ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.18ms, 10.2MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.08ms, 10.1MB)
ํ
์คํธ 20 ใ ํต๊ณผ (0.60ms, 10.4MB)