14464번: 소가 길을 건너간 이유 4
첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.
www.acmicpc.net
import sys
C, N = map(int, sys.stdin.readline().rstrip().split())
chickens = [int(sys.stdin.readline().rstrip()) for _ in range(C)]
chickens = sorted(chickens)
cows = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
cows = sorted(cows, key=lambda x: (x[1], x[0]))
visited = [0 for _ in range(C)]
ans = 0
for s, e in cows:
for idx, value in enumerate(chickens):
if s <= value <= e and visited[idx] == 0:
ans += 1
visited[idx] = 1
break
print(ans)
이 문제는 우선순위큐로 쉽게 생각하고 덤볐다간 고생하기 쉽다
1. 닭은 오름차순 정렬한다.
2. 소는 종료시간을 기준으로 오름차순 정렬한다.
아래와 같은 Case의 경우를 대비하기 위해서였다.
닭 : 2, 4
소: (1, 5) (2, 3)
출처: https://data-make.tistory.com/578 [Data Makes Our Future]
3. 이미 도와준 닭인지 기록할 배열을 생성한다.
3. 전체 소를 순회한다.
4. 전체 닭을 순회한다.
5. 닭이 소시작 <= 닭 <= 소끝 의 조건을 만족하면서 아직 도와주지 않은 닭이라면 정답에 1을 추가한다.
6. 도와준 닭 기록 배열에 닭의 인덱스를 기록한다.
7. 닭 순회 루프를 종료한다.
소 순회 내에서 닭 순회 중이기 때문에 닭이 도와줬다면 나머지 닭을 순회하면 안된다. 왜냐하면 소도 한번, 닭도 한번의 도움을 주고 받아야 하기 때문이다.
8. 이 과정을 모두 반복한 후, 정답을 출력한다.
PS. 이 소스는 파이썬으로 제출하면 시간초과가 발생한다. Pypy3 로 제출해야 통과된다.
PS. 어찌보면 이런문제는 어설프게 알고리즘 공부한 사람보다 아예 공부하지 않은 사람이 의식의 흐름대로 풀면 더 쉽게 풀릴 것도 같다.
여담.. 이 문제는 정말 어려웠다. 처음에는 heapq 를 이용해서 잘 풀었다고 생각했는데 계속 틀리고 반례를 알 수 없어서 고생을 많이 했다.
하루 꼬박 문제를 들여다보다가 도저희 안돼서 다른 분의 코드를 참고해서도 겨우 풀었고 끝내 내가 제출한 코드가 어디서 문제가 발생했는지 모르겠어서 개운치 않다.
결과 코드만 놓고봤을 땐 별거 아닌것 처럼 보이지만 말이다...
그리고 처음부터 너무 이중 루프를 쓰는걸 꺼리다보니 늪에 빠지게 되는듯하다. 처음엔 조금 무식하게 먼저 풀어보는것도 좋은방법일듯..
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
출처: https://data-make.tistory.com/578 [Data Makes Our Future]