본문 바로가기

문제풀이6

[ SWEA ] D2 - 2001, 1989, 1986, 1984 - python 문제풀이 2001 파리퇴치 퇴치할 파리 정사각형이 어디까지 이동할 수 있을 지 파악해서 갈 수 있는 곳 까지만 for문을 도는게 그나마 시간을 조금이라도 줄이는 방법 for tc in range(int(input())): N,M = map(int, input().split()) fly = [list(map(int, input().split())) for _ in range(N)] max_value = 0 for i in range(N-M+1): for j in range(N-M+1): row_idx = i col_idx = j tmp = 0 for k in range(M): tmp += sum(fly[row_idx+k][col_idx:col_idx+M]) if tmp > max_value: max_value = .. 2021. 6. 24.
[ Codility ] MaxProductOfThree - python 개념 Lesson 6. Sorting 두 번째 문제 문제요약 입력으로 주어진 정수 배열에서 숫자 3개를 곱한 값 중 최대를 리턴하라 첫번째 접근(효율성 고려X) 문제에 충실히 만들수 있는 모든 인덱스 조합을 만들고, 그 조합대로 값을 곱한 뒤 최대일 경우 max-value값을 갱신해주는 코드(3개니까 당연히 3중 for문을 돌고, 시간복잡도는 O(N**3)이상) def solution(A): max_v = A[0]*A[1]*A[2] for i in range(len(A)-2): for j in range(i+1, len(A)-1): for k in range(j+1,len(A)): if A[i]*A[j]*A[k]>max_v: max_v = A[i]*A[j]*A[k] return max_v 두번째 접근(통.. 2021. 6. 18.
[ Codility ] Distinct - python 개념 Lesson 6. Sorting 첫 번째 문제 문제요약 N개의 정수를 원소로 갖는 배열A가 입력으로 주어질 때, 원소들의 중복을 제외한 총 개수를 리턴하라 첫 번째 접근 (효율성 고려X, 통과는 O) 파이썬 내장함수를 이용한 풀이(set로 중복 제거한뒤 그 개수만 리턴하는 코드) # 방법 1 def solution(A): return len(list(set(A))) # 방법 2 - 굳이 list를 안해도 돼 ㅎㅁㅎ def solution(A): return len(set(A)) 생각보다 너무 빨리 대충 푼 것 같은 느낌에 set 쓰지 않고 푸는 다양한 방식을 찾아보기로 했다 두 번째 접근 (효율성X) 처음 파이썬을 배웠다면 썼을 것 같은 코드로 문제에 충실하게 짠 코드. A를 쭉 돌다가 지금까지 나.. 2021. 6. 18.
[ Codility ] PassingCars - python 개념 Lesson 5. Prefix Sums 네 번째 문제 문제요약 0,1로만 이루어진 배열A가 입력으로 주어짐. 0은 동쪽으로 가는 차, 1은 서쪽으로 가는 차일때 서로 마주칠 수 있는 케이스는 얼마나 되는지 리턴하는 문제. 예시) [0,1,0,1,1] => (0,1),(0,3),(0,4),(2,3),(2,4) 5개 => 5리턴 첫번째 접근( 효율성 고려X ) 문제에 충실하게, 앞에서부터 순회하다가 0이 나오면 그 뒤에 있는 1의 개수를 구해 더해나가는 방식 def solution(A): cnt = 0 for i in range(len(A)-1): tmp = 0 if A[i] == 0: tmp += A[i+1:].count(1) cnt += tmp return cnt 답은 맞지만 역시 타임아웃. for.. 2021. 6. 17.
[ Codility ] MinAvgTwoSlice - python 개념 Lesson 5. Prefix Sums 세 번째 문제 문제요약 n개의 원소를 갖는 리스트가 주어지면, 0부터 n-1사이에서 두 수를 뽑아 작은 값(P)를 시작인덱스, 큰 값(Q)를 끝인덱스로 정해 A[P:Q+1]에 해당하는 리스트를 슬라이스라고 한다. 만들 수 있는 모든 슬라이스 중 슬라이스 내부 원소들의 평균이 가장 낮을때의 P값(시작인덱스)를 리턴. 첫 번째 접근(효율성 고려X) def solution(A): n = len(A) min_v = sum(A)/n r = 0 comb = [(i,j) for i in range(n-1) for j in range(i+1,n)] for pair in comb: new_v = sum(A[pair[0]:(pair[1]+1)])/(pair[1]-pair[0]+.. 2021. 6. 16.
[ Codility ] CountDiv - python 개념 Lesson 5. Prefix Sums 첫 번째 문제 문제요약 입력으로 정수 A, B, K가 주어졌을 때 정수 A부터 정수 B(를 포함해서) 사이에 있는 정수들 중 K로 나누어 떨어지는 수들의 총 개수를 리턴하라 첫번째 접근(효율성 고려X) 문제에서 풀이한 방식 그대로 코드 구현 def solution(A, B, K): sn = A # 01 starting number를 A로 설정 cnt = 0 while sn 2021. 6. 15.

티스토리툴바