self.winter.(07). 집합과 맵 _백준[14425, 10815, 10816, 11478]

🧐 백준 14425

🤔 Algorithm 과정 
1. s와 string 리스트에 입력에 해당하는 각각의 문자열을 넣음
2. for문으로 string을 돌면서 string에 있는 문자열과 일치하는 단어가 s에 있다면?
3. cnt값 1 증가 (= 일치하는 문자열이 있다는 것)
4. 최종적으로 cnt값 출력

🤫  solution_14425

N, M = map(int, input().split())
s = [input() for _ in range(N)]
string = [input() for _ in range(M)]

cnt = 0
for i in string:
    if i in s:
        cnt += 1
print(cnt)

 

 

 

🧐 백준 10815, 10816(이진탐색)

🤔 Algorithm 과정 
1. 중복되어 입력되어도 비교만 하면 되기에 n이라는 set과 m이라는 리스트를 생성
2. 이후 m안의 원소를 돌면서 만약 m의 원소가 n에 있다면 1을 출력, 아니면 0을 출력해주면 된다.
3. 물론 위의 경우 m 리스트의 원소에 순서대로 접근하기 때문에 순서를 상관쓰지 않아도 된다.

🤫  solution_10815

# cf. n을 list로 했더니 시간초과가 났음.
# 즉, 중복된 결과가 들어가게 되어 set보다 시간복잡도가 더 걸리게 되는 것.
N, n = input(), set(map(int, input().split()))
M, m = input(), list(map(int, input().split()))
m_set = list(set(m))

for i in m:
    print(1, end = " ") if i in n else print(0, end = " ")



# 리스트를 실제로 분할해서 새로 저장하는 것은 O(N)으로 매우 무거운 연산

 

🤫 해결의 실마리(10816): 이진탐색

🤔 count 함수를 무턱대고 쓰면 안된다??
count함수는 시간복잡도가 O(n)시간이 걸려서 for문과 같이 쓰면 시간초과가 발생할 확률이 높다.

🤔 Algorithm 과정 
1. cnt = {}로 딕셔너리를 생성한다.
2. cnt라는 비어있는 딕셔너리에 i 즉, n의 원소가 없다면 cnt[i] = 1로 원소와 개수를 맵핑
3. 만약 i in cnt라면 원소의 개수를 증가시켜줘야 하므로 cnt[i] += 1을 통해 value(원소의 개수)를 증가
4. 이후 m 안의 어떤 원소 i에 대해 cnt에 i가 있으면 value를 출력, 없으면 0을 출력한다.

🤫  solution_10816(시간초과  ∵ count함수의 사용)

N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))

for i in m:
    print(n.count(i), end = " ") if i in n else print(0, end = " ")

🤫  solution_10816

N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))

cnt = {}
for i in n:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

# 딕셔너리 생성
# print(cnt)  => {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}

for i in m:
    if i in cnt:
        print(cnt[i], end = " ")
    else:
        print(0, end = " ")

 

 

🧐 백준 11478

🤔사실 문제에서 말하는 바는 등수를 출력하는 것과 동일!

🤔 Algorithm 과정 
1. s에 바로 문자열을 입력받는다.
이때, s에 "abcde"라는 문자열이 들어왔을때, s[1:3]으로 bc에 접근할 수 있다.]

2.  set_s = set()를 통한 set을 생성해주고
3. 이중 for문에서 위의 인덱스 슬라이싱원리를 이용해 부분문자열을 구한다.
4. 이때, set_s에 넣어주는데, 중복된 문자열은 추가되지 않는다.

🤫  solution_11478

s = input()
# print(s[1:3])  ba출력

set_s = set()

# 이중 for문을 돌면서 부분 문자열을 구하고 set_s에추가한다.
# 이때, set_s는 집합이기 때문에 중복된 문자열을 추가되지 않는다.
for i in range(len(s)):
    for j in range(i, len(s)):
        set_s.add(s[i:j+1])

print(len(set_s))