요격 시스템 문제 바로가기 나의 풀이 def solution(targets): count = 0 current = 0 targets.sort(key=lambda x: x[1]) for t in targets: if current <= t[0]: current = t[1] count += 1 return count CODE REVIEW 최댓값을 구하라 해서 미사일 배치를 어떻게 해야할지 막막했는데, targets을 오름차순으로 정렬하면 풀기가 편리해진다. 첫 번째 미사일을 범위로 정하고 다음 미사일들이 이 범위에 속하는지 아닌지를 확인하며 진행하는 방식이다. x[0]이 아닌 x[1]을 key로 정렬하는 이유는, 예제에서 볼 수 있듯이 최솟값을 기준으로 하면 반례가 생기기 때문이다.
짝수와 홀수 문제 바로가기 나의 풀이 def solution(num): answer = 'Odd' if num % 2 == 0: answer = 'Even' return answer CODE REVIEW 간단한 구현 문제. 나눗셈을 할 때에 나머지는 % 몫은 //을 사용하면 된다.
평균 구하기 문제 바로가기 나의 풀이 def solution(arr): answer = sum(arr)/len(arr) return answer CODE REVIEW 간단한 구현 문제. 예제에서 input이 [5,5]일 때에 output이 5.0이 아닌 5이길래 나누어 떨어질 땐 따로 처리해야하나 고민했는데, 그럴 필요는 없었다. 5.0으로 출력되어도 정답 처리된다.
백준 1654번 바로가기 나의 풀이 # 입력 n, m = map(int,input().split()) lines = [] for _ in range(n): lines.append(int(input())) start,end = 1,max(lines) # 처리 while start <= end: mid = (start + end) // 2 temp = 0 for l in lines: temp += (l // mid) if temp >= m: start = mid + 1 else: end = mid-1 print(end) CODE REVIEW 이분탐색을 응용해서 해결하는 문제. 처음 봤을 때에는 막막했는데, 최종 자른 선의 길이를 기준으로 이분 탐색을 실시해서 답을 찾아내었다. start=1, end=max(lines)로 설정했는데, 만일 end=min(lines)로 설정하면 [1,100,100,100,100]같은 input의 경우 1을 출력해서 문제가 발생한다.
백준 18111번 바로가기 나의 풀이 # 입력 n, m, b = map(int, input().split()) blocks = [] for _ in range(n): for i in map(int, input().split()): blocks.append(i) from collections import Counter blocks=Counter(blocks) time = 1000000000 current = 0 # 처리 for h in range(257): temp = 0 a = b for i in blocks.keys(): dif = h-i if dif >= 0: temp += dif * blocks[i] a -= dif * blocks[i] else: temp -= dif * blocks[i] * 2 a -= dif * blocks[i] if a >= 0: if time >= temp: time = temp current = h print(time, current) CODE REVIEW 브루트포스로 풀어내는 문제. 조건에 맞게 for문을 작성하는게 은근 까다로워 푸는데 시간이 오래 걸렸다. python3이라 그런지 시간 초과 에러가 발생해서 collections라이브러리의 Counter를 이용해서 풀어냈다. 모든 땅을 각각 저장하는 대신 땅의 높이에 따라 정리하니까 시간 복잡도가 O(n*m)에서 O(256)으로 줄어들었다. 반례 모음으로 충분히 테스트 해본 뒤에 결과를 제출하자. 생각지도 못한 반례가 은근 있어서 놀랬다.