본문 바로가기

코딩테스트

(39)
백준 10974 모든 순열 실버(3) PYTHON from itertools import permutationsn = int(input())arr = [i for i in range(1,n+1)]answer = list(permutations(arr))for i in answer: print(' '.join(map(str,i)))파이썬에 있는 순열 모듈을 이용해주고,마지막에 출력하는 과정만 살짝 바꾸어 주면 된다.
프로그래머스 숫자의 표현 level 2 PYTHON def solution(n): answer = 0 count = 0 for i in range(1,n+1): for j in range(i,n+1): answer += j if answer == n: count += 1 break answer = 0 return count 이중 for문을 사용하여 문제를 해결할수있다고 생각했다.하지만 시간 초과떄문에 문제를 해결할수 없었다. 시간을 줄일려면 어떻게 해야할까라는 부분에 대해서 고민을했다.def solution(n): count = 1 for i in range(1,n//2+1): answer = ..
백준 가로수 2485(실버4) PYTHON https://www.acmicpc.net/problem/2485 import mathfrom functools import reducedef gcd_multiple(list): return reduce(math.gcd,list)n = int(input())answer = []check = []number = []for i in range(n): k = int(input()) answer.append(k)for i in range(len(answer)-1): check.append(answer[i+1]-answer[i])result = gcd_multiple(check)total = (answer[-1] - answer[0])//result+1print(total-len(answer..
백준(4949) 균형잡힌 세상 PYTHON https://www.acmicpc.net/problem/4949 while (True): word = input() if word == ".": break stack = [] for i in word: if i == '(' or i == '[': stack.append(i) elif i ==')': if len(stack) != 0 and stack[-1] == '(': stack.pop() else: stack.append(i) elif i ==']': if len(stack) != 0 and sta..
백준 숫자 카드 2 PYTHON https://www.acmicpc.net/problem/10816 import bisectimport sysinput = sys.stdin.readlinea = int(input())check = list(map(int, input().split()))check.sort()b = int(input())find = list(map(int, input().split()))count = []for num in find: left_index = bisect.bisect_left(check, num) right_index = bisect.bisect_right(check, num) count.append(right_index - left_index)for i in range(len(count))..
백준 순서쌍의 곱의 합 13900 PYTHON https://www.acmicpc.net/problem/13900import itertoolsimport sysinput = sys.stdin.readlinen = int(input())answer = list(input().split())check = []for i in range(len(answer)): answer[i] = int(answer[i])combination = list(itertools.combinations(answer,2))for i in range(len(combination)): check.append(combination[i][0] * combination[i][1])print(sum(check))처음 문제를 보고 2가지 경우만 고려하면 되니, 조합을 생각하였다. ..
백준 구간 합 구하기 4 11659 import sysinput = sys.stdin.readlinen,m = map(int ,input().split())check = list(map(int, input().split()))prefix_sum = [0]*(n+1)answer = 0for i in range(1,n+1): prefix_sum[i] = prefix_sum[i-1] + check[i-1]for _ in range(m): a,b = map(int, input().split()) answer = prefix_sum[b] - prefix_sum[a-1] print(answer)처음 문제를 풀때는 구간별로 전부 수를 더하였지만, 시관초과가 나왔다.O(n^2)의 시간복잡도가 필요하기 때문에 시간초과가 나온것 같다...
백준 최대힙 11279 import sysimport heapqn = int(input())heap = []for i in range(n): a = int(sys.stdin.readline()) if a == 0: if heap: print((-1)*heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap,(-1)*a) 파이썬 힙 모듈을 사용해주었다. 힙은 heappush,heappop은 최소힙에서만 작용하기때문에 -1을 곱해주어 가장큰 값을 가장 작은값으로 바꾸어 주었다.