5480 전함

2차원 좌표평면 안에 전함들이 선분으로 주어질 때, 대포를 수직 수평으로 발사한다고 한다.
대포는 직선에 있는 모든 배를 뚫는다고 할 때, 발포된 대포가 부순 가장 무거운 배를 출력하는 문제이다.

얼핏보면 선분의 기울기를 이용하여 대포에 맞는지 안맞는지를 확인해야 하는 문제로 보인다.
하지만 대포가 수직, 수평으로 발사되기 때문에 단순히 전함의 x좌표 사이에 있는가, y좌표 사이에 있는가만 확인해주면 된다.

우선 전함을 구조체로 잡고, 그 안에 생존여부, 시작x 시작y, 끝x 끝y, 무게를 담았다.
그리고 쏘아진 대포에 대해 전함전체를 검사하면서 생존해 있다면 전함에 닿는지 안닿는지를 판별해서 무게의 최대값을 잡고, 격침시키게끔 했다.

그렇게 했는데 시간제한이 6초나 됬지만 TLE가 나왔다.
아무래도 대포가 격침되어도 전함 전체를 검사하는것에 문제가 있다고 판단하여
연결리스트를 이용해, 격침된 전함은 리스트에서 제외하도록 구현하였더니 ACCEPT를 받았다.

다른 사람들이 푼 것에 비해 상당히 성능이 좋아서 기분이 좋았다.

소스