[F-Lab 모각코 챌린지 3일차] Annotation?

부추·2023년 6월 3일
f-lab챌린지
0

F-Lab 모각코 챌린지

목록 보기
3/66

TIL

  1. 알고리즘 : 순위 검색
  2. Java @Annotation
  3. List

1. 순위 검색

2일차 포스트에서 해결하지 못해 오늘 다시 시도한 문제이다. 일단 가장 먼저 '중첩 딕셔너리'를 사용했다. 별로 추천하지 않는다! 효율성에서도 out이었다! 

from bisect import bisect_left

def solution(info, query):
    ans = []
    graph = {} # store score
    for lang in ("java","python","cpp"):
        graph[lang] = {}
        for field in ("backend","frontend"):
            graph[lang][field] = {}
            for year in ("junior","senior"):
                graph[lang][field][year] = {}
                for food in ("chicken","pizza"):
                    graph[lang][field][year][food] = []
    
    for i in info:
        lang,field,year,food,score = i.split()
        graph[lang][field][year][food].append(int(score))
    
    for q in query:
        qlang,_,qfield,_,qyear,_,qfood,qscore = q.split()
        qlang = [qlang] if qlang!="-" else ["java","python","cpp"]
        qfield = [qfield] if qfield!="-" else ["backend","frontend"]
        qyear = [qyear] if qyear!="-" else ["junior","senior"]
        qfood = [qfood] if qfood!="-" else ["chicken","pizza"]

        scores = []
        for lang in qlang:
            for field in qfield:
                for year in qyear:
                    for food in qfood:
                        scores += graph[lang][field][year][food]
        
        scores.sort()

        ans.append(len(scores)-bisect_left(scores,int(qscore)))

    return ans

언어, 분야, 연차, 음식을 각각 중첩해서 딕셔너리에 넣어놓고 query에 맞는 놈들을 뽑아내 합친 뒤 sort했는데.. 밑에서 세번째줄 scores.sort()에서 결국 시간초과가 난듯하다.

와일드카드, 즉 query 리스트의 -를 어떻게 처리하냐가 사실 효율성의 핵심이었던 것 같다. 위 코드의 경우 와일드카드가 등장했을 때, 리스트를 이용해 딕셔너리에서 탐색할 범위를 늘렸다. 서로 다른 조건 하에서 점수를 합쳤으므로 마지막에 합친 scores 리스트를 한 번 더 정렬해줘야 했다.

결국 "-"를 포함해 쿼리에서 요구할만한 모든 경우에 대해 점수 정보를 미리 만들어놓아야 한다는 점을 깨달았다. 이를 위해 딕셔너리의 키 값을 조금 더 효율적으로 설정했다.


효율성까지 정답처리된 코드이다.

from collections import defaultdict
from bisect import bisect_left

def solution(info,query):
    dict,ans = defaultdict(list),[]
    
    for i in info:
        i = i.split()
        condition,score = i[:-1],int(i[-1])
        for c1 in (i[0],"-"):
            for c2 in (i[1],"-"):
                for c3 in (i[2],"-"):
                    for c4 in (i[3],"-"):
                    	# wild card 경우까지 전부 추가
                        dict[(c1,c2,c3,c4)].append(score)
    for key in dict:
    	# 미리 sort
        dict[key].sort()
    
    for q in query:
        q = [c for c in q.split(" ") if c!="and"]
        key = (q[0],q[1],q[2],q[3])
        qscore = int(q[-1])

        if (key in dict):
            scores = dict[key]
            ans.append(len(scores)-bisect_left(scores,qscore))
        else:
            ans.append(0)
    return ans
  • defaultdict를 이용해 딕셔너리의 기본값을 리스트로 지정했다.
  • 딕셔너리의 key는 튜플이다. info 리스트에 제공된 지원자의 각각의 정보를 담되, query의 wild card를 처리하기 위해 항목이 "-"인 정보까지 추가했다.
  • 이로써 해당 조건에 맞는 지원자들의 점수를 미리 정렬할 수 있다.
  • 쿼리를 튜플로 구성하고, 이분 탐색을 통해 조건을 만족하는 지원자 수를 찾으면 해결이다.

쿼리가 10만개, 지원자가 5000명으로 매우 많으므로 완전 탐색은 힘들다는걸 빨리 알아야 한다. 그리고 조건이 고작 4개라는 점에서 딕셔너리의 키로 이용할 수 있다는 점을 캐치해야 할 것 같다.




2. Annotation

1. @Annotation : 메타데이터

자바 소스코드를 읽거나 쓰면 "@" 표시가 붙은 단어와 떨어질 수 없다. @Override, @Bean, @Getter, @Component ...

자바 어노테이션이란, 자바 소스코드의 메타데이터이다. 메타데이터란 데이터 자체에 대한 설명으로, 자바 어노테이션의 경우 자바 소스코드 대한 설명을 담고있다고 이해할 수 있다. 프로그램의 주요 비즈니스 코드와는 큰 관련이 없지만, 코드 자체에 대한 설명이나 횡단 관심사의 기능을 추가하고 싶을때 어노테이션을 이용한다.


2. Annotation 사용하는 이유

1) 코드 가독성 향상

어노테이션은 코드 정보 자체를 담고있다는 특징 때문에 코드의 가독성을 높여준다.

상위 인터페이스나 클래스를 상속 / 구현할 때, 오버라이드 하는 메소드에 @Override 어노테이션을 붙인다. 그를 통해 이 메소드가 상위 메소드를 재정의하고 있음을 표현하여 코드를 더 잘 이해할 수 있고, 재정의에 오류가 있을 때 IDE 상에서나 컴파일 타임에 검출 가능하다.

추가하고 싶은 메타데이터가 있다면, 그 정보를 담을 수 있는 어노테이션을 새로 선언해 사용할 수도 있다.

2) 생산성 향상

프로그래밍의 효율성은, 주요 비즈니스 로직에 집중하여 원하는 기능을 빨리 구현했을 때 올라간다. 주요 관심사에서 벗어난 부가 기능들을 하나하나 만들다보면 생산성이 떨어지기 쉽다. 이런 위험을 피하기 위해 비슷한 역할을 하는 코드, 주요 관심사에서 벗어난 코드, 구조의 기본이 되는 코드 등을 어노테이션을 이용해 축약할 수 있다.

많이들 사용하는 Lombok이 그 예시이다. Lombok 라이브러리엔 @Getter, @Setter, @AllArgsConstructor, @toString 등이 존재하는데 이것들은 모두 클래스 구성의 기본이 되는 boilerplate 코드를 작성해줌으로써 개발자의 생산성 향상에 기여한다.

@NonNull을 통해 타입에 대한 null checking이 간단하게 진행되므로 이또한 그 예시라고 할 수 있다.

3) 좋은 성능

위와 같은 장점을 가진 어노테이션을 사용한다고 해서 딱히 프로그램의 성능에 영향을 미치는 것도 아니다. 뒤에 어노테이션의 동작 과정에서 설명하겠지만, 어노테이션은 컴파일 타임에 처리된다. 런타임엔 어노테이션 프로세서에 의해 바이트코드에 추가된 코드를 실행할 뿐이다. 런타임에 추가적인 작업이 필요하지 않으므로, 어노테이션을 사용하는 것이 프로그램의 성능을 떨어뜨리는 것은 아니다.


3. Annotation 동작 과정

어노테이션은 컴파일 타임에 어노테이션 프로세서에 의해 처리된다. javac의 컴파일 타임에, 등록된 어노테이션 프로세서가 소스코드에 존재하는 어노테이션을 스캔해 코드를 추가하는 방식으로 동작한다.

간단한 그림을 보며 추가로 이해해보자.
어노테이션 프로세서는 컴파일러에게 java 소스코드 혹은 byte code를 받아 프로세싱 라운드를 시작한다.
어노테이션 프로세서는 소스코드에 존재하는 어노테이션을 스캔하고 프로세서의 로직에 맞는 코드를 추가하여 결과물(주로 .java)로 내놓는다.
다음 어노테이션 프로세서가 동작한다. 다음 프로세서는 이전 프로세서가 결과물로 내놓은 코드를 받아 프로세싱 라운드를 시작한다.
같은 과정은 소스코드의 모든 어노테이션이 처리될때까지 연쇄적으로 일어난다.

각 어노테이션에 맞는 어노테이션 프로세서가 순서대로 동작한다는 것이 핵심이다. 어떤 프로세서가 먼저 동작하는지에 따라 코드가 추가되는 순서도 달라지는데, 이때문에 문제가 발생하는 경우도 종종 있는듯하다(롬복을 이용해 생성자를 만들었는데, 생성자가 있어야 동작 가능한 프로세서가 롬복보다 먼저 프로세싱을 시작해버리든가 하는 상황 등)



4. Annotation 종류

1) Built-in 어노테이션

다른 외부 라이브러리를 가져올 필요 없이, Java 자체에 존재하며 사용가능한 어노테이션이다.

  • @Override : 상위 클래스를 상속받거나, 인터페이스를 구현했을 때 재정의한 메소드에 붙이는 어노테이션.
  • @Deprecated : 다음 버전에서 더이상 지원하지 않을 예정이거나, 더이상 사용을 장려하지 않는 요소에 붙이는 어노테이션.
  • @FuntionalInterface : 람다식으로 사용가능한 인터페이스에 붙이는 어노테이션. 보통 한 가지의 메소드를 가지고 있음.
  • @SuppressWarning : 컴파일러가 내뱉는 경고 문구를 무시하기 위해 사용하는 어노테이션. "unchecked", "deprecated"를 value 요소로 설정할 수 있다.

2) 메타 어노테이션

어노테이션을 위한 어노테이션이다. 필요에 따라 개발자가 직접 어노테이션을 작성해야하는 경우가 있는데, 이때 어노테이션을 정의하기 위해 사용한다.(메타 데이터를 위한 메타 데이터를 위한 메타데이터)

  • @Target : 해당 어노테이션이 붙을 수 있는 범위를 지정한다. ElementType 값을 설정으로 받는다.
    • CONSTRUCTOR : 생성자 method
    • FIELD : 클래스 멤버변수, enum 상수
    • LOCAL_VARIABLE : 지역 변수
    • METHOD : 메소드
    • PACKAGE : 패키지
    • PARAMETER : 매개변수
  • @Retention : 해당 어노테이션과 그 기능이 유지되는 기간을 지정한다. RetentionPolicy 값을 설정으로 받는다.
    • SOURCE : 소스 파일에서만 사용하고, 클래스파일엔 존재하지 않는다. 거의 주석과 같은 기능
    • CLASS : 클래스 파일에만 존재하고, 런타임엔 사용하지 않는다. default
    • RUNTIME : 클래스 파일에도 존재하고, 런타임동안 JVM이 사용할 수 있다.
  • @Documented : 작성한 어노테이션에 대한 정보가 javadoc에 들어가길 원할 때 사용한다.
  • @Inherited : 해당 어노테이션이 붙은 클래스의 자식 클래스에도 같은 어노테이션을 붙일 때 사용한다.

3) custom 어노테이션

필요에 의해 개발자가 직접 정의해서 사용하는 어노테이션이다. 다음과 같이 어노테이션의 이름 앞에 "@interface"를 붙여 이것이 개발자가 직접 정의한 custom annotation임을 알린다.

public @interface MyAnno { }

어노테이션을 정의할 때 알아야할 기본적인 특징을 몇 가지 살펴보겠다.

  • 어노테이션은 내부적으로 Java.lang.annotation.Annotation 클래스를 확장한다. 따라서 다른 클래스를 추가로 extend할 수 없다.
  • 어노테이션 안에 0개 이상의 element를 가질 수 있다.
  • element는 어노테이션의 내부에 가지고있는 상태값이다. element 개수가 각각 0개, 1개, 2개인 어노테이션은 아래와 같이 정의된다.
public @interface NoElement {
}

public @interface OneElement {
    public int element();
}

public @interface TwoElements {
    public String name();
    public int value();
}

이렇게 정의한 custom annotation은 자바 코드에서 자유롭게 사용할 수 있다.

@OneElement(element = 3)
public class Example {
    public static void main(String[] args) {
        @TwoElements(name = "제 어노테이션입니다",value = 3)
        String hi;
    }
}




3. List

List는 순서가 있고, 값이 중복되어도 상관없을 때 이용하는 자료구조이다. Set, Map 등의 여타 다른 자료구조를 사용할 특별한 이유가 없으면 대부분 List를 사용한다. 자바에서 List는 Collection 프레임워크의 인터페이스이고, 이를 구현한 구현체는 대표적으로 ArrayList<E>, LinkedList<E>가 있다.

1) ArrayList

내부적으로 배열(array)을 이용한다.

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

initial capcity를 지정하지 않은 기본 생성자는 위와 같은데, 따라가보면 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};라고 적힌 코드를 찾을 수 있다.

여기서 말하는 default capacity는 얼마일까?

private static final int DEFAULT_CAPACITY = 10;

10이다. 즉, ArrayList에서 아무런 인자가 없는 생성자는 크기가 10인 배열을 만든다.

# add

add() 메소드를 통해 initial capacity 이상의 요소가 ArrayList에 추가되면, 새로운 capacity의 배열을 만든 뒤 기존 배열의 값을 복사한다.

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

newCapacity 계산 후 Arrays.copyOf()를 호출하는 부분을 보면 알 수 있다.

# remove

remove() 메소드는 내부적으로 fastRemove() 메소드를 호출하는데, 이는 지우고자 하는 ArrayList인 es와 인덱스 i를 인자로 받는다. 그 뒤 해당 인덱스의 뒤에 있는 원소들을 한 칸씩 앞으로 당긴다.

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

# find

indexOf(O o) 메소드는 내부적으로 indexOfRagne() 메소드를 호출하는데, 이는 ArrayList를 가장 앞부터 순회하며 맞는 객체의 인덱스를 반환한다.

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}



2) LinkedList

내부적으로 Node<E> 클래스를 사용한다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
  • 동일한 타입의 next, prev 노드를 멤버 변수로 가지고 있다. 이는 LinkedList의 이전 노드, 다음 노드를 가리킨다.
  • 실질적인 노드 값을 담고 있는 것은 item이다.
  • next, prev 변수를 통해 LinkedList 내 Node를 iterate하는 자료구조임을 짐작할 수 있다.

# add

새로운 노드를 생성하며, 가장 마지막 노드를 가리키는 last 필드값을 업데이트한다.

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

원래 LinkedList자체가 비어있어 last 필드가 null이라면 first와 last를 모두 새로 들어온 요소 값으로 업데이트 하는 과정을 확인하자.


# remove

삭제할 노드를 찾은 뒤, 해당 노드 값의 next 필드를 null로 설정하고, 해당 노드의 바로 앞 노드의 next 필드를 원래 노드의 next값으로 대체한다.

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

# find

LinkedList의 head부터 시작해, item 필드가 일치할 때까지 next 노드를 순회한다. 해당 로직을 수행하는 indexOf() 메소드의 한 부분이다.

for (Node<E> x = first; x != null; x = x.next) {
    if (o.equals(x.item)) return index;
    index++;
}



3) ArrayList vs LinkedList

간단하게 큰 특징을 정리해보면 다음과 같다.

ArrayListLinkedList
구현 방법배열(array)Node 객체를 이용한 연결
데이터 접근 시간(by index)O(1)최악의 경우 O(N)
검색(find)최악의 경우 O(N)최악의 경우 O(N)
삽입 / 삭제 시간capacity를 넘기는 상황, list의 중간에 있는 데이터를 삭제해야 하는 상황 등에 배열 복사 시간 발생삽입 / 삭제 index까지 이동해야하는 시간 발생
장점빠른 검색 시간 + Cache 사용배열 복사 과정이 없어 ArrayList보다 삽입 / 삭제 동작에 더 유리
구현체(JAVA)ArrayListLinkedList

일반적으로 add나 remove 등 list의 원소를 수정하는 동작이 많으면 LinkedList, 그렇지 않은 경우 ArrayList를 사용하는 것이 그동안의 상식이었다.

그러나 다음과 같은 이유 때문에 최근엔엔 ArrayList가 더 선호되는 모양이다.

  • CPU cache를 사용할 수 있어 실제 프로그램에서 동작이 빠르다는 점
  • java 언어 자체적으로, 그리고 하드웨어적으로 많은 발전이 일어나 배열 복사에 그렇게 큰 시간이 소모되지 않는다는 점



REFERENCE

https://velog.io/@dion/%EB%B0%B1%EA%B8%B0%EC%84%A0%EB%8B%98-%EC%98%A8%EB%9D%BC%EC%9D%B8-%EC%8A%A4%ED%84%B0%EB%94%94-12%EC%A3%BC%EC%B0%A8-Annotation

https://velog.io/@eia51/Annotation-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5%EA%B8%B0

https://docs.oracle.com/javase/tutorial/java/annotations/index.html

https://velog.io/@suyeon-jin/%EB%A6%AC%ED%94%8C%EB%A0%89%EC%85%98-%EC%8A%A4%ED%94%84%EB%A7%81%EC%9D%98-DI%EB%8A%94-%EC%96%B4%EB%96%BB%EA%B2%8C-%EB%8F%99%EC%9E%91%ED%95%98%EB%8A%94%EA%B1%B8%EA%B9%8C

https://www.youtube.com/watch?v=xvi-n11kym0&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72

profile
부추
부추튀김인지 부추전일지 모를 정도로 빠싹한 부추전을 먹을래
이전 포스트

[F-Lab 모각코 챌린지 2일차] Immutable

다음 포스트

[F-Lab 모각코 챌린지 4일차] JVM

0개의 댓글