JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

코딩테스트 연습

1. 개미

  • 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각하자. 각각의 개미의 위치는 x좌표로 표시되며, 좌표값은 0보다 크고 L보다 작은 값으로 표현된다.

  • 각각의 개미는 왼쪽, 혹은 오른쪽으로 움직이고 있다. 모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다. 개미들이 움직이는 도중에 서로 부딪히는 경우가 생길 수도 있다. 두 마리의 개미가 서로 부딪혔을 때, 두 마리의 개미는 모두 즉시 방향을 바꾸어 다시 움직이게 된다.

  • 개미들이 이동하다가 0인 위치나 L인 위치에 도달하게 되면, 그 개미는 막대기 아래로 떨어지게 된다. 개미들의 초기상태가 주어졌을 때, 가장 마지막에 떨어지는 개미와 그 개미가 떨어지는 시각을 알아내는 프로그램을 작성하시오.

입력

  • 첫째 줄에 두 정수 N, L이 주어진다.
  • 다음 N개의 줄에는 각 개미의 초기 위치가 주어진다.
  • 초기 위치가 양수로 주어지는 경우는 그 값이 그 개미의 위치가 되며, 그 개미는 오른쪽으로 움직이고 있다.
  • 초기 위치가 음수로 주어지는 경우에는 그 절댓값이 그 개미의 위치가 되며, 그 개미는 왼쪽으로 움직이고 있다.
  • 예를 들어 3이 주어지는 경우에는 3인 위치에서 오른쪽으로 움직이고 있고, -7인 경우에는 7인 위치에서 왼쪽으로 움직이고 있다.

출력

  • 첫째 줄에 두 정수 i, t를 출력한다.
  • i는 가장 마지막에 떨어지는 개미의 번호이다.
  • 개미의 번호는 입력에서 주어지는 순서대로 1, 2, …, N이다.
  • t는 가장 마지막에 떨어지는 개미가 바닥에 떨어지는 시간이다.
  • 가장 마지막에 떨어지는 개미가 여러 마리인 경우는 없다고 가정한다.

풀이


# your code goes here
 
import sys
 
# 첫째 줄에 두 정수 N, L이 주어진다.
# N = 개미 수, L = 막대의 길이
# 좌표는 0~L
 
N,L = list(map(int,sys.stdin.readline().split()))
 
# 개미들의 위치를 저장하는 리스트
vector = []
 
# 개미들의 순서를 저장하는 리스트
order = [x for x in range(1,N+1)]
 
# 다음 N개의 줄에는 각 개미의 초기 위치가 주어진다.
# 초기 위치가 양수로 주어지는 경우는 그 값이 그 개미의 위치가 되며, 그 개미는 오른쪽으로 움직이고 있다.
# 초기 위치가 음수로 주어지는 경우에는 그 절댓값이 그 개미의 위치가 되며, 그 개미는 왼쪽으로 움직이고 있다.
for _ in range(0,N):
	ant_position = int(sys.stdin.readline())
	if vector == []:
		vector.append(ant_position)
	elif vector != []:
		vector.append(ant_position)
		# 절댓값을 기준으로 개미들의 위치를 정렬한다.
 
 
 
for i in range(0,len(vector)):
	for k in range(0,len(vector)):
		if abs(vector[i]) < abs(vector[k]):
			tmp = vector[i]
			tmp2 = order[i]
			vector[i] = vector[k]
			order[i] = order[k]
			vector[k] = tmp
			order[k] = tmp2
 
 
# 모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다.
# 오른쪽으로 움직이는 개미(양수)의 경우, 매 초마다 오른쪽으로 이동하여 L에 가까워진다.
# 왼쪽으로 움직이는 개미(음수)의 경우, 매 초마다 왼쪽으로 이동하여 0에 가까워진다.
# 즉, 모든 개미의 이동은 +1하는것으로 축약 가능하다.(양수는 절댓값이 커지고, 음수는 절댓값이 작아진다.)
 
 
time = 0
final = 0
 
# 모든 개미가 떨어질때까지, 시간을 측정한다.
while(vector != []):
	time += 1
	vector = [x+1 for x in vector]
 
	# 막대 밖으로 떨어짐
 
	if vector[0] == 0:
		del vector[0]
		del order[0]
	if vector[len(vector)-1] == 7:
		del vector[len(vector)-1]
		del order[0]
 
	# 절대값 순으로 정렬
	for i in range(0,len(vector)):	
		for k in range(0,len(vector)):
			if abs(vector[i]) < abs(vector[k]):
				tmp = vector[i]
				tmp2 = order[i]
				vector[i] = vector[k]
				order[i] = order[k]
				vector[k] = tmp
				order[k] = tmp2
 
	# 개미가 두마리 이상일때, 충돌하여 반대방향으로 가는 연산
	for i in range(0,len(vector)-1):
		if abs(vector[i]) == abs(vector[i+1]):
			vector[i] *= -1
			vector[i+1] *= -1
 
 
	# 개미가 한마리 남았을때, 해당 개미의 번호를 기록
	else:
		final = order[0]

채점 결과

  • 오답

고찰

  • 오답 원인의 분석을 위해 print문으로 하나하나 조사해본 결과, 충돌에 대한 개념을 잘못 잡고있었음이 확인되었다.

    • 내 풀이에서 충돌의 정의는 ‘같은 지점에 두 개미가 모이는 경우’만 정의했었다.
    • 하지만, 가짜 예제를 넣고 돌려보는 과정에서는 ‘서로 지나쳐가는 경우’ 역시 존재했고, 이부분에 대한 처리를 진행하지 않아 오답이 나온것으로 추측되었다.

  • 매일 solved.ac기준 레벨을 한단계씩 올려나가는 식으로 문제 풀이를 진행했는데, 3월 7일에 해결한 ‘해밍 수열’ 문제가 골드5 레벨인것과 이번 문제가 골드4 레벨인것을 감안할때, 당분간은 골드5의 문제를 풀며 실력을 늘려야 할 것으로 보인다.

You May Also Enjoy