https://leetcode.com/problems/add-two-numbers/

이문제 풀다가 간단한 문제고, 문제 풀이도 잘 했는데 뭐가 문제지 했었다. 

결론부터 말하자면 LeetCode에서 코드를 제출할 때 static 변수를 사용하지 말자. 사용하더라도 한번의 코드가 끝나면 static 변수를 초기화해주자

public class Solution{
	static int carry = 0;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	// carry에 따라 결과값 변화
    }
}

대충 요약하면 이런 상황이었는데,

이상하게 testcase에 해당 wrong answer이 나는 걸 그대로 테스트하면 accept 되는데, 실제로 submit을 해서 넣어 돌리면 wrong answer이 떳다. 이상하게 내 output에 이 올바르지 않은 값이었다.

그래서 엥,, 이상하다 하고 leet code 측에 메일을 보냈었는데, 문뜩 생각이 들어서 확인을 해보니, test case를 1000개를 실행해 주었고, 내가 전역변수로 설정한 carry값이 다음 test case 실행에 영향을 미췄더라면? 이라는 가설을 내고 확인해보았더니 맞았다.

리트코드에서 전역변수를 사용할 때는 꼭 전역변수를 초기화해주자. 초기화하지 않은 전역변수 값이 submition시 test case에 영향을 줄 수 있다.

알고리즘을 역시 안풀어보니까 이런거에도 끙끙 대는구나 싶다... 다시 리트코드 풀러가야지 총총

https://leetcode.com/problems/add-two-numbers/

I was solving this problem and it was a simple one — I thought my solution was correct, so I couldn't figure out what was going wrong. 

Long story short: when submitting code on LeetCode, don't use static variables. If you do use them, make sure to reset the static variables after each run.

public class Solution{
	static int carry = 0;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	// carry에 따라 결과값 변화
    }
}

To summarize, here's what was going on:

Strangely, when I tested the exact wrong answer test case myself, it would pass just fine. But when I actually submitted the code, it came back as a wrong answer. Somehow my output had this incorrect value.

So I was like, huh, that's weird, and I even sent an email to the LeetCode team. But then it suddenly hit me — I checked and found out that they run around 1,000 test cases, and I hypothesized: what if the carry value I declared as a global variable was carrying over and affecting the next test case? I tested that theory, and sure enough, that was exactly the problem.

When using global variables on LeetCode, always make sure to reset them. Uninitialized global variable values can affect other test cases during submission.

I guess this is what happens when you don't practice algorithms regularly — you end up struggling with stuff like this... Time to get back to grinding LeetCode problems. Off I go~

1. 자바의 제네릭과 로타입 (Java Generics and Raw Type)

public class<T> Example{
	private T member;
}

위와 같이 클래스 및 인터페이스 선언에 타입 매개변수 T 가 사용되면 제네릭 클래스, 제네릭 인터페이스라고 말하는데, 이때 사용된 이 클래스 Example<T> 를 제네릭타입이라고 이야기한다.

제네릭을 사용하면 로타입이라는 개념이 나오는데, 로타입은 제네릭 타입에서 타입 매개변수를 전혀 사용하지 않았을 때를 의미한다 즉, 위 제네릭 타입Example<T>를 Example 로만 선언하여 사용했을 경우를 말한다.

public class Example<T> {
    private T member;

    public Example(T member) {
        this.member = member;
    }

    public static void main(String[] args) {
        Example<Integer> parameterType = new Example<>(1);
        Integer parameterTypeMember = parameterType.member;
        System.out.println(parameterTypeMember);

        Example rawType = new Example(1);
        Object rawTypeMember = rawType.member;
        System.out.println(rawTypeMember);
    }
}

위 코드는 제네릭 파라미터 타입과 로타입을 사용한 경우이다. 하지만 로타입은 사용하지말자.

제네릭의 장점은 컴파일 타임에 타입에 대한 안정성을 보장받을 수 있다는 점이다. 제네릭 타입으로 선언한 변수는 컴파일 타임에 타입 체크를 하기 때문에 런타임에서 ClassCastException과 같은 UncheckedException을 보장 받을 수 있다.

반면 아래와 같이 로타입으로 사용될 경우에는 제네릭을 사용했을 때의 안정성과 표현력이라는 장점을 발휘할 수 없기 때문에, IDE 에서도 "Raw use of parameterized class 'Example' " 라는 경고를 주는 것을 볼 수 있다.

그럼 로타입이 나오게 된 이유는 무엇일까? 로타입이 나오게 된 이유는 제네릭의 특징인 소거와 관련이 있다.

제네릭은 JDK5 에서 도입이되었다. 버그를 줄이기 위한 목적과, 다른 추상화된 타입에 대한 레이어를 추가하기 위해서이다.
이에 따라 제네릭을 도입한 JDK5는 기존의 코드를 모두 수용하면서 제네릭을 사용하는 새로운 코드와의 호환성을 유지 했어야 했다. 따라서 코드의 호환성 때문에 : 로타입의 지원 + 제네릭을 구현할 때 소거(erasure)하는 방식을 이용하였다.

2. 제네릭의 타입소거 (Generics Type Erasure)

소거란 원소 타입을 컴파일 타임에만 검사하고 런타임에는 해당 타입 정보를 알 수 없는 것이다. 다른 말로는 컴파일 타임에만 타입에 대한 제약 조건을 적용하고, 런타임에는 타입에 대한 정보를 소거하는 프로세스이다.

List<Object> ol = new ArrayList<Long>(); // 컴파일 에러
ol.add("타입이 달라 넣을 수 없다");

다음과 같은 상황에서 컴파일시에 타입 오류를 바로 알 수 있다 (리스트도 제네릭 타입으로 구현되어있기 때문에)

Java 컴파일러는 타입소거를 아래와 같이 적용한다.

• 제네릭 타입( Example<T>) 에서는 해당하는 타입 파라미터 (T) 나 Object로 변경해준다. 
  Object로 변경하는 경우는 unbounded 된 경우를 뜻하며, 이는 <E extends Comparable<E>>와 같이 bound를 해주지 않은 경우를 의미한다.
  따라서 이 소거 규칙에 대한 바이트코드는 제네릭을 적용할 수 있는 일반 클래스, 인터페이스, 메서드에만 해당된다.
• 타입 안정성 보존을 위해 필요하다면 type casting을 넣어준다.
• 확장된 제네릭 타입에서 다형성을 보존하기 위해 bridege method를 생성한다.

public static <E> boolean containsElement(E[] elements, E element) {
	for (E e : elements) {
		if (e.equals(element)) {
			return true;
		}
	}
	return false;
}

실제로 이렇게 선언되어있는 제네릭 메서드의 경우 선언 방식에 따라 컴파일러가 타입파라미터 E를 변경한다.

public static boolean containsElement(Object[] elements, Object element) {
	for (Object e : elements) {
		if (e.equals(element)) {
			return true;
		}
	}
	return false;
}

컴파일러는 첫번째 규칙에 따라 타입 파라미터 E가 bound하게 선언되어있지 않기 때문에 타입 파라미터 E를 Integer로 우선적으로 바꾼다.

이때 만약 프로그래머가 continasElement(Integer[], Integer) 형식으로 해당 메서드를  사용했다면, 컴파일러 내부에서 두번재 규칙에 따라 타입 안정성 보존을 위해 Object -> Integer로의 타입 캐스트 코드를 넣어주어 제네릭의 타입 안정성을 보장해주는 것이다. 

반면 로타입일 경우에는, 타입 파라미터가 정해져있지 않아. Object로 변환한 것에서 끝난다.

public static <E extends Comparable<E>> void containsElement(E[] elements) {
	for (E e : elements) {
		System.out.println("%s", e);
	}
}

public static void containsElement(Comparable[] elements) {
	for (Comparable e : elements) {
		System.out.println("%s", e);
	}
}

추가로 세번째 규칙에 대해서 언급하자면 java compiler는 제네릭의 타입안정성을 위해 Bridge Method도 만들어낼 수있다. Bridge Method는 java 컴파일러가 컴파일 할 때 메서드 시그니처가 조금 다르거나 애매할 경우에대비하여 작성된 메서드이다. 이 경우는 파리미터화된 클래스나 인터페이스를 확장한 클래스를 컴파일 할 때 생길 수 있다.

public class IntegerStack extends Stack<Integer> {
    public Integer push(Integer value) {
        super.push(value);
        return value;
    }
}

Java 컴파일러는 다형성을 제네릭 타입 소거에서도 지키기 위해, IntegerStack의 push(Integer) 메서드와 Stack의 push(Object) 메서드 시그니처 사이에 불일치가 없어야 했다. 따라서 컴파일러는 런타임에 해당 제네릭 타입의 타입소거를 위한 Bridge 메서드를 만드는데 아래와같은 방식으로 만든다.

public class IntegerStack extends Stack {
    // Bridge method generated by the compiler
     
    public Integer push(Object value) {
        return push((Integer)value);
    }
 
    public Integer push(Integer value) {
        return super.push(value);
    }
}

즉 extends Stack<Integer> -> Stack 으로  변경한 것을 볼 수 있으며, push에 parameter를 Object가 아닌 Integer로 맞추기 위한 도우미 메서드가 늘어났다는 것을 알 수 있다. 결과적으로 Stack 클래스의 push method는 타입소거를 진행한 후에, IntegerStack 클래스의 원본 push 방법을 사용하게 한다.

3. 제네릭에서는 리스트를 사용하자

실체화 불가 타입(Non-Reifiable Type)에 대한 설명이 있다 runtime에 타입 정보를 갖고있지 않고, compile-time에 타입 소거가 되는 타입을 의미한다고 한다. 이에 반대하는 개념으로는 실체화(reifiable)가 있다. 이는 타입 정보를 런타임에 완벽하게 사용할 수 있는 유형으로, 소거와는 반대 개념이다. 

실체화 불가 타입의 대표적인 예시로는 List<String> List<Number> 와 같은 리스트가 있고, 실체화 타입의 대표적인 예시로는 String[], Number[] 와 같은 배열이 있다.

이펙티브 자바에서는 타입소거라는 특성이 있는 제네릭은 실체화 불가 타입인 List와 함께 사용하기를 권장한다. Array 에서는 런타임에 타입정보를 갖고있는데, 제네릭을 사용하면 타입이 소거되기 때문에 해당 제네릭 변수에 대한 정보를 런타임에 갖고있지 않기 때문이다.

사실 이 부분은 이펙티브 자바를 읽으면서 스터디에서 했던 제네릭과 관련한 이야기를 예시로 이야기 하려한다.

관련 이슈 : https://github.com/Java-Bom/ReadingRecord/issues/88

static <T> T[] pickTwo(T a, T b, T c) {
  switch (ThreadLocalRandom.current().nextInt(3)) {
    case 0:
      return toArray(a, b);
    case 1:
      return toArray(b, c);
    case 2:
      return toArray(a, c);
  }
  throw new AssertionError();
}

static <T> T[] toArray(T... args) {
  return args;
}

public static void main(String[] args) {
  String[] strings = pickTwo("좋은", "빠른", "저렴한");  
}

위 코드에서 ClassCastException이 터진다. 반면 아래와 같이 pickTwo 메서드를 사용했을 때는 ClassCastException이 터지지 않는다. 왜그럴까? 

static <T> List<T> pickTwoList(T a, T b, T c) {
  switch (ThreadLocalRandom.current().nextInt(3)) {
    case 0:
      return Arrays.asList(a, b);
    case 1:
      return Arrays.asList(b, c);
    case 2:
      return Arrays.asList(a, c);
  }
  throw new AssertionError();
}

List<String> strings = pickTwoList("좋은", "빠른", "저렴한");

문제를 좀 더 단순히 해보자.

static <T> List<T> pickList(T a) {
        return Arrays.asList(a);
    }

    static <T> T[] toArray(T... args) {
        return args;
    }

    static <T> T[] pickArray(T a) {
        return toArray(a);
    }

    public static void main(String[] args) {
        List<String> stringList = pickList("자바봄");
        String[] stringArray = pickArray("자바봄");
   }
}

위 코드에서 pickList를 지나 pickArray를 실행하면 runtimeException이 터지는 것을 볼 수 있다. 내용은 [Ljava.lang.Object; cannot be cast to [Ljava.lang.String; 이다 무엇이 문제일까?

정답은 Array와 List의 실체화에 있었다. 

코드를 이해해보자. 위에서는 제네릭 타입추론이 2 depth가 들어간다. pickArray에서 타입 매개변수 T가 String과 대응하여 들어가기 때문에 pickArray(String) toArray(String...) 이 들어갈 것으로 예상한다. 하지만 실제 런타임에 확인해보면 pickArray(String),  toArray(Object...)가 들어간다. 그 이유는 위에서 제네릭 타입추론을 이야기할 때 우선적으로 bounded가 아닌 매개변수일경우 컴파일러가 Object로 대체한다는 이야기와 대응된다. pickArray에서는 main에 있는 String 타입으로 타입추론이 가능했으나 toArray는 제네릭 타입을 바라보고 있으므로 타입추론을 Object로 하여 런타임에 타입정보를 갖고있게 된다.

따라서 pickArray는 String[] 으로 타입캐스팅을 준비하였으나, 위에서 말한 것처럼 런타임에 toArray가 갖고있는 타입은 Object[] 이므로 런타임에 (String[]) Object[] 와 같은 형식으로 강제적으로 타입캐스팅을 하다가 ClassCastException이 발생한다. (String 배열은, Object 배열의 하위 타입이 아니기 때문에 Casting이 되지 않는다.)

반면에 pickList를 호출할때는 컴파일이 성공한다. 이 이유는 List가 실체화 불가타입이었기 때문이다. 컴파일 타임에 캐스팅할 정보가 이미 결정이되고, 런타임때에는 제네릭의 소거라는 특성 때문에 Java 컴파일러가 타입에 맞는 캐스팅 방식을 올바르게 추가해줘서 캐스팅 에러가 나지 않는다.

정리하자면, 리스트 + 제네릭은 컴파일 타임에 결정된 캐스팅 정보가 올바르기 때문에 통과가 된다. 제네릭의 장점인 컴파일 타임에 타입이 안맞는 것을 체크해주는 걸 List에서도 수행하기 때문이다. 반면 배열 같은 경우엔 타입 캐스팅을 런타임에 결정하기 때문에 문제가 생긴 것이다. 

조금 길었지만 사실 결론은 간단하다. 제네릭은 타입소거라는 특징으로 컴파일러가 컴파일 타임에 타입을 추론할 수 있으며, 이런 타입 추론 기능을 강력하게 사용하기 위해서는 런타임에 타입을 추론하는 Array 대신에 컴파일타임에 타임을 추론하는 List를 함께 사용해야 안정성을 보장 할 수 있다는 것이다.

참고 글

https://www.baeldung.com/java-generics

Effecitve Java 3/E - Chapter 5: Generics 

https://docs.oracle.com/javase/tutorial/java/generics/erasure.html

https://www.baeldung.com/java-type-erasure

1. Java Generics and Raw Type

public class<T> Example{
	private T member;
}

When a type parameter T is used in a class or interface declaration like above, we call it a generic class or generic interface. The class Example<T> used here is referred to as a generic type.

When using generics, the concept of raw types comes up. A raw type is when you don't use a type parameter at all with a generic type — in other words, when you declare and use the generic type Example<T> as just Example.

public class Example<T> {
    private T member;

    public Example(T member) {
        this.member = member;
    }

    public static void main(String[] args) {
        Example<Integer> parameterType = new Example<>(1);
        Integer parameterTypeMember = parameterType.member;
        System.out.println(parameterTypeMember);

        Example rawType = new Example(1);
        Object rawTypeMember = rawType.member;
        System.out.println(rawTypeMember);
    }
}

The code above shows both a generic parameterized type and a raw type in use. But don't use raw types.

The advantage of generics is that they guarantee type safety at compile time. Since variables declared with a generic type are type-checked at compile time, you're protected from UncheckedException errors like ClassCastException at runtime.

On the other hand, when used as a raw type like below, you lose the benefits of safety and expressiveness that generics provide. That's why you can see the IDE giving you a warning like "Raw use of parameterized class 'Example' ".

So why do raw types exist in the first place? The reason raw types came about is related to erasure, a key characteristic of generics.

Generics were introduced in JDK5. The goals were to reduce bugs and to add a layer of abstraction over types.
Because of this, JDK5 — which introduced generics — had to accommodate all existing code while maintaining compatibility with new code that uses generics. So for the sake of code compatibility, they supported raw types and implemented generics using erasure.

2. Generics Type Erasure

Erasure means that element types are only checked at compile time and the type information is not available at runtime. In other words, it's a process where type constraints are enforced only at compile time, and type information is erased at runtime.

List<Object> ol = new ArrayList<Long>(); // 컴파일 에러
ol.add("타입이 달라 넣을 수 없다");

In a situation like this, you can immediately catch the type error at compile time (because List is also implemented as a generic type).

The Java compiler applies type erasure as follows:

• In a generic type (Example<T>), it replaces the type parameter (T) with the corresponding type or Object. 
  Replacing with Object happens when the type is unbounded — meaning it hasn't been bounded like <E extends Comparable<E>>.
  Therefore, the bytecode for this erasure rule only applies to regular classes, interfaces, and methods that can use generics.
• It inserts type casting where necessary to preserve type safety.
• It generates bridge methods to preserve polymorphism in extended generic types.

public static <E> boolean containsElement(E[] elements, E element) {
	for (E e : elements) {
		if (e.equals(element)) {
			return true;
		}
	}
	return false;
}

For a generic method declared like this, the compiler replaces the type parameter E depending on how it's declared.

public static boolean containsElement(Object[] elements, Object element) {
	for (Object e : elements) {
		if (e.equals(element)) {
			return true;
		}
	}
	return false;
}

Following the first rule, since the type parameter E is not declared as bounded, the compiler first replaces the type parameter E with Integer.

At this point, if the programmer used the method in the form of containsElement(Integer[], Integer), the compiler internally inserts type casting code from Object to Integer according to the second rule to preserve type safety, thus guaranteeing the type safety of generics.

In the case of raw types, however, since no type parameter is specified, it simply ends with the conversion to Object.

public static <E extends Comparable<E>> void containsElement(E[] elements) {
	for (E e : elements) {
		System.out.println("%s", e);
	}
}

public static void containsElement(Comparable[] elements) {
	for (Comparable e : elements) {
		System.out.println("%s", e);
	}
}

Additionally, regarding the third rule, the Java compiler can also generate Bridge Methods for generic type safety. A Bridge Method is a method created by the Java compiler during compilation to handle cases where method signatures are slightly different or ambiguous. This can happen when compiling a class that extends a parameterized class or interface.

public class IntegerStack extends Stack<Integer> {
    public Integer push(Integer value) {
        super.push(value);
        return value;
    }
}

The Java compiler needed to ensure there was no mismatch between the push(Integer) method signature of IntegerStack and the push(Object) method signature of Stack, in order to preserve polymorphism even during generic type erasure. So the compiler creates a Bridge method for the type erasure of that generic type at runtime, and it does it like this:

public class IntegerStack extends Stack {
    // Bridge method generated by the compiler
     
    public Integer push(Object value) {
        return push((Integer)value);
    }
 
    public Integer push(Integer value) {
        return super.push(value);
    }
}

You can see that extends Stack<Integer> has been changed to just Stack, and a helper method has been added to match the push parameter to Integer instead of Object. As a result, the Stack class's push method, after type erasure, delegates to the original push method of the IntegerStack class.

3. Use Lists with Generics

Non-Reifiable Type refers to a type that doesn't hold type information at runtime and undergoes type erasure at compile time. The opposite concept is reifiable, which refers to types whose type information is fully available at runtime — the opposite of erasure. 

Typical examples of non-reifiable types include lists like List<String> and List<Number>, while typical examples of reifiable types include arrays like String[] and Number[].

Effective Java recommends using generics — which have the characteristic of type erasure — with List, a non-reifiable type. This is because arrays hold type information at runtime, but when you use generics, the type gets erased, so the generic variable's information isn't available at runtime.

This part is actually something I want to illustrate with an example from a study group discussion about generics that we had while reading Effective Java.

Related issue : https://github.com/Java-Bom/ReadingRecord/issues/88

static <T> T[] pickTwo(T a, T b, T c) {
  switch (ThreadLocalRandom.current().nextInt(3)) {
    case 0:
      return toArray(a, b);
    case 1:
      return toArray(b, c);
    case 2:
      return toArray(a, c);
  }
  throw new AssertionError();
}

static <T> T[] toArray(T... args) {
  return args;
}

public static void main(String[] args) {
  String[] strings = pickTwo("좋은", "빠른", "저렴한");  
}

In the code above, a ClassCastException is thrown. However, when using the pickTwo method like below, no ClassCastException occurs. Why is that?

static <T> List<T> pickTwoList(T a, T b, T c) {
  switch (ThreadLocalRandom.current().nextInt(3)) {
    case 0:
      return Arrays.asList(a, b);
    case 1:
      return Arrays.asList(b, c);
    case 2:
      return Arrays.asList(a, c);
  }
  throw new AssertionError();
}

List<String> strings = pickTwoList("좋은", "빠른", "저렴한");

Let's simplify the problem a bit.

static <T> List<T> pickList(T a) {
        return Arrays.asList(a);
    }

    static <T> T[] toArray(T... args) {
        return args;
    }

    static <T> T[] pickArray(T a) {
        return toArray(a);
    }

    public static void main(String[] args) {
        List<String> stringList = pickList("자바봄");
        String[] stringArray = pickArray("자바봄");
   }
}

In the code above, after pickList passes, executing pickArray throws a runtimeException. The message is [Ljava.lang.Object; cannot be cast to [Ljava.lang.String; — what's the problem?

The answer lies in the reifiability of Array vs. List.

Let's understand the code. Here, generic type inference goes 2 levels deep. Since the type parameter T in pickArray corresponds to String, you'd expect pickArray(String) toArray(String...) to be called. But when you actually check at runtime, it's pickArray(String), toArray(Object...) that gets called. The reason is exactly what we discussed above about generic type inference — when the parameter is unbounded, the compiler replaces it with Object first. While pickArray could infer the String type from main, toArray looks at the generic type, so it infers Object and holds that type information at runtime.

Therefore, pickArray prepares to cast to String[], but as mentioned above, the type that toArray holds at runtime is Object[], so at runtime it tries to forcefully cast like (String[]) Object[], which causes a ClassCastException. (A String array is not a subtype of an Object array, so the cast fails.)

On the other hand, calling pickList compiles successfully. The reason is that List is a non-reifiable type. The casting information is already determined at compile time, and at runtime, thanks to the erasure characteristic of generics, the Java compiler correctly adds the appropriate casting, so no casting error occurs.

To summarize, List + generics works because the casting information determined at compile time is correct. List performs the same compile-time type mismatch checking that is the advantage of generics. Arrays, on the other hand, determine type casting at runtime, which is where the problem arises.

That was a bit long, but the conclusion is actually simple. Generics use type erasure, which allows the compiler to infer types at compile time. To fully leverage this type inference capability, you should use List — which infers types at compile time — instead of Array — which infers types at runtime — to guarantee type safety.

References

https://www.baeldung.com/java-generics

Effecitve Java 3/E - Chapter 5: Generics 

https://docs.oracle.com/javase/tutorial/java/generics/erasure.html

https://www.baeldung.com/java-type-erasure

개발자 포트폴리오, 백엔드 개발자 레주메 (update 2020.06.12)

Developer Portfolio, Backend Developer Resume (update 2020.06.12)