문제
항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.
파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.
항승이는 길이가 L인 테이프를 무한개 가지고 있다.
항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.
물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.
난이도
Silver 3
입력 조건
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.
출력 조건
첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.
입력 예시
4 2
1 2 100 101
출력 예시
2처음 짠 코드
n,l = map(int, input().split())
water = list(map(int, input().split()))
count = 0 # 테이프 갯수
water.sort() # 오름차순 정렬
iscount =[True] * len(water) # True이면 아직 막지 않은곳, False이면 막은 곳
for i in range(len(water)):
if iscount[i] == True: # 막지 않은 곳이면
count+=1 # 테이프 한개 추가
iscount[i] = False # 막은 곳으로 변경
for j in range(len(water)-i-1,0,-1): # 현재 위치를 기점으로 가장 먼곳부터 탐색
if water[i+j]-water[i]+1 <= l: # 여러 개를 한번에 막을 수 있으면
for k in range(0,j+1):
iscount[i+k] = False # 현재 위치 ~ 한번에 막을 수 있는 위치까지를 False로 변경
break # 이후 더 탐색하지 않고 for문 종료
print(count)수정 코드
n,l = map(int, input().split())
water = list(map(int, input().split()))
water.sort() # 오름차순 정렬
start = water[0] # 시작 지점
count = 1 # 테이프 갯수
for location in water[1:]:
if location in range(start, start+l): # 현재 위치가 테이프 범위 안에 있으면 넘기기
countinue
else:
start = location
count +=1
print(count)
느낀 점
처음에는 무작정 하나하나 다 탐색하는 방법으로 풀어서 굉장히 비효율적인 코드가 되었다,,
아직 처음이라 그런지 계속 True False 리스트를 만들어서 가능한지 아닌지 여부를 탐색하는 방식으로 짜는걸 좋아하는 것 같다
이 습관을 좀 고치자. 코드를 짜서 정답을 맞추는게 중요한게 아니다. 정답을 맞추더라도 더 효율적인 방식으로 짤 수는 없었는지 항상 고민하고 또 고민해야겠다
이러한 유형의 문제를 풀 때 저렇게 여러 지점을 탐색해야 하는 경우가 꽤 있는데, 이럴때 하나하나 탐색하는것보다 수정한 코드처럼 범위를 지정해주고 한번에 탐색하자
