Trey

백준 1764번: 듣보잡 (www.acmicpc.net/problem/1764) 💡접근 제한 시간 : 2초 듣도 못한 사람 리스트, 보도 못한 사람 리스트에서 중복 원소를 찾아야하는 문제이다. 두개의 리스트를 만들어 이중 for loop으로 모든 원소를 비교할 경우, 최악의 경우 50만x50만 = 2500억번의 연산을 해야하므로 시간초과가 날 수 있다. 따라서, 탐색하는 시간이 O(1)걸리는 python dictionary를 사용해서 풀어보면 어떨까? 먼저, 듣도 보도 못한 종류의 관계없이, 이름을 key값으로 가져가고, key가 처음 생기는 경우라면 1을 넣어준다. → 삽입에 총 O(n) 시간복잡도가 소요됨 key값이 앞에서 만들어져있는 상태에서 또 같은 key값이 입력값으로 들어온다면, 해당 key값..

백준 1676번: 팩토리얼 0의 개수 (www.acmicpc.net/problem/1676) 💡접근 시간 제한 : 2초 구해야 하는것은 팩토리얼 결과값의 1의 자리부터 0이 나오지 않는 첫번째 숫자까지 0의 개수를 구하는것이다. 단순히 팩토리얼을 다 계산한 다음에 뒤에서부터 0의 개수를 세면 되지 않을까? ⚠️ 일단 문제에서 가장 큰 수인 500!의 자릿수는 무려 528이다... ⚠️ 역시 파이썬...! Python3.0부터는 int에 사이즈가 없어져서 자료형은 int를 사용해도 될 것 같다. https://docs.python.org/3/whatsnew/3.0.html#integers 팩토리얼을 계산한 후에 뒤에서 0의 개수를 세는 방법으로 풀겠다. 💡배운점 및 오답원인 다른 사람들의 풀이를 보니, J..

백준 1620번: 나는야 포켓몬 마스터 (www.acmicpc.net/problem/1620) 💡접근 시간 제한 : 2초 포켓몬을 리스트에 저장하고, 숫자로 변환 가능한 경우 index-1로 검색, 숫자로 변환 가능하지 않은 경우는 이름으로 index 검색하자. isdigit() 함수의 시간복잡도는 O(n)이다 → 한 문자열의 최대 길이가 20이니까, 최악의 경우 20x10만 = 200만이다. (이 함수는 시간초과랑 크게 관련 없을듯) 풀이코드1번으로 하니까 시간초과가 났는데, index 함수의 시간복잡도는 O(n)이기 때문에, 10만개의 포켓몬들 중에서 찾을때는 최악의 경우 매번 10만번을 탐색한다.. 즉 10만x10만 = 100억번. 그럼 데이터 읽기 부분을 어떻게 개선 시킬 수 있을까? → 해쉬 자..

백준 1541번: 잃어버린 괄호(www.acmicpc.net/problem/1541) 💡접근 첫번째 숫자 다음 숫자부터, 마이너스 부호가 있을경우 다음 마이너스 부호가 나타나기전까지의 숫자들을 괄호처리하여 더한다. (아래의 그림을 참고하면 쉽게 이해될 것이다) 그리고 마이너스 부호가 없는 입력값의 경우는 다 더하기! 참고로, 예시를 보니 숫자의 위치는 바뀌지 않고, 괄호로 묶는다고해서 부호가 바뀌지는 않는다. 💡배운점 및 오답 원인 생각보다 예외조건 처리하는것이 까다로웠다.. 💡풀이 코드 input = input() # 마이너스 부호가 있으면 분류하기 if '-' in input: subs = input.split('-') # 마이너스 부호가 있었던 숫자들의 합 구하기 subs_sum = 0 for i ..