[코딩인터뷰] 문제 3.3

문제 3.3

	#region Question 3.3
	/*
	* SetOfStacks는 여러 스택으로 구성되며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다.
	* Push()와 Pop()은 스택이 하나인 경우와 동일하게 동작해야 한다.
	* (특정한 하위 스택에 대해서 Pop()을 수행하는 PopAt(int index) 함수를 구현하라.)
	*/
	/// <summary>
	/// 저장할 수 있는 데이터 개수에 제한이 있는 스택이다.ㄴ
	/// </summary>
	/// <typeparam name="T">데이터 타입</typeparam>
	public class LimitedStack<T>
	{
	/// <summary>
	/// 스택에 저장된 데이터
	/// </summary>
	private LinkedList<T> data;
	/// <summary>
	/// 스택에 저장가능한 개수
	/// </summary>
	private int capacity;
	/// <summary>
	/// 저장된 데이터 총량
	/// </summary>
	public int Count
	{
	get { return data.Count; }
	}
	/// <summary>
	/// 저장할 수 있는 최대개수를 지정하고 인스턴스 생성한다.
	/// </summary>
	/// <param name="capacity">저장가능한 개수</param>
	public LimitedStack(int capacity)
	{
	this.data = new LinkedList<T>();
	this.capacity = capacity;
	}
	/// <summary>
	/// 스택에 데이터를 저장한다.
	/// </summary>
	/// <param name="value">저장할 데이터</param>
	public void Push(T value)
	{
	if(data.Count >= capacity)
	{
	throw new InvalidOperationException("Stack is full.");
	}
	data.AddLast(new LinkedListNode<T>(value));
	}
	/// <summary>
	/// 스택에서 데이터 꺼낸다.
	/// </summary>
	/// <returns>마지막으로 저장된 스택 데이터</returns>
	public T Pop()
	{
	if(this.IsEmpty())
	{
	throw new InvalidOperationException("Stack is empty.");
	}
	var value = data.Last.Value;
	data.RemoveLast();
	return value;
	}
	public bool IsEmpty()
	{
	if(data.Last == null || data.First == null)
	{
	return true;
	}
	return false;
	}
	/// <summary>
	/// 일반적인 스택과 달리, 큐처럼 제일 오래된 데이터를 꺼낸다.
	/// </summary>
	/// <returns>스택에서 제일 오래된 데이터</returns>
	public T PopBottom()
	{
	if (this.IsEmpty())
	{
	throw new InvalidOperationException("Stack is empty.");
	}
	var value = data.First.Value;
	data.RemoveFirst();
	return value;
	}
	}
	/// <summary>
	/// 데이터 총량이 제한된 스택에 나누어 데이터를 저장하는 스택이다.
	/// </summary>
	/// <typeparam name="T">스택에 저장될 데이터 타입</typeparam>
	public class SetOfStacks<T>
	{
	private List<LimitedStack<T>> stacks = new List<LimitedStack<T>>();
	/// <summary>
	/// 각 제한된 스택에 가질 수 있는 데이터 총량
	/// </summary>
	public int Capacity { get; }
	public SetOfStacks(int capacity)
	{
	this.Capacity = capacity;
	}
	public LimitedStack<T> GetLastStack()
	{
	if(this.stacks.Count == 0)
	{
	return null;
	}
	else
	{
	return stacks[this.stacks.Count - 1];
	}
	}
	public void Push(T value)
	{
	var last = GetLastStack();
	try
	{
	last.Push(value);
	}
	catch (Exception)
	{
	var stack = new LimitedStack<T>(Capacity);
	stack.Push(value);
	this.stacks.Add(stack);
	}
	}
	public T Pop()
	{
	var last = GetLastStack();
	var value = last.Pop();
	if(last.Count == 0)
	{
	this.stacks.Remove(last);
	}
	return value;
	}
	/// <summary>
	/// 특정 스택에서 최근 데이터를 꺼낸다.
	/// </summary>
	/// <param name="index">특정 스택 번호</param>
	/// <returns>특정 스택에서 꺼낸 데이터</returns>
	public T PopAt(int index)
	{
	if(index < 0 || index >= stacks.Count)
	{
	throw new InvalidOperationException("There is no stack at " + index);
	}
	var value = this.stacks[index].Pop();
	if (this.stacks[index].IsEmpty())
	{
	this.stacks.RemoveAt(index);
	}
	else
	{
	while ((++index) < stacks.Count)
	{
	this.stacks[index - 1].Push(this.stacks[index].PopBottom());
	}
	}
	return value;
	}
	}
	#endregion

view raw Code_Q3_3.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q3_3()
	{
	var setOfstacks = new StackQueue.SetOfStacks<int>(3);
	//stack 0
	setOfstacks.Push(1);
	setOfstacks.Push(2);
	setOfstacks.Push(3);
	//stack 1
	setOfstacks.Push(4);
	setOfstacks.Push(5);
	setOfstacks.Push(6);
	Assert.AreEqual(6, setOfstacks.Pop());
	Assert.AreEqual(5, setOfstacks.Pop());
	Assert.AreEqual(4, setOfstacks.Pop());
	Assert.AreEqual(3, setOfstacks.Pop());
	Assert.AreEqual(2, setOfstacks.Pop());
	Assert.AreEqual(1, setOfstacks.Pop());
	//stack 0
	setOfstacks.Push(1);
	setOfstacks.Push(2);
	setOfstacks.Push(3);
	//stack 1
	setOfstacks.Push(4);
	setOfstacks.Push(5);
	setOfstacks.Push(6);
	Assert.AreEqual(3, setOfstacks.PopAt(0));
	Assert.AreEqual(4, setOfstacks.PopAt(0));
	Assert.AreEqual(5, setOfstacks.PopAt(0));
	}

view raw Test_Q3_3.cs hosted with ❤ by GitHub