JinWoo Kim

백문이 불여일견, 백견이 불여일행.

2 minute read

개요

  • 이번주의 주제인 ‘정렬’에 관한 코딩테스트 문제를 풀고, 서로 리뷰해보기로 했다.

  • 내가 푼 문제들은 다음과 같다.

1. N번째 큰 수

  • 배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.

  • 배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다.

입력

  • 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보다 작거나 같은 자연수이다.

출력

  • 각 테스트 케이스에 대해 한 줄에 하나씩 배열 A에서 3번째 큰 값을 출력한다.

풀이


import sys
 
# 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 
 
T = int(sys.stdin.readline())
 
# 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 
 
for i in range(0,T):
	case = list(map(int,sys.stdin.readline().split()))
 
	# 배열 A에서 세번째로 큰 값을 매 줄마다 출력하라.
 
	case.sort()
	print(case[-3])

채점 결과 : 정답

2. 교수님의 기말고사

  • 안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

  • 알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호에서 말고 다른 강의실에서 시험을 치를 수 없게 되었다.

  • 공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 무조건 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학과 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

  • 각 시험은 xi분에 시작해서 yi분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, xi + yi ≤ xj 일 때 i 시험과 j 시험은 서로 겹치지 않는다.

  • 안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

입력

  • 다음과 같이 입력이 주어진다. 
    N M S
x1 y1
. . .
xN yN

출력

  • 교수님이 시험을 시작할 수 있는 시각을 출력하여라. 시작 가능한 시각이 여러 개 있으면 그중 가장 앞선 시각을 출력한다. 시험을 치룰 수 없다면 -1을 출력하여라.

제한

  • 1 ≤ N ≤ 100,000.
  • 1 ≤ M ≤ S ≤ 1,000,000,000.
  • 0 ≤ xi < xi + yi ≤ S.
  • 입력에 주어진 수들은 전부 정수다.

내 풀이

# your code goes here
import sys
 
# N은 해당 강의장에서 시험보는 다른 수업의 개수
# M은 우리 시험시간
# S는 강의장의 사용 제한 시간
 
# 첫줄에는 N,M,S가 주어진다
 
N,M,S = list(map(int,sys.stdin.readline().split()))
 
 
# 강의실 사용 가능시간을 time배열로 생성한다.
time = [x for x in range(0,S+1)]
 
 
# 두번째 줄부터 N+1줄까지는 다른 수업들의 시험 시작시간(xi)와 시험시간(yi)가 주어진다.
for i in range(0,N):
	xi,yi = list(map(int, sys.stdin.readline().split()))
 
	# 다른 과목의 시험 시작 시간으로 인해 빈 시간이 시험시간보다 적다면, 잔여 시간을 제거한다.
	if len(time[0:xi]) < M:
		del time[0:xi+yi]
  # 다른 과목의 시험 종료 시간과 빈 시간의 끝이 시험시간보다 적다면, 잔여 시간을 제거한다.
	elif len(time[xi+yi:-1]):
		del time[xi:-1]
  # 다른 과목의 시험시간을 제거한다.
	else:
		del time[xi:xi+yi]
	
	
 
	# 만약 남아있는 시간대가 시험을 볼수있는 시간보다 적다면, 시험은 치룰수 없다.
	if len(time) < M:
		print(-1)
		break
		
if len(time) >= M:
	# 남아있는 시간대를 탐색한다.
	for i in range(0,len(time)-M):
		# 정렬되어있으므로, 연속적이라면 i+M번째 항목과 i번 항목의 차이는 M이다.
		if time[i+M-1]-time[i] == M-1:
			print(time[i])
			break

채점 결과 : 시간 초과

오답 사유 고찰

  • 현재 내 풀이의 시간 복잡도는 최소 O(2N)정도로 확인된다.

    • 마지막 잔여시간 검사의 반복문을 다른것으로 대체하는등의 해법이 필요해보인다.

You May Also Enjoy