문제링크
https://www.acmicpc.net/problem/20055
코드 제출 기록 (메모리 및 시간)
제출 날짜
@4/15/2021
메모리
123444 KB
시간
1284 ms
메모
•
삼성 SW 역량 테스트 기출 문제
•
분명히 실버 문제인데... 컨베이어 벨트 돌아가는 방향 & 로봇의 이동방향을 동시에 생각하다보면 생각보다.. 복잡한 문제 ㅠㅠ
문제풀이
1. 컨베이어 벨트
아래줄, 윗줄을 가진 컨베이어벨트를 하나의 리스트로 생각하였다. 즉, 2N개의 칸을 가지고 있는 하나의 리스트로 입력을 받아 저장하고 있었다.
•
문제를 풀기위해서는 컨베이어벨트를 아래와 같이 오른쪽으로 한칸씩 움직여줘야 한다.
•
하지만 매번 반복문을 사용하여 배열을 돌리는 일은 너무 시간이 많이 드는 일이라
올라가는 위치(up_idx) 와 내려가는 위치(down_idx)를 인덱스로 가지고 있어 그 수를 변경해주는 과정으로 대신했다
2. 박스 로봇
로봇은 컨베이어벨트 한칸에 하나의 로봇만이 올라갈 수 있고 내구도(belt배열) 가 적어도 1이어야 로봇을 올릴 수 있다.
•
첫 시도
비어있는 robot 배열을 만들어 컨베이어 벨트위에 로봇이 올라갈 때마다 robot에 컨베이어벨트의 인덱스를 append하는 과정으로 구현
→ 먼저 올라간 로봇부터 순서대로 오른쪽으로 이동 시키는 과정에서 문제가 발생
•
두번째 시도
2N 칸을 가지고 있는 배열을 0으로 초기화한 후 로봇이 올라간 컨베이어 벨트의 인덱스와 같은 인덱스를 가지는 robot 배열의 인덱스를 1로 변경시켜준다.
즉, 로봇이 x 위치로 이동하면→ robot[x] = 1
로봇이 올라가는 위치에 올라가면 → robot[up_idx] = 1
로봇이 내려가는 위치에서 내려가면 → robot[down_idx] = 0
3. 단계 구현
•
문제에 주어진 하나의 단계 순서
1.
벨트가 한 칸 회전한다.(오른쪽)
벨트가 오른쪽으로 한칸씩 움직이게 되면 아래의 그림과 같이 각 자리의 인덱스가 -1씩 줄어들게 된다.
하지만 그렇다고
up_idx -= 1
down_idx -= 1
Python
복사
위와 같이 구현하게 된다면 0→5로 바뀌는 과정에서 오류가 발생하게 된다.
따라서, 아래의 코드와 같이 삼항연산자를 사용하여 idx == 0 이라면 컨베이어벨트의 가장 마지막 인덱스인 2*N - 1 이 되도록 구현해야한다.
up_idx = (2 * N - 1) if (up_idx == 0) else (up_idx - 1)
down_idx = (2 * N - 1) if (down_idx == 0) else (down_idx - 1)
Python
복사
python의 삼항연산자( true_value ) if ( condition ) else ( false_value )
내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다 라는 조건을 만족시키기 위해robot[down_idx] = 0
Python
복사
robot[down_idx] 의 원소의 값을 0으로 바꿔주어 해당 위치에 로봇을 내려준다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. (로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.)
가장 먼저 벨트에 올라간 로봇부터, 마지막으로 올라간 로봇까지 순서대로 pos에 저장하여 조건이 맞으면 이동을 하는 과정을 수행해야한다.
•
pos 변수 = down_idx 부터 up_idx 까지의 인덱스 순서대로 저장
단순히 down_idx~ up_idx 까지 반복문을 돌리게 되면 중간에 2→1→0→2N→2N-1 과 같은 순서에서는 오류가 발생하게 된다.
down_idx 부터 up_idx 까지의 원소의 개수는 언제나 N이므로 아래의 과정을 통해 pos 를 계산할 수 있다.
for i in range(N):
pos = down_idx-i if (down_idx-i >= 0) else (2*N + down_idx - i)
Python
복사
•
next 변수 = pos 다음의 인덱스를 저장
pos 가 가장 마지막 원소인 2N-1이라면 next에 0을 저장하도록 삼항연산자를 사용한다.
next = 0 if (pos == (2 * N - 1)) else (pos + 1)
Python
복사
•
로봇에 pos에 존재하고 next 가 비어있고 next의 내구도가 1이상이면 로봇 이동!
for i in range(N):
pos = down_idx-i if (down_idx-i >= 0) else (2*N + down_idx - i)
next = 0 if (pos == (2 * N - 1)) else (pos + 1)
if (robot[pos] == 1) and (robot[next] == 0) and (belt[next] > 0):
belt[next] -= 1
robot[pos] = 0
robot[next] = 1
Python
복사
내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다 라는 조건을 만족시키기 위해robot[down_idx] = 0
Python
복사
robot[down_idx] 의 원소의 값을 0으로 바꿔주어 해당 위치에 로봇을 내려준다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
if (robot[up_idx] == 0) and (belt[up_idx] > 0):
robot[up_idx] = 1
belt[up_idx] -= 1
Python
복사
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
한단계를 수행하는 while 문의 조건을 아래와 같이 지정하여 내구도가 0인 칸의 수가 K개 이상이면 과정을 중단하고록 구현한다.
arr.count(x) → arr 배열에서 x 원소의 개수 while belt.count(0) < K:
Python
복사
Code
•
첫번째 시도 → 마지막 테스트케이스 통과 못함
if __name__ == '__main__':
N, K = map(int, input().split())
belt = list(map(int, input().split()))
robot = []
cnt = 0 # 횟수를 저장할 변수
up_idx = 0 # 올라가는 위치의 인덱스
down_idx = N - 1 # 내려가는 위치의 인덱스
while belt.count(0) < K: # 내구도가 0인 벨트가 K개 이상이면 끝
cnt += 1
# 한칸씩 오른쪽으로 회전
up_idx = (2 * N - 1) if (up_idx == 0) else (up_idx - 1)
down_idx = (2 * N - 1) if (down_idx == 0) else (down_idx - 1)
# 내려가는 칸에 있는 로봇내리기
if down_idx in robot:
robot.remove(down_idx)
# 로봇 오른쪽으로 한칸씩 이동(가능하면)
temp = robot
for pos in temp:
robot.remove(pos)
next = 0 if (pos == (2 * N - 1)) else (pos + 1)
if (next not in robot) and (belt[next] > 0):
belt[next] -= 1
if next != down_idx:
robot.append(next)
else:
robot.append(pos)
# 올라가는 위치에 로봇이 없다면 하나 올려주기
if (up_idx not in robot) and (belt[up_idx] > 0):
robot.append(up_idx)
belt[up_idx] -= 1
print(cnt)
Python
복사
•
두번째 시도
위의 코드와 다른 점 = 빨간색
오른쪽으로 한칸 회전 = 파란색
down_idx부터 up_idx까지의 인덱스를 pos에 저장 = 보라색
if __name__ == '__main__':
N, K = map(int, input().split())
belt = list(map(int, input().split()))
robot = [0 for _ in range(2*N)]
cnt = 0 # 횟수를 저장할 변수
up_idx = 0 # 올라가는 위치의 인덱스
down_idx = N - 1 # 내려가는 위치의 인덱스
while belt.count(0) < K: # 내구도가 0인 벨트가 K개 이상이면 끝
cnt += 1
# 한칸씩 오른쪽으로 회전
up_idx = (2 * N - 1) if (up_idx == 0) else (up_idx - 1)
down_idx = (2 * N - 1) if (down_idx == 0) else (down_idx - 1)
# 내려가는 위치에 있는 로봇내리기
robot[down_idx] = 0
# 로봇 오른쪽으로 한칸씩 이동(가능하면)
for i in range(N):
pos = down_idx-i if (down_idx-i >= 0) else (2*N + down_idx - i)
next = 0 if (pos == (2 * N - 1)) else (pos + 1)
if (robot[pos] == 1) and (robot[next] == 0) and (belt[next] > 0):
belt[next] -= 1
robot[pos] = 0
robot[next] = 1
# 내려가는 위치에 있는 로봇내리기
robot[down_idx] = 0
# 올라가는 위치에 로봇이 없다면 하나 올려주기
if (robot[up_idx] == 0) and (belt[up_idx] > 0):
robot[up_idx] = 1
belt[up_idx] -= 1
print(cnt)
Python
복사
