✅ 문제 - [백준] 문자열 폭발 (9935번) ✅ 처음 풀이 코드 - 시간초과import syssentence = sys.stdin.readline().rstrip()bomb = sys.stdin.readline().rstrip()while True: tmp = sentence.replace(bomb,"") if tmp == sentence: break sentence = tmpif len(sentence) == 0: print("FRULA")else: print(sentence)bomb이 있는 경우 replace 하고replace한 결과 tmp가 sentence랑 같은 경우 반복문을 멈춘다 ❌ 문제점 이런식으로 풀면 replace 메소드가 문자열의 처음부터 끝..
✅문제 - AC(5430번) ✅아이디어🔵문제 조건시간제한이 1초 이므로 연산을 2000만 번 안에 끝내야 한다. (Python 은 1초에 2000만 번의 연산을 한다고 가정하자)이때 함수의 최대 길이가 100,000이므로 시간 복잡도가 O(N^2)을 넘으면 시간 초과에 걸리게 된다.🔵실패 했던 아이디어실제로 R인 경우에는 reverse를 D인 경우에는 pop을 실행했다. 이때 함수의 길이만큼 for문을 돌려야 하고 그 안에서 if 문을 돌려야 하므로 시간 복잡도가 O(N^2)이 된다.정말 처참한 결과다🔵성공한 아이디어실제로 pop 이나 reverse를 진행하지 않는 방법을 생각했다.1. 함수에서 RR이 나오면 순서가 바뀌지 않으므로 입력받은 함수에서 replace("RR","")을 통해 모든 RR을..
✅문제 - 문자열 집합(14425번)✅오늘 배운점문제에서 두 집합 간의 비교를 위해 in method를 사용하였다.하지만 처음에 list에서 in method를 사용한 경우에 시간이 3724ms나 소요 되어 문제가 있다고 판단했다.그래서 list를 set로 변경하였더니 시간이 116ms로 감소하였다.이유는 파이썬 홈페이지에서 확인할 수 있었다set 자료형에서 in method의 시간복잡도는 최선: O(1) 최악: O(N)이고list 자료형에서 in method의 시간복잡도는 O(N)인 것을 확인할 수 있었다. ❗❗❗ 앞으로 성분의 포함 여부를 사용할 때는 set를 사용하자!! ✅첫 코드 - (시간 3724ms)import sysindex = int(sys.stdin.readline().rstrip()..
✅문제 ✅풀이 - (시간 초과)import syssys.stdin.readline()num_list = list(map(int,sys.stdin.readline().rstrip().split()))rank = sorted(set(num_list))for i in num_list: print(rank.index(i),end=" ") 해설입력 받은 수를 set()를 통해 중복을 제거하고 정렬하여 for 문을 통해 index를 찾아 출력하였다. ❗❗❗시간 초과 발생 이유 ( .index() method ) 마지막 출력문에서 num_list 를 탐색하며 index(method)를 사용하는데.index() method는 리스트를 순회하며 값을 찾으므로 시간 복잡도가 O(N)이 된다.👎.index() me..
문제 ✅중요 개념계수 정렬 ( Counting Sort ) 계수 정렬이란 sort 메소드를 이용하는 것이 아니라 정렬하려는 List의 값 중 가장 큰 값을 List의 size + 1을 크기로 가지는 List를 생성하여 index를 정렬하는 숫자의 해당 숫자로 사용하여 Sorting을 하는 방법을 말한다.👍자세한 내용은 링크를 참고해 주세요 -- https://www.programiz.com/dsa/counting-sort Counting Sort (With Code in Python/C++/Java/C)Counting Sort Algorithm In this tutorial, you will learn about the counting sort algorithm and its implement..
처음 코드 ( 실행시간 1120ms) import sys# 소수 리스트 생성 함수def prime(n): sieve = [True] * (n+1) for i in range(3,int(n**.5)+1,2): if sieve[i]: sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i]) return [2]+[i for i in range(3,n+1,2) if sieve[i]]# 파티션 구하는 함수def getPartition(prime:list,n:int)->str: left, right = 0, len(prime)-1 partition = "" while left n: right -= 1 ..
