오른쪽으로 배열 회전하기

배열 arr[]에서 위치 s, t 사이로 1만큼 오른쪽으로 회전시켜보자.

단, arr[t]의 경우, arr[s]로 복사하면 된다.

풀이 순서

  1. i = t : 뒤부터 탐색을 시작하자.
  2. arr[i] = arr[i - 1] : 1 만큼 왼쪽으로 이동.
  3. arr[s] 에 이르선 arr[s - 1] 이 더 이상 없는 문제가 있음.
  4. 사전에 arr[t] 를 last 에 저장하여 arr[s] 에 대입한다.

코드 풀이

void right_rotate(int arr[], int s, int t)
{
    int i, last;
    last = arr[t];
    for (i = t; i > s; i--)
        arr[i] = arr[i - 1];
    arr[s] = last;
}

N 만큼 이동하기

1만큼 이동하는 함수를 k 번 반복하면 되지만 이 방법은 O(n^k), (n은 s , t 사이의 거리)로 느린 문제가 있다.

Python 풀이

def n_right_rotate(array: list, start: int, end: int, rotateTo: int):
    first = array[:start]
    middle = array[start:end+1]
    second = array[end+1:]

    odd = rotateTo % len(middle)
    for _ in range(odd):
        middle = [middle.pop(), *middle]
    return [*first, *middle, *second]


def test_n_right_rotate():
    assert k_right_rotate([1, 2, 3, 4], 1, 3, 4) == [1, 4, 2, 3]

파이써닉하게 slice 문법과 Unpacking Argument Lists*args 기능을 사용하면 무려 O(n) 에 풀 수 있다.

N의 크기가 n 보다 큰 경우에도 나머지 숫자 만큼 반복을 한 덕분에 항상 해당 시간 복잡도로 풀 수 있다.

C 풀이

int n_right_rotate(int arr[], int s, int t, int k)
{
    int i, last[k];
    int move_last = t - k;
    for (i = t; i > move_last; i--)
        last[t - i] = arr[i];
    for (i = t; i > move_last - 1; i--)
        arr[i] = arr[i - k];
    for (i = 0; i < k; i++)
        arr[s + i] = last[k - 1 - i];
    return arr;
}

실행 시간은 n + k 이다.

스택 2개로 큐 구현하기

스택 2개를 활용하여 큐를 구현해보자.

풀이 순서

  1. 큐 객체를 처음 생성할 때 스택 2개 in_stack, out_stack 를 만든다.
  2. 큐에 값이 들어갈때는 in_stack의 끝에 넣는다.
  3. 큐에 값이 나갈때는 모든 in_stack의 값을 out_stack 로 옮겨 stack2 을 뺴내면 된다.

in_stack에서 out_stack으로 값이 옮겨지는 과정을 활용하면 자연스럽게 큐가 구현된다.

풀이

Python 풀이

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, value):
		self.elements.append(value)

	def pop(self):
		if self.size() > 0: # 우선순위 pop > None
			return self.elements.pop()
		else:
			return None

	def size(self):
		return len(self.elements)

class Queue:
	def __init__(self):
		self.inbox = Stack()
		self.outbox = Stack()

	def enqueue(self, value):
		self.inbox.push(value)

	def dequeue(self):
		if self.outbox.size() is 0:
			while not self.inbox.size() is 0:
				pop = self.inbox.pop()
				self.outbox.push(pop)
		return self.outbox.pop()