LeetCode 155. MinStack
처음에 생각한 구현은 Stack에 최소값만 담는 방식 이었습니다.... 그리하여,...
input
["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]expected
[null,null,null,null,null,null,-1024,null,-1024,null,512]-
512 도 담길 수 있다.
- 이 때는, 문제 해결만 하자 생각으로 논리적으로 다시 확인 않고 일단 풀었습니다.
-
작은 값만 stack에 담으면 왜 안 될까?
- 작은 값만 minStack에 담고, peek() 비교 결과 동일한 값이 stack에서 pop 되면 minStack도 pop 되게 했었다.
- 결국 작은 값이 제거된 후에는 stack은 값이 있지만, minStack은 먼저 비게 되어 문제에서는 의도하지 않은 예외 케이스가 발생 합니다.
- 여기서 예외케이스라고 생각하면서 empty 의 경우를 null 로 반환하는 등으로 생각하면 문제를.... 못 풀 수 있습니다. 😂
-
0 1 2 3 stack 512 -1024 -1024 512 min -1024 -1024
-
새로 넣을 때, 기존 값과 비교해서 작은 값을 계속 넣습니다.
-
0 1 2 3 stack 512 -1024 -1024 512 min 512 -1024 -1024 -1024
-
- 시간복잡도 O(1) 이니 stack을 2개 대신 다르게 한다면?
- 클래스 만들어서 하면, 실수도 많고, 코테나 인터뷰 때는 배열이 덜 복잡하고 편리하다...
class MinStack {
Stack<Element> stack = new Stack<>();
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if(stack.isEmpty()) {
stack.push(Element.of(val, val));
return;
}
stack.push(Element.of(val, stack.peek().getMinVal(val)));
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().getValue();
}
public int getMin() {
return stack.peek().getMinValue();
}
private Element toArr(int stack, int minStack) {
return Element.of(stack, minStack);
}
static class Element {
private int stackVal;
private int minVal;
private Element(int stackVal, int minVal){
this.stackVal = stackVal;
this.minVal = minVal;
}
public static Element of(int stackVal, int minVal){
return new Element(stackVal, minVal);
}
public int getMinVal(int newVal){
return Math.min(this.minVal, newVal);
}
public int getValue(){
return this.stackVal;
}
public int getMinValue(){
return this.minVal;
}
}
}처음에 생각한 구현은 Stack에 최소값만 담는 방식 이었습니다.
➜ 단순한 논리적 오류 : minStack 이 비었을 때는 stack 값 동일하게 넣어주고, 최소값을 유지하면 된다.
그래서
- minStak.isEmpty 이거나 minStack <= val 이면 push(val)
하지만... 오류 😮💨
- 초보적인 실수였습니다.
- IDE로 옮겨서 확인하니 비교값이 true 여야 하는데 false 가 나왔습니다.
- 반환 타입은 정의한 타입
Stack<Integer> minStack = new Stack<>();으로 Integer로 객체간 비교해야 했습니다.
- 반환 타입은 정의한 타입
- 사실, Wrapper 클래스 primitive로 자동 형변환 해주니까요. 그냥 썼는데, Stack의 peek() 반환타입으로
==는 안 되네요 ?
@Test
void primitiveAndWrapper() {
Integer number = 1;
int toInt = number;
int intNumber = 1;
System.out.println(toInt);
System.out.println(toInt == number);
System.out.println(intNumber == number);
}- 혹시나 싶어 반환 타입 확인하러 가봤다가 제네릭을 ... primitive는 안 되겠네요.
- 반환 시점에 비교시 자동 형변환은 안 되나 봐요.
public class Stack<E> extends Vector<E> {
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
}구현 코드는 GitHub
Stack
그렇게 Stack을 보게 되었 습니다. ㅎㅎ
Vector 클래스를 상속 받고 있습니다.
Queue (interface) 와 다르게 Stack은 구현 클래스로,
Vector 에는 indexOf() 위의 elementAt() 과 같이 자료구조 관련 기능들이 있었고,
Stack은 Stack으로서의 기능들을(LIFO 형태의 자료구조 방식)담당하고 있었습니다.
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
protected Object[] elementData;
/**
* The number of valid components in this {@code Vector} object.
* Components {@code elementData[0]} through
* {@code elementData[elementCount-1]} are the actual items.
*
* @serial
*/
protected int elementCount;
/**
* The amount by which the capacity of the vector is automatically
* incremented when its size becomes greater than its capacity. If
* the capacity increment is less than or equal to zero, the capacity
* of the vector is doubled each time it needs to grow.
*
* @serial
*/
protected int capacityIncrement;
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
public synchronized E firstElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return elementData(0);
}그러다가 제 의식은 제네릭에 ...
Object[] elementData;가 어떻게 반환은E로 할 수 있지?
Generic 타입 배열은 생성할 수 없다.
Java에서 배열은 공변(covariant)로 만든 이유는 무엇인가? 🙂 감사합니다.
저는 자바의 정석부터 읽어 봤습니다.
제네릭스가 제한되는 상황이 크게 2가지가 있습니다.
- static 멤버는 인스턴스 변수를 참조 할 수 없다.
- 제네릭 타입의 배열을 생성하는 것도 허용되지 않는다.
사실 저는 외우진 않고, IDE에서 알려주면 '아, 맞다맞다' 하면서 static 등 고쳤습니다.
(실수도 많이 하면 빨리 고칠 수 있고, 그게 손이 동작하기 전에 고치면 아는 듯이 보이고... 말로 표현하지 못하는 어떤 Dreams Come True )
이 참에 정리라도 해보자 싶었습니다.
먼저 제 코드의 잘못을 IDE를 통해서 알 수 있었습니다. 컴파일 에러!
제네릭은 컴파일 시 타입 체크와 형변환을 통해 타입 안정성과 편리성을 제공
class Stack<T> {
T[] elemendts;
T[] extendsArray() {
T[] arr = new T[elements.length * 2];
return arr;
}
// Vector 클래스 예시
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
public synchronized E firstElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return elementData(0);
}
}-
위에서
T[] elemendts;는 괜찮지만,new T[elements.length * 2];에서 컴파일 에러 발생합니다.- new 연산자는 컴파일 시점에 타입을 알아야 하기 때문입니다.
- 위에 참고한 링크의 내용에서
Object[] objArr = new Integer[10];는 컴파일 에러가 발생하지 않습니다. 컴파일하면서 Integer로 형변환 됐겠지 싶은데요.- 다만,
objArr[1] = "test";처럼 컴파일 과정에서는 다른 타입으로 대입도 괜찮지만, 실행 하면 에러 발생 합니다. - 타입 안정성 X
- 다만,
Object[] objArr = new Integer[10]; objArr[0] = 1; objArr[1] = "test"; // 실행 후 ArrayStoreException System.out.println(objArr[0]); System.out.println(objArr[1]); -
Vector 클래스의
return elementData(0);은 Obejct 타입이고 메서드는 E가 반환타입 입니다.- 컴파일시 E는 Vector 의 타입에 맞춰 변경되고, Object 반환하는 elementData(0)의 해당 타입으로 형변환 해줍니다.
정리
제네릭은 컴파일을 통해 형변환을 대신 해주고, 그러기 위해서 타입 체크를 합니다.
다만, 배열은 제네릭 타입의 선언은 되지만 new 연산자로 생성은 불가합니다.
1. new 로 Object배열로 생성해주고 형변환을 일일이 선언해준다면?
- ClassCastException 에러 발생 (그러지 말래요...)
- 심지어 반환을 arr 하는데 반환 타입이 T[] 가 아니어도 컴파일 에러가 안 떠요.
( 물론 T[] 로 변경해도 동일 에러 발생 합니다.)
public class TestGeneric<T> {
private T[] arr;
public TestGeneric() {
this.arr = (T[])new Object[10];
}
public T testGeneric() {
// arr = (T[])new Integer[10];
// arr[0] = (T)"문자열 넣기";
arr = (T[])new Object[10];
return (T)arr;
}
@Test
void testGenericArr() {
TestGeneric<String> stringTest = new TestGeneric<>();
String s = stringTest.testGeneric();
System.out.println(s);
}
}- ClassDefiner 클래스에서 unsafe로 반환
static Class<?> defineClass(String name, byte[] bytes, int off, int len,
final ClassLoader parentClassLoader)
{
ClassLoader newLoader = AccessController.doPrivileged(
new PrivilegedAction<ClassLoader>() {
public ClassLoader run() {
return new DelegatingClassLoader(parentClassLoader);
}
});
return unsafe.defineClass(name, bytes, off, len, newLoader, null);
}- unsafe 여서 끝나는 줄 알았는데 리플렉션(Proxy - newProxyInstance()) 통해서
T inst = (T) ca.newInstance(initargs);가 진행 됩니다.- 형변환 까지 가는 거 같은 데, 변환하면서 에러가 하는 거 같아요.
- 이게 컴파일과 실행의 에러 차이? ( 저는 여기까지인 것 같습니다.... 저는 오늘도 결국 몰라요로 마무리를.. 😑 )
@CallerSensitive
@ForceInline // to ensure Reflection.getCallerClass optimization
public T newInstance(Object ... initargs)
throws InstantiationException, IllegalAccessException,
IllegalArgumentException, InvocationTargetException
{
if (!override) {
Class<?> caller = Reflection.getCallerClass();
checkAccess(caller, clazz, clazz, modifiers);
}
if ((clazz.getModifiers() & Modifier.ENUM) != 0)
throw new IllegalArgumentException("Cannot reflectively create enum objects");
ConstructorAccessor ca = constructorAccessor; // read volatile
if (ca == null) {
ca = acquireConstructorAccessor();
}
@SuppressWarnings("unchecked")
T inst = (T) ca.newInstance(initargs);
return inst;
}그러면 Vector 클래스에서 elementData 의 초기화는?
- 멤버 변수로 배열의 타입을 제네릭이 아닌 Obejct로 해야 초기화도 가능
protected Object[] elementData;
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}2. 코드 예시 하나더!
- 컴파일 에러는 없지만, 실행시 ParameterResolutionException 발생
public class TestGeneric<T> {
private Object arr;
public TestGeneric(T element) {
this.arr = element;
}
public T toTestGeneric() {
return (T)arr;
}
@Test
void testGenericArr() {
Integer[] expected = {1, 2, 3, 4};
TestGeneric<Integer[]> arrTest = new TestGeneric(expected);
Integer[] actual = arrTest.toTestGeneric();
}
}
그리고 Vector 가 상속받은 RandomAccess 인터페이스
sally의 법칙을 따르는 bug Duck