EDOC 2022.07 4주차

<백준 10815번>- 숫자 카드

N = int (input())
Nlist = []
for i in range(N):
    plus = int(input())
    Nlist.append(plus)
M = int (input())
Mlist = []
for i in range(M):
    plus = int(input())
    Mlist.append(plus)
result = []
for i in range(M):
    if Mlist[i] in Nlist:
        result.append(1)
    else:
        result.append(0)
print(result)

잘 돌아간다. 하지만 시간복잡도 문제로 인해 백준에서는 런타임 에러가 난다. 그리고 입력 한줄로 못 받는 거랑 리스트 형식으로 출력되는 문제도 있는듯

 

import sys

N = int (sys.stdin.readline())
Nlist = list(map(int, sys.stdin.readline().split()))
M = int (sys.stdin.readline())
Mlist = list(map(int, sys.stdin.readline().split()))
result =[]
for i in range(M):
    if Mlist[i] in Nlist:
        result.append(1)
    else:
        result.append(0)
realresult=" ".join(map(str,result))
print(realresult)

시간복잡도 줄이려고 sys 모듈을 가져왔다 (input() 대신 sys,stdin.readline() 쓰기)

map()으로 한 줄로 입력받고

join()으로 문자열로 출력되게 바꿈

 

근데 또 런타임에러가 난다

from sys import stdin 로 바꿔봤지만 예상했듯이 소용없었다.

---

이 문제는 여러 가지로 시간복잡도를 줄일 수 있다. (딕셔너리 키 이용하기.  set이용하기. 등)

그 중 '이분탐색'이라는 것을 공부해서 해결해보겠다.

 

이분탐색 : 가지고 있는 자료를 둘로 나누어 탐색한다는 의미

 

하나하나 찾아보는 순차 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있다. ( 시간복잡도 이분 탐색 O(logn) < 순차 탐색 O(n) )

둘의 차이를 잘 설명한 이미지 -> https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

이분탐색을 하려면 자료를 미리 정리해두어야 함 sort()

 

이분탐색 구조도 대충 작성

from sys import stdin
N = int(stdin.readline())
Nlist = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
Nlist.sort()
Mlist = list(map(int, stdin.readline().split()))

for value in Mlist:
    left = 0
    right = N-1
    while True:
        if left == right:
            print(0, end=' ')
            break
        mid = (left +right)//2
        if Nlist[mid] == value:
            print(1, end=' ')
            break
        elif Nlist[mid] > value:
            right = mid
        else:
            left = mid

오 구조도부터 틀렸다. 왜냐면

우리 리스트에는 모든 숫자가 다 있는 게 아니다.

그리고 mid가 아니라는 게 판명됐으니 mid까지 다 삭제하는 게 좋다 (mid+1,mid-1)

리스트에 찾는 숫자가 없으면 Nlist[mid] == value가 작동하지 않으니 무조건 left가 right보다 오르쪽에 있는 이상한 상황이 발생한다.

그러므로,

from sys import stdin
N = int(stdin.readline())
Nlist = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
Nlist.sort()

for value in list(map(int, stdin.readline().split())):
    left = 0
    right = N-1
    while True:
        if left > right:
            print(0, end=' ')
            break
        mid = (left +right)//2
        if Nlist[mid] == value:
            print(1, end=' ')
            break
        elif Nlist[mid] > value:
            right = mid-1
        else:
            left = mid+1

!성공

 

+

print() 안에 end=' '

띄어쓰기 쓸 수 있음

---

<백준 1062번>- 가르침

어려워서 다른 분의 코드를 보고 공부해 작성했다.

from sys import stdin
from itertools import combinations
from string import ascii_lowercase

N, K= map(int, stdin.readline().split())

if K < 5 : #아는 숫자가 5 이하면 아무 단어도 모름
    print(0)
    exit()

word =[]
for i in range(N): #앞의 anta와 뒤의 tica를 없애고 set으로 만들고, a/c/i/t/n을 제외한 알파벳을 리스트에 저장
    word.append(set(stdin.readline().rstrip()[4:-4]).difference('a','c','i','t','n'))

# a/c/i/t/n을 제외한 알파벳 모음
exceptAcitn = set(ascii_lowercase).difference('a', 'c', 'i', 't', 'n')
maxCount = 0

 #모든 조합 구하기 combinations()
 #a/c/i/t/n과 a/c/i/t/n을 제외한 알파벳 중 k - 5개의 조합으로 만들 수 있는 단어 개수의 최대값
for x in list(combinations(exceptAcitn, K - 5)):
    count = 0
    for k in word:
        if not k.difference(x):
                count += 1
        maxCount = max(maxCount, count)
print(maxCount)

-quit(),  exit() 함수

프로그램을 종료하는 함수이다.

 

 string 모듈 //  ascii_lowercase 

>>> import string
>>> string.ascii_lowercase
'abcdefghijklmnopqrstuvwxyz'

strip()함수 

• strip() : 인자로 전달된 문자를 String의 왼쪽과 오른쪽에서 제거합니다.
• lstrip() : 인자로 전달된 문자를 String의 왼쪽에서 제거합니다.
• rstrip() : 인자로 전달된 문자를 String의 오른쪽에서 제거합니다.

difference() 함수

차집합 구하는 함수

>>> a = set([1, 2, 3, 4, 5, 6])
>>> b = set([4, 5, 6, 7, 8, 9])

>>> c = a.difference(b)
>>> print(c)

{1, 2, 3}

 

리스트에 있는 값들의 모든 조합을 구하기

• 하나의 리스트에서 모든 조합을 계산을 해야 한다면, permutations, combinations을 사용
• 두개 이상의 리스트에서 모든 조합을 계산해야 한다면, product를 사용