[백준OJ] #1946 ; 신입사원

[해결 IDEA]

- 여러번의 fail 끝에 해결했다.

- dictionary로 만들어줘서, key값 sort를 해주면 위에꺼 (서류가 현 index보다 등수 높음) 랑만 비교해 주면 될줄 알았다.

- 하지만, 예를들어서 [[1,6],[2,4],[3,7],[4,1],[5,3],[6,2],[7,5]]에서 [6,2]는 [4,1]보다 둘다 등수가 낮기 때문에 떨어지는 경우를 생각해, 전반적인 비교가 필요했고, 

  해결방안으로, 마지막으로 신입사원으로 뽑힌 인덱스랑 계속 비교해줬다. 

 

[그림 설명]

 

[CODE]

 

import sys

def pickme(arr):
	pick = 1
	new_list = list(map(list, zip(*arr)))
	# 입력 받은 리스트를 dictionary로 한후 key값에 맞게 sort
	dic = dict(zip(new_list[0],new_list[1]))
	sdic = sorted(dic.items())

	i=0
	nonpass=1
	#nonpass 는 통과하지 못한 사람들 카운트
	j=1
	while True:
		if sdic[i][1] > sdic[j][1]:
			pick += 1
			i += nonpass
			j = i+1
			nonpass = 1
			if i==len(sdic)-1 or j==len(sdic):
				break
		else:
			j += 1
			nonpass += 1
			if j==len(sdic):
				break	
			
	return pick

if __name__=="__main__":
	ans = []
	a = int(input())
	for i in range(a):
		arr=[]
		b = int(input())
		for j in range(b):
			arr.append(list(map(int, sys.stdin.readline().split())))
		ans.append(pickme(arr))
	for p in ans:
		print(p)

 

- 유형 : Greedy Algorithms(탐욕법, 탐욕 알고리즘)

- 반례를 찾느라 힘들었다..

- 반례 찾는 연습 더 해야할 것 같다

 

[CODE modify]

- modify는 다른 사람이 짠 코드를 보고 감탄하며 이해한 코드 입니다.

 

- 시간 제한이 2s 이었는데 거의 1.6s 정도 나와,  더 단순하게 짜볼 필요가 있다.

- sort 할 시간을 아끼기 위해 등수를 배열 index로 넣는 방법이 있다.

 

 

import sys
input = sys.stdin.readline

def pickme(test_num):
	for _ in range(test_num):
		n = int(input())
		arr = [0]*(n+1)
		for __ in range(n):
			p1,p2 = map(int,input().split())
			arr[p1] = p2
		winner = arr[1]
		pick = 1 #winner는 무조건 뽑히니까
		for person in arr[2:]:
			if winner > person:
				pick +=1
				winner = person # 더 높은 등수로 갱신
		print(pick)

if __name__=="__main__":
	test = int(input())
	pickme(test)

- 524ms 나온다..

- 메모리도 절반정도 줄였다.

- 너무 복잡하게 생각하지 말자