https://www.codetree.ai/missions/2/problems/conveyor-belt-triangle/description
알고리즘
- 시뮬레이션
특정한 알고리즘을 요구하지 않는 단순 구현 문제이고 1차원 배열을 한 쪽 방향으로 n칸 만큼 미는 문제이다.
1차원 배열을 한 쪽 방향으로 n칸 만큼 미는 방법은 구현 문제에서 자주 등장하기 때문에 정리해두려고 한다.
문제 해결 과정
한 칸씩만 미는 경우를 생각해보자.
크게 두 가지 방법이 있는데 기존 배열을 활용하는 방법과 새로운 배열을 생성하는 방법이다.
기존 배열을 활용할 때는 다음 두 가지를 기억하자.
- 방향을 반대로 생각한다.
- 첫 값을 기억해둔다.
- n을 최소화 한다.
오른쪽으로 한 칸씩 미는 경우는 다음과 같다.
만약 진행 방향과 동일하게 진행한다면 이미 갱신된 값을 다음 갱신에 사용하기 때문에 제대로 된 결과를 얻을 수 없다.
방향을 반대로 생각해야 한다.
오른쪽으로 한 칸씩 미는 것이 아니라 오른쪽에서부터 한 칸씩 당기는 것이라고 생각해야 한다.
여기서 첫 번째로 진행한 "6"이란 값을 따로 변수에 저장해야 한다.
첫 번째 값이 갱신되고 나면 원래 값을 알아야 하기 때문이다.
그리고 반복을 할 때 % 연산을 사용하여 반복 횟수를 줄일 수 있다.
원소가 6개일 때 3칸씩 미는 경우와 9칸씩 미는 경우는 동일하기 때문이다.
두 번째는 새로운 배열을 생성하는 것이다.
기존 배열을 사용할 때는 다음 두 가지를 기억하자.
- 새로운 배열을 생성한다.
- n을 최소화 한다.
새로운 배열을 생성할 때는 복잡하게 생각할 필요가 없다.
그냥 새로운 배열을 생성해서 넣어주면 된다.
새로운 배열을 생성할 때는 1칸이 아닌 n칸을 옮겨야 할 때 반복문으로 여러 번 할 필요 없이 한 번의 순회만으로 n칸을 옮길 수 있다.
최종 코드
import sys
input = sys.stdin.readline
n, t = map(int, input().split())
t %= n*3
arr = []
for _ in range(3):
arr += list(map(int, input().split()))
new_arr = [0 for _ in range(len(arr))]
# 마지막 값 저장
temp = arr[-1]
for i in range(n*3 - 1, -1, -1):
new_arr[i] = arr[i-t]
for i in new_arr[:n]:
print(i, end = ' ')
print()
for i in new_arr[n:2*n]:
print(i, end = ' ')
print()
for i in new_arr[2*n:3*n]:
print(i, end = ' ')
파이썬은 리스트의 인덱스에 음수를 사용하면 뒤에서부터 접근을 할 수 있어서 이러한 문제를 해결할 때 인덱스를 크게 고려하지 않아도 된다.
'백준 알고리즘' 카테고리의 다른 글
[CodeTree] 십자 모양 폭발 (중력) (0) | 2024.08.24 |
---|---|
[CodeTree] 격자 칠하기 2 (0) | 2024.08.18 |
[CodeTree] 우리는 하나 (0) | 2024.08.17 |
[백준 16500][파이썬] 문자열 판별 (dfs) (0) | 2023.07.06 |
[백준 1080, 2138][파이썬] 행렬, 전구와 스위치 (그리디 알고리즘) (0) | 2023.06.30 |
댓글