[Python] BOJ 11946 - ACM-ICPC

www.acmicpc.net/problem/11946

11946번: ACM-ICPC

단순 구현문제이지만, 생각보다 빡세서 포스팅해본다.

일단 입력값이 많고, 그에 대한 순서 처리가 생각보다 힘들다.

 

1. dic이라는 딕셔너리를 만들고 미리 1번팀의 1번문제 결과부터 n번팀의 m번 문제결과 까지 [0, -1]을 만들어 놓는다.

   (주석에 설명했듯이 '틀린횟수'와 '총 시간'이다)

 

2. q개의 로그를 입력받는다. 만약 log[3]이 'AC'가 아니라면 틀린 것이므로 해당하는 팀의 문제결과인 

   dic[dic[(int(log[1]), int(log[2]))]의 0번째 index값을 1증가시켜준다 (틀린횟수 1 증가)

 

3. log[3]이 'AC'라면 정답을 맞춘 것이므로 해당하는 팀의 문제결과인

    dic[dic[(int(log[1]), int(log[2]))]의 1번째 index값에 틀린횟수 * 20 + 맞춘시간을 넣어준다

    (12번째 줄을 넣은 이유는 만약 맞춘 문제를 시간이 지나서 또 맞추는 경우가 있기 때문에

     한번 맞춘 문제를 또 맞췄을 경우 그냥 무시하기 위해서이다. 문제를 맞추는 시간은 시간경과순으로 입력

     되기 때문에 무시해도된다.)

 

4. dab배열에 팀의 개수 n만큼 반복문을 돌며 [i, 0, 0]을 넣어준다. [i번째 팀, i번째 팀의 맞춘문제 수, 걸린 시간]

 

5. for문으로 dic을 돌면서 dic[(i, j)][1]이 0 이상이면 해당 문제를 맞췄으므로

   (그 문제를 맞추지 못했으면 dic[(i, j)]가 -1이다.)

   dab[i-1][1]을 1증가시키고 dab[i-1][2]에 그 문제를 맞추는 데 걸린 시간인 dic[(i, j)][1]을 증가시켜준다.

 

6. dab배열을 정렬한다. (맞춘 문제 수 x[1]는 내림차순, x[1]이 같으면 걸린 시간 x[2]를 오름차순으로, x[2]까지 같으면

   팀 번호인 x[0]을 오름차순으로 정렬)

 

7. dab의 index를 출력한다.

 

n, m, q = map(int,input().split())
dic = {}
for i in range(1, n+1):
	for j in range(1, m+1):
		dic[(i, j)] = [0, -1] # 틀린횟수, 총 시간
for _ in range(q):
	log = input().split()
	if log[3] != 'AC':
		dic[(int(log[1]), int(log[2]))][0] += 1
	else:
		if dic[(int(log[1]), int(log[2]))][1] < 0:
			dic[(int(log[1]), int(log[2]))][1] = dic[(int(log[1]), int(log[2]))][0] * 20 + int(log[0])
dab = [[i,0,0] for i in range(1, n+1)]
for i in range(1, n+1):
	for j in range(1, m+1):
		if dic[(i,j)][1] >= 0:
			dab[i-1][1] += 1
			dab[i-1][2] += dic[(i,j)][1]
dab.sort(key = lambda x: (-x[1], x[2], x[0]))
for i in dab:
	print(*i)

(solved.ac 티어: 실버 5)

 

# 확실히 단순 구현문제는 최적화를 잘해줘야 하는 파이썬 입장에서는 생각보다 힘든 것 같다.

   (파이썬은 생각나는 대로 막짜면 시간초과 나는 경우가 많다..)