전체 글92 백준 14425. 문자열 집합 굉장히 쉬웠던 문제! 그냥 집합에 차례대로 집어넣고 탐색하면 된다. 파이썬의 집합은 해쉬맵 자료형을 사용하므로 접근 속도가 빨라, 탐색 복잡도는 O(1)이라 시간 초과에 걸리지 않는다. n, m = map(int, input().split()) s = set() for i in range(n): s.add(input()) count = 0 for i in range(m): check = input() if check in s: count += 1 print(count) 2022. 6. 7. 백준 10815. 숫자 카드 다음 단계인 집합과 맵. 처음에 문제를 봤을 때는 왜 집합을 이용하는지 이해하지 못했다. 문제의 조건에서도 카드의 숫자가 중복되는 일은 없다고 하는데 굳이 집합을 써야 하나..? 그래서 리스트와 in list 를 활용한 코드를 제출했더니 날 반기는 시간 초과 ㅋㅋㅋㅋㅋ 약간의 구글링 후에 in을 쓸 때는 집합이 리스트보다 시간 복잡도가 훨씬 낮다는 점을 알아냈다. 해쉬 맵을 쓰기 때문에 (이는 후에 포스팅할 거리) 시간 복잡도가 O(1)이고, 리스트의 경우에는 모든 원소를 뒤져야 하기 때문에 시간 복잡도가 O(n)이다. 그래서 집합을 쓰면 쉽게 풀림. import sys n = int(sys.stdin.readline()) cards = set(map(int, sys.stdin.readline().spl.. 2022. 6. 7. 백준 18870. 좌표 압축 생각보다는 까다로웠던 문제. 단순히 이중 반복문을 사용하면 금방 풀 수 있을 거라고 생각했지만, 보기 좋게 시간 초과가 떴다 ,,, input 대신 성능이 좋은 sys.stdin.readline()을 이용해봐도 마찬가지. 그래서 이중 for문을 사용하지 않고 정렬 후 index 함수를 이용하는 방법을 선택했으나, 이 또한 실패했다. 분석해보니 index함수에서 어차피 다시 반복을 하니까 이중 반복문의 성능이 크게 개선되지 않은 듯 했다. 그래서 집합으로 바꾸고, 해당 인덱스를 딕셔너리에 넣는 방법으로 정리한 후, 리스트를 반복하며 출력하는 방법을 선택했다. 이렇게 하면 최악의 경우 n*n의 반복문이 돌 일이 없기 때문에 가능한 것으로 보인다. import sys n = int(sys.stdin.readl.. 2022. 6. 7. 백준 10814. 나이순 정렬 나이 순으로 정렬하고, 나이가 같다면 리스트의 순서를 바꾸지 않는 문제. 역시 클래스의 연산자 오버로딩을 이용해서 풀었다. n = int(input()) class Info : def __init__(self, age, name): self.age = age self.name = name def __lt__(self, c): return self.age < c.age lst = [] for i in range(n): age, name = input().split() age = int(age) lst.append(Info(age, name)) lst.sort() for i in lst: print(i.age, i.name) __lt__ ( 2022. 6. 7. 이전 1 ··· 14 15 16 17 18 19 20 ··· 23 다음
