๐ญ ๋ฌธ์ ์ดํด
์ ๋ชฉ์ด....ใ
์ํผ ์ ํ์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ํ๋ฉด ์ด๋ถํ์์ด์ง๋ง,
ํ์ด์ฌ์ ์ฅ์ ์ ์ ์ด๋ฆฌ๋ฉด ์ด๋ถํ์๋ณด๋ค ์คํ์๋๋ ๋ ๋น ๋ฅด๊ณ ๊ฐ๋จํ๊ฒ ํ์ด๋ผ ์ ์๋ค.
ํ์ด ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ๋ค.
1. ์ด๋ถํ์
2. Set ์๋ฃ๊ตฌ์กฐ์ in ์ฐ์ฐ์
3. Set์ ๊ต์งํฉ์ ๊ตฌํ ์ ์๋ & ์ฐ์ฐ์
4. Set๊ณผ intersection ๋ฉ์๋๋ฅผ ์ด์ฉํ ๊ต์งํฉ ์ฐ์ฐ
์คํ์๋๋ 4 > 3 >= 2 > 1 ์์ผ๋ก ๋น ๋ฅด๋ค.
๊ตฌํ ์ธ์ด: Python
1. ์ด๋ถํ์
import sys
r = sys.stdin.readline
def binary_search(d_list: list, b_list: list) -> list:
result = []
d_list.sort()
for b in b_list:
left = 0
right = len(d_list) - 1
while left <= right:
mid = (left + right) // 2
if d_list[mid] < b:
left = mid + 1
elif d_list[mid] > b:
right = mid - 1
else:
result.append(b) # ๋ฃ๋ ๋ณด๋ ๋ชปํ ๋ช
๋จ ์ฐพ์
break # ์ฌ๊ธฐ์ ๊ผญ ์ข
๋ฃ๋ฅผ ํด์ฃผ์ด์ผ ํ๋ค!
return sorted(result)
d_num, b_num = map(int, r().split())
d_list = list(r().rstrip() for _ in range(d_num)) # ๋ฃ๋ ๋ชปํ ๋ช
๋จ
b_list = list(r().rstrip() for _ in range(b_num)) # ๋ณด๋ ๋ชปํ ๋ช
๋จ
answer = binary_search(d_list, b_list) # ์ฌ์ ์์ผ๋ก ์ ๋ ฌ๋ ๋ฃ๋ ๋ณด๋ ๋ชปํ ๋ช
๋จ
print(len(answer))
for name in answer:
print(name)
2. Set ์๋ฃ๊ตฌ์กฐ์ in ์ฐ์ฐ์
import sys
r = sys.stdin.readline
d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num)) # ๋ฃ๋ ๋ชปํ ๋ช
๋จ
b_list = list(r().rstrip() for _ in range(b_num)) # ๋ณด๋ ๋ชปํ ๋ช
๋จ
answer = sorted([name for name in b_list if name in d_list])
print(len(answer))
for name in answer:
print(name)
Set์ Hash function์ผ๋ก ๊ตฌํ์ด ๋์ด์์ด์ Dict๋ฅผ ์ฌ์ฉํ ๋์ฒ๋ผ in ์ฐ์ฐ์๋ฅผ O(1)์ ์๊ฐ์ผ๋ก ์ฌ์ฉํ ์ ์์ด ๋งค์ฐ ๋น ๋ฅด๋ค!
3. Set์ ๊ต์งํฉ์ ๊ตฌํ ์ ์๋ & ์ฐ์ฐ์
import sys
r = sys.stdin.readline
d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num)) # ๋ฃ๋ ๋ชปํ ๋ช
๋จ
b_list = set(r().rstrip() for _ in range(b_num)) # ๋ณด๋ ๋ชปํ ๋ช
๋จ
answer = sorted(d_list & b_list)
print(len(answer))
for name in answer:
print(name)
4. Set๊ณผ intersection ๋ฉ์๋๋ฅผ ์ด์ฉํ ๊ต์งํฉ ์ฐ์ฐ
import sys
r = sys.stdin.readline
d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num)) # ๋ฃ๋ ๋ชปํ ๋ช
๋จ
b_list = set(r().rstrip() for _ in range(b_num)) # ๋ณด๋ ๋ชปํ ๋ช
๋จ
answer = sorted(d_list.intersection(b_list)) # ๋ด์ฅ ๋ฉ์๋๊ฐ ๋ ๋น ๋ฆ!!
print(len(answer))
for name in answer:
print(name)
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 1535 ์๋ / ๋์ ๊ณํ๋ฒ(Dynamic-Programming) (0) | 2021.03.11 |
---|---|
[BOJ] ๋ฐฑ์ค 2512 ์์ฐ / ์ด๋ถํ์ (0) | 2021.02.11 |
[BOJ] ๋ฐฑ์ค 10816 ์ซ์ ์นด๋ 2 / ์ด๋ถํ์ (0) | 2021.02.09 |
[BOJ] ๋ฐฑ์ค 1654 ๋์ ์๋ฅด๊ธฐ / ์ด๋ถํ์ (0) | 2021.02.09 |
[BOJ] ๋ฐฑ์ค 10815 ์ซ์ ์นด๋ / ์ด๋ถํ์ (0) | 2021.02.09 |