Guiwoo's Blog

2244. Minimum Rounds to Complete All Tasks

0번 부터 시작하는 인덱스가 주어지고 한번의 테스크는 2,3 개 만 이루어진다. 동일한 레벨 만 동시에 작업할수 있다.

최소 라운드 를 구해라 만약 없다면 -1 을 리턴 하라는 문제이다.

최대 갯수가 10000 개 밖에 되지않는다.

Map 을 이용해 저 숫자들 을 분류하고, bfs 를 이용해 최소 라운드 를 찾아갈 생각을 했다.

class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer,Integer> map = new HashMap();
            for(int a:tasks){
                Integer b = map.getOrDefault(a,0);
                map.put(a,b+1);
            }

            int round = 0;
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                Integer value = entry.getValue();
                if(value < 2) return -1;
                int calculate = calculate(value);
                if(calculate < 0) return -1;
                round += calculate;
            }

            return round;
    }

    private int calculate(Integer value) {
            int round =0;
            boolean found = false;

            Queue<Integer> q = new ArrayDeque<>();
            Set<Integer> set = new HashSet();
            q.add(0);

            while(!q.isEmpty()){
                int size = q.size();
                for(int i =0;i<size;i++){
                    int poll = q.poll();

                    int a = poll + 2;
                    if( a == value) return round+1;
                    int b = poll + 3;
                    if( b == value) return round+1;

                    if(a < value && set.add(a)) q.offer(a);
                    if(b < value && set.add(b)) q.offer(b);
                }
                round++;
            }

            return found ? round : -1;
        }
}

이렇게 작성했더니 무려 126ms 나 나와버렸더 무진장 느리다 ...  아무래도 저 bfs 부분이 문제인거 같은데 나름 최적화 가 되어있다고 생각하는데 이렇게 느린걸 보면 다른 규칙이 있는것 같다.

연산 을 한번 두번 .... 했을때 중복 값을 제외하고 나올 경우의 수를 작성해 보면 위와 같다. 파란색으로 마킹된 부분을 살펴보자. 

모두 3의 배수이다. 2,3 을 이용한다면 모든수 를 작성할수 있다 단 1 인 경우를 제외한다면 이다. caculate 함수 부분을 변경하자.

    private int calculate(Integer value) {
        if(value%3 == 0) return value/3;
        return (value/3)+1;
    }

좋다 이렇게 변경하니 속도가 개선 되었으나 여전히 36ms 로 상위 19% 이다. 많이 느리다. 어떤 부분을 놓친걸까...

class Solution {
    public int minimumRounds(int[] tasks) {
        Arrays.sort(tasks);
        int round = 0;
        int cnt = 1;
        if(tasks.length < 2) return -1;

        for(int i=1;i<tasks.length;i++){
            if(tasks[i-1] != tasks[i]){
                if(cnt < 2) return -1;
                round += calculate(cnt);
                cnt =1;
            }else{
                cnt++;
            }
        }
        
        if(cnt < 2) return -1;
        else round += calculate(cnt);

        return round;
    }

    private int calculate(Integer value) {
        if(value%3 == 0) return value/3;
        return (value/3)+1;
    }
}

로직을 변경해 배열을 정렬하고 for loop 으로 로직 변경 => 10ms  98.8% 까지 나왔다.

음 ? 다른사람의 풀이도 별반 다르지 않다... 다 이런 2가지 방식으로 풀었다.

83. Remove Duplicates from Sorted List

연결 노드상 에서 중복된 값을 지워주는 로직을 구현하면 된다. 재귀 를 노드 의 마지막 까지 이동을 하고

현재 헤드 기준으로 헤드 의 다음을 계속 업데이트 해주면서 날려주는 로직을 재귀 안에 구성하면 될것같다.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        helper(head);
        return head;
    }
    public void helper(ListNode head){
        if(head == null || head.next == null) return;
        while(head.next != null && head.val == head.next.val){
            ListNode next = head.next;
            if(next == null){
                head.next = null;
                break;
            }
            head.next = next.next;
        }
        helper(head.next);
    }
}

null 체크 를 제대로 하지않아서 nullPointer exception 을 여러번 맞았다 ㅎㅎㅎ... while 을 next 의 null 까지 돌리지 않는다면 

1,1,1,1,1,1,1 케이스 에서 1,1 로 반환되는 불상사가 발생한다. 주의 하자

Solution 중에 가독성 좋은 코드가 있어서 가져와 봤다.

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode list = head;
         
         while(list != null) {
        	 if (list.next == null) {
        		 break;
        	 }
        	 if (list.val == list.next.val) {
        		 list.next = list.next.next;
        	 } else {
        		 list = list.next;
        	 }
         }
         
         return head;
    }
}

while 을 이용해서 loop 를 돌리는게 확실히 재귀보다 직관적 이다.

1619. Mean of Array After Removing Some Elements

정렬하고 5% 계산해서 평균 구해주면 되는 Easy 난이도 에 맞는 문제이다.

class Solution {
    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        int cut = (int) ((double) arr.length * 0.05);
        double sum = 0;
        for(int i = cut;i<arr.length-cut;i++){
            sum+=arr[i];
        }
        return sum/(arr.length-(cut*2));
    }
}

    public double trimMean(int[] arr) {
        int n = arr.length;
        double sum = 0d;
        Arrays.sort(arr);
        for (int i = n / 20; i < n - n / 20; ++i) {
            sum += arr[i];
        }
        return sum / (n * 9 / 10);
    }

작년 나름 릿코드 열심히 들어가서 문제를 풀었다고 생각했는데 올해 처음 들어가니 100 일 짜리 뱃지 를 받았다 ㅎㅎ

내년 에는 200 일 짜리 뱃지 를 받아보도록 노력해보자.

944. Delete Columns to Make Sorted

주어진 문자 를 나열하고 세로로 읽었을때 사전 순이 되지 않는 경우를 판별하는 문제이다. 모든 문자열의 길이가 똑같다는 전제조건 이 있어서 이지 난이도라고 생각된다.

class Solution {
    public int minDeletionSize(String[] strs) {
        int answer = 0;
        int len = strs[0].length();
        for(int i=0;i<len;i++){
            for(int j=1;j<strs.length;j++){
                char a = strs[j].charAt(i);
                char b = strs[j-1].charAt(i);
                if( a < b){
                    answer++;
                    break;
                }
            }
        }
        return answer;
    }
}

배열의 최대 크기 1000, 문자의 최대길이 100 => 2중 포문 돌려도 문제없다고 생각해서 바로 작성했다. 

최초 작성시 에 i, j 를 이상하게 지정을 해버리는 바람에 indexOutOfRange 에러가 났다. 언제쯤 이런 잔 실수를 없앨수 있는지...

그래도 제출하니 바로 통과 가 되긴한다.

대부분 의 solution code 들도 이중포문 을 이용해서 작성 되어있다.

520. Detect Capital

주어지는 문제 의 조건 에 맞춰서 구현만 해주면 된다. 

class Solution {
    public boolean detectCapitalUse(String word) {
        char first = word.charAt(word.length()-1);
        if('A' <= first && first <= 'Z'){
            for(char c : word.toCharArray()){
                if(!('A' <= c && c <= 'Z')) return false;
            }
        }else{
            for(int i=word.length()-1;i>=0;i--){
                char c = word.charAt(i);
                if(!('a' <= c && c <= 'z') && (i!= 0)) return false;
            }
        }
        return true;
    }
}

그냥 문제 에서 주어진 그대로 구현했다. 

이 방법 외에는 regex 가 있다. 

class Solution {
    public boolean detectCapitalUse(String word) {
        return word.matches("[A-Z]*|[A-Z]?[a-z]*");
    }
}

대문자 이거나 혹은 대문자가 있거나 없거나 그리고 나머지 소문자 로 채우면 된다.

이것 외에 괜찮다고 생각하는 코드가 있어서 들고왔다.

public boolean detectCapitalUse(String word) {
        if (word.length() < 2) return true;
        if (word.toUpperCase().equals(word)) return true;
        if (word.substring(1).toLowerCase().equals(word.substring(1))) return true;
        return false;
}

반대로 true 가 되는 조건만 을 subString 과 toUpperCase 를 이용해 깔끔하게 코드 를 구사했다. 

그러나 toUpperCase 의 작동하는 방식을 보면 내부적으로 forLoop 를 돌려서 내부로직 수행후 String 을 리턴해준다.

하물며 subString 은 어떤가 String 은 불변 이다 따라서 클래스 내부 의 value 바이트 코드 배열을 arrayCopy 를 수행해 새로운 스트링을 만들어 뱉어준다. 즉 for 를 한번더 돈다는 의미이다. eqaul 또한 하나씩 비교하기 위해 forLoop 을 돈다 

이렇게 수행 로직 만 보고 생각한다면 느릴수 밖에없다. 다만 이해하기 쉽다. 

실제 업무에 투입되어 작성한코드 라면 사실 나는 이 코드 처럼 작성하고 싶다. 성능상의 문제가 있는 것 이 아니라면 코드 자체를 이렇게 두고 유지할것이다. 왜 ? 읽기 쉬운 코드가 최고니깐.

290. Word Pattern

주어진 패턴에 맞는 스트링 값을 찾아 반환 해주면 되는 문제이다.

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> map = new HashMap();
        Set<String> set = new HashSet();

        int len = pattern.length();
        String[] arr = s.split(" ");

        if(len != arr.length) return false;
        for(int i=0;i<len;i++){
            char p = pattern.charAt(i);
            if(!map.containsKey(p) && set.add(arr[i])){
                map.put(p,arr[i]);
            }
            if(!map.getOrDefault(p,"ㄱ").equals(arr[i])) return false;
        }

        return true;
    }
}

쫌 과하다 싶을 만큼 자료구조 를 선언해서 사용했다. Set 없이 그냥 map.containsValue 를 사용해도 됬었다. 다만 containsValue 를 사용해서 forLoop 를 두번돌게 하고 싶지 않았다. 

Map 을 두번써서 좌우로 맵핑 한 사람도 있고, 다양한 풀이방법 이 있다.

본인이 선호하는 방법으로 작성하면 된다고 생각한다. 

이렇게 3문제를 풀어도 2,3 번 같은경우는 2~3번씩 제출을 더 했다. 로직 의 오류, 예외케이스 핸들링 생략 등이 그 이유이다.

언제쯤 풀어야 이런 이지 난이도 를 한번에 클리어 할수 있을까.... 

나는 언제 LinkedList를 사용했는가? 데이터를 주로 앞에서 삽입하는 경우 즉 queue의 자료구조가 필요했다면 사용한 것 같다. 

linked 연결되 있다는 소리이다. 여기에 는 그렇다면 그래프, 트리 도 포함되어야 마땅하지 않겠는가? 이 두 개의 자료구조 또한 연결된 구조다. 다만 이번 챕터에서 분석하고 성능측정 해볼 것은 다음의 하나의 노드만 포인팅 하는 자료구조를 공부해볼 것이다.

연결 자료 구조는 데이터 하나를 크게 노드라는 단위로 부르고 있으며 노드 안에는 하나의 데이터가 들어있고 다음 노드를 포인팅 하는 주소값이 들어가 있다. 

바로 구현해 보자.

생성자 몇 개 와 toString을 만들어 나의 편의성을 위해 위와 같이 작성했다. 이번에도 역시 숫자의 데이터 값만 받아서 노드를 구상할 생각이다.

지난번에 사용한 인터페이스 그냥 그대로 가져다 사용해도 될 것 같다고 생각한다. 사실 명확하게 떠오르는 생각 이 없다..... LinkedList 본연의 기능보다 오히려 Queue 형태의 자료구조로 더 많이 사용했던 것 같다.

생각보다 사용한 함수들 이 많이 있어서 일단 작성했다. (API DOC을 참고해서 작성)

public interface LinkedListInterface {
    void add(int index,int number);
    boolean add(int number);
    void addFirst(int number);
    void addLast(int number);
    
    boolean contains(int number);
    
    int get(int index);
    int getFirst();
    int getLast();
    
    int indexOf(int number);
    
    boolean offer(int number);
    boolean offerFirst(int number);
    boolean offerLast(int number);
    
    int peek();
    int peekFirst();
    int peekLast();
    
    int poll();
    int pollFirst();
    int pollLast();
    
    int pop();
    void push(int number);
    
    int remove();
    int remove(int index,int number);
    int removeFirst();
    int removeLast();
    
    int set(int index,int number);
    int size();
}

구현

package datastructure.myLinkedList;

import java.util.LinkedList;

public class GuiwooLinkedList implements LinkedListInterface {

    private int total;
    private GuiwooNode first;
    private GuiwooNode last;

    public GuiwooLinkedList() {
        this.total = 0;
        this.first = null;
        this.last = null;
    }

    @Override
    public void add(int index, int number) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        if(this.size() == 0 || this.size() == index+1){
            this.add(number);
            return;
        }

        if(index == 0){
            first = new GuiwooNode(number,first);
        }else{
            int count = 0;
            GuiwooNode current = this.first;
            GuiwooNode previous = this.first;
            while(count < index){
                previous = current;
                current = current.next;
                count++;
            }
            previous.next = new GuiwooNode(number,current);
        }
        total++;
    }

    @Override
    public boolean add(int number) {
        if(first == null){
            first = new GuiwooNode(number);
            first.next = first;
            last = first;
        }else{
            GuiwooNode next = new GuiwooNode(number);
            last.next = next;
            last = next;
        }
        total++;
        return true;
    }

    @Override
    public void addFirst(int number) {
        if(this.size() == 0){
            this.add(number);
        }else{
            first = new GuiwooNode(number,first);
        }
    }

    @Override
    public void addLast(int number) {
        this.add(number);
    }

    @Override
    public boolean contains(int number) {
        return this.indexOf(number) >= 0;
    }

    @Override
    public int get(int index) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        GuiwooNode current = this.first;
        int cnt = 0;
        while(cnt < index){
            current = current.next;
            cnt++;
        }
        return current.data;
    }

    @Override
    public int getFirst() {
        if(first == null) throw new NullPointerException();
        return first.data;
    }

    @Override
    public int getLast() {
        if(first == null) throw new NullPointerException();
        return last.data;
    }

    @Override
    public int indexOf(int number) {
        GuiwooNode current = this.first;
        int cnt = 0;
        while(current != null){
            if(current.data == number) return cnt;
            cnt++;
            current = current.next;
        }
        return -1;
    }

    @Override
    public boolean offer(int number) {
        try{
            return this.add(number);
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public boolean offerFirst(int number) {
        try{
            this.addFirst(number);
            return true;
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public boolean offerLast(int number) {
        try{
            this.addLast(number);
            return true;
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public int peek() {
        return this.getFirst();
    }

    @Override
    public int peekFirst() {
        return this.getFirst();
    }

    @Override
    public int peekLast() {
        return this.getLast();
    }

    @Override
    public int poll() {
        if(first == null) throw new NullPointerException();
        int value = first.data;
        first = first.next;
        return value;
    }

    @Override
    public int pollFirst() {
        return this.poll();
    }

    @Override
    public int pollLast() {
        GuiwooNode current = first;
        GuiwooNode previous = first;
        while(true){
            if(current.next == null) break;
            previous = current;
            current = current.next;
        }
        previous.next = null;
        return current.data;
    }

    @Override
    public int pop() {
        return this.pollLast();
    }

    @Override
    public void push(int number) {
        this.add(number);
    }

    @Override
    public int remove() {
        return this.pollLast();
    }

    @Override
    public int remove(int index) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        if(index == 0) return this.poll();
        else if(index+1 == this.size()){
            return this.pollLast();
        }else{
            int cnt = 0;
            GuiwooNode current = first;
            GuiwooNode previous = first;
            while(cnt < index){
                cnt++;
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
            return current.data;
        }
    }

    @Override
    public int removeFirst() {
        return this.pollFirst();
    }

    @Override
    public int removeLast() {
        return this.pollLast();
    }

    @Override
    public int set(int index, int number) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        GuiwooNode current = first;
        int count = 0;
        while(count <index){
            if(current != null) current = current.next;
            count++;
        }
        current.data = number;
        return number;
    }

    @Override
    public int size() {
        return this.total;
    }
}

테스트 코드

package datastructure.myLinkedList;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class GuiwooLinkedListTest {
    private GuiwooLinkedList gll;
    private int listSize = 10;
    @BeforeEach
    void init(){
        gll = new GuiwooLinkedList();
        for(int i=1;i<=listSize;i++){
            gll.add(i);
        }
    }

    @Test
    void addBasic(){
        int i = gll.indexOf(10);
        assertEquals(9,i);
    }

    @Test
    void contains(){
        boolean contains = gll.contains(100);
        assertFalse(contains);
    }

    @Test
    void sizeCheck() throws Exception{
        int size = gll.size();
        assertEquals(listSize,size );
    }

    @Test
    void addNumberByIndex() throws Exception{
        gll.add(0,100);
        int i = gll.indexOf(100);
        // 맨 앞에 추가할때
        assertEquals(0,i);
        // 가운데 추가할때
        gll.add(5,500);
        int i1 = gll.indexOf(500);
        assertEquals(5,i1);

        assertEquals(listSize+2,gll.size());
    }

    @Test
    void addFirst(){
        gll.addFirst(10000);
        int i = gll.indexOf(10000);
        assertEquals(i,0);
    }

    @Test
    void addLast() throws Exception{
        gll.add(20000);
        int i = gll.indexOf(20000);
        assertTrue(gll.contains(20000));
        assertEquals(listSize,i);
        assertEquals(listSize+1,gll.size());
    }

    @Test
    void getByIndex() throws Exception{
        int i = gll.get(0);
        assertEquals(1,i);
        int i1 = gll.get(9);
        assertEquals(10,i1);
    }

    @Test
    void getFirst() throws Exception{
        int first = gll.getFirst();
        assertEquals(1,first);
    }

    @Test
    void getLast() throws Exception{
        int last = gll.getLast();
        assertEquals(10,last);
    }

    @Test
    void peek() throws Exception{
        int peek = gll.peek();
        assertEquals(1,peek);
        int i = gll.peekFirst();
        assertEquals(1,peek);
        int i1 = gll.peekLast();
        assertEquals(10,i1);
    }

    @Test
    void poll() throws Exception{
        for(int i=1;i<=listSize;i++){
            int poll = gll.poll();
            assertEquals(poll,i);
        }
    }

    @Test
    void pollLast () throws Exception{
        int i = gll.pollLast();
        assertEquals(10,i);
    }

    @Test
    void removeByIndex () throws Exception{
        gll.remove(5);
        int i = gll.indexOf(6);
        int i1 = gll.get(5);
        assertEquals(i,-1);
        assertEquals(i1,7);
    }

    @Test
    void set() throws Exception{
        gll.set(9,1000);
        int i = gll.indexOf(1000);
        assertEquals(9,i);
    }

}

어제 와는 다르게 apiDoc을 보고 작성했으니 실질적인 비교를 해보자.

먼저 클래스 작성자의 설명을 읽어보자.

doubly-linked list라는 표현을 쓴다. 이중연결 리스트?라고 해석이 되는데 음 그러면 노드의 선언이 잘못되었다. 

노드 내부적으로 필드가 하나 더 추가되어 앞뒤로 탐색이 가능해야 한다. 단방향 리스트 가 되어버린 내 구현체는 반쪽 짜리였다.

어쩐지 함수를 작성할 때마다 매번 역방향 탐색 이 있다면 적어도 50% 이상의 성능향상 이 있다고 생각되던 참이던데 참... 

마저 읽다 보면 arrayList와 동일하게 이 클래스도 동기화 예약어를 사용하지 않는다.

다중 스레드 환경에서 비동기적 수행이 필요하다면 아래와 같은 방식을 권장한다.

Collections.synchronizedList(new LinkedList(...));

읽다 보면 재미있는 설명과 예외가 있다. ConcurrentModificationException 전 회사 다닐 때 마주했던 에러였다.

언제 발생하는가? 리스트를 순회하면서 데이터 수정 을 하게 되면 마주하게 되는 에러이다.

modCount를 비교하면서 순회하게 되는데 이때 modCount 순회와 modCount의 값을 비교하면서 돌게 되는데 이때 숫자가 맞지 않다면 위와 같은 에러를 뱉어낸다. 한 번씩 고의로 에러를 내보면 어떤 의미인지 이해하기 쉽다.

listIterator 의해 수행되는 반복자는 빠르게 위 예외를 터트린다고 한다. 최대한 빠르게 위 에러를 터트리는데, 클래스 작성자는 이 예외에 의존해 프로그램을 작성하지 말라고 말한다. 오직 버그를 확인하기 위해 확인하라고 한다.

즉 동기화되지 않은 동시 수정이 있는 겨우 위와 같은 에러를 빠르게 터트려 주어 사전에 방지해주는 함수 설계가 되어 있지 않을까라고 생각한다. modCount 가 여기서 말하는 빠르게 터트리는 트리거 일 것 같은데 차근차근 함수를 살펴보자.

add(int index, E element)

- 특정 인덱스에 원하는 값을 넣어주는 함수이다

- 나의 구현 : 인덱스 가 현재 사이즈 보다 크거나 같은 경우 예외를 던지고, 제일 앞에 추가할 때 뒤에 추가할 때의 분기를 나누어 주었고 , 사이즈에 따른 분기도 나누어 주었다.

-  총 3개의 함수를 호출한다. (checkPositionIndex, linkLast, linkBefore)

- checkPositionIndex => 말 그대로 들어온 인덱스의 범위를 확인하는 함수이다.

- linkLast => index와 사이즈가 같은 경우 분기를 나눈다. 함수 내부적으로 총 개수에 따라 다시 분기를 나누고 first last 그리고 size를 업데이트해준다.

- linkBefore => 말 그대로 가운데 끼여 주는 함수이다. 확실히 previous 포인터 가 있으니깐 함수가 훨씬 간단한다.

o(n) 만큼 의 시간이 걸릴 것으로 보인다. for loop에 의해 분기를 돌아 index까지 current와 previous 업데이트가 필요하기 때문이다.

node(index)의 함수가 따로 있는데 이건 인덱스에 따른 노드를 반환해주는 함수이다. 
1000줄 이 넘어가는 클래스이다 보니 클래스 작성자도 귀찮았는지 x라는 변수를 선언해서 리턴해준다. ㅋㅋ
클린코드 읽다 보면 변수명에 대해 한 챕터를 사용할 정도로 중요하게 생각하는 거 같은데 작자 가 중간중간 자바 의 몇몇 클래스에 대해 혹평을 내리고는 하는데 이런 것 들도 그의 마음에 들지 않았을 것으로 생각된다.ㅎㅎ

다만 이 이렇게 previous와 next를 동시에 가지고 있다면 total 기준으로 반으로 나눠 가까운 쪽에서 시작한다면 최소 내가 작성한 코드보다 빠를 것으로 예상된다.

add(E e)

- 가장 끝 쪽에 e를 추가해주는 함수이다.

-  나의 구현 : 총 total의 숫자를 증가시켜 주고, 현재 노드가 없는 경우만 판별해 분기를 나눠 주었다. null이라면 first와 tail 모두 동일한 노드이기 때문에 이렇게 분기를 나눠주었다.

- 위에서 사용한 linkLast(e)에 그냥 return true이다.

- 사실 인터페이스 작성하고 클래스 구현을 하면서 이 함수에서 boolean을 리턴하면서 얻게 되는 이득이 뭔지 고민을 많이 해봤다. 도대체 어떤 경우에 false 리턴하는지 몰랐는데... 그냥 여기  클래스 작성자도 true로 박아놨다. ㅎㅎ.. 고민 한 시간이 아깝다...

o(1)의 시간이 걸릴 것으로 예상된다. 왜? tail을 직접적으로 필드 내에 가지고 있기 때문에 바로바로 접근이 가능하다. 고민의 여지없이 상수 시간이다.

addFirst(E e)

- 이번에는 가장 앞쪽에 e를 추가해주는 함수이다.

-  0인 사이즈에 따라 분기를 나눠 위에서 작성한 add(E e)를 이용해 추가해주거나 head를 교체해주거나 단순하다.

- modCount와 size를 증가시켜 주고, linkFirst라는 새로운 함수가 있는데 내가 작성한 것 과 다를 바 없다.

- o(1)의 시간이 소요된다 이유는 위와 동일하다.

addLast(E e)

- 나의 구현 : 끝에 추가하나 add를 이용해서 마지막에 추가하나 별차이를 모르겠다 실제로도 그냥 add 함수를 내부적으로 구현했다.

- add와 동일하게 구현되어 있다 단 차이점이라면 반환값의 유무 정도?

- o(1) add 함수 자체를 들고 와서 사용하기 때문에 이렇게 정했다.

contains(E e)

- e 가 list 안에 존재하는 여부를 반환해주는 함수이다.

- 나의 구현 : 지난번 ArrayList에서 했듯이 indexOf를 이용해 -1을 리턴하면 false를 리턴하는 함수를 작성했다.

- 나의 구현과 동일하게 작성되어 있다. indexOf를 이용해 반환한다.

- indexOf는 loop를 이용해 리스트를 순회하기 때문에 o(n) 시간 복잡도를 소요한다.

get(int index)

- 연결 리스트 이더라도 리스트 본연의 get 이 있어야 한다. index에 따른 값을 반환한다.

- 나의 구현 : index 범위를 확인 후 하나의 currentNode와 count를 지정해 count 가 index에 도달할 때까지 루프를 돈다.

- 확실히 pervious 가 있으니깐 위에서 내가 언급했듯이 index와 전체 크기를 비교해 반 이하라면 front에서 이상이라면 rear로부터 시작한다.

- o(n)이라고 해야 할지 o(lonN) 이라고 해야할지 잘 모르겠다. 어쨌든 o(n) 보다는 빠르다는 생각이 든다. o(1) 보다는 느리지만 o(n) 보다는 빠르기 때문에 o(logN)이라고 생각한다. 

getFirst()

- 함수명 그대로 당연히 첫 번째 Element를 반환한다.

- 나의 구현 : Frist에 해당하는 포인터는 객체 내부에 존재하기 때문에 바로 조회 가능하다.

- null 체크 이후 바로 나와 유사하게 리턴을 때려주는 모습이다.

- 의심 여지없이 o(1) 시간복잡도를 가진다.

getLast()

- 함수명 그대로 마지막 Element를 반환한다.

- 나의 구현 : First와 동일하게 Last 즉 tail 노드 도 가지고 있기 때문에 바로 조회 가능하다.

- 위와 동일하다.

- o(1) 시간 복잡도

indexOf(E e)

- 주어진 오브젝트의 인덱스를 반환하는 함수이다 없다면 -1을 반환하기 때문에 contains에서 활용된다.

- 나의 구현 : 사실 이 함수를 제일 먼저 구현했다. testCode에서 확인을 위해서는 add와 확인 이 필요하기 때문에 먼저 작성했다,

단순하게 while을 이용해 동일한 오브젝트를 만날 때까지 돌린다.

- 나와 동일하게 반복문 한 번의 순회를 통해 동일한 값을 찾아낸다. 다만 null 인 경우 의 분기를 나눠준다. 

- for 문 자체를 정말 깔끔하게 사용했다. 아래와 같은 방식으로 사용했다. 중간 x!= null 이 인상적이다. 

for(Node<E> x = first; x != null; x = x.next){

- 한 번의 순회를 모두 거쳐야 하기 때문에 o(n) 시간복잡도를 의미한다.

// 여기부터 Queue Opertaion이라고 명시되어 있다.

offer(E e)

- 마지막에 요소를 추가한다. 사실 add와 이것의 차이를 둬서 구분하는 이유를 모르겠다 둘 다 동일한 반환값에 동일한 기능을 하는데

- 찾아보니 인터페이스(Queue)의 기능 구현을 위해 작성이 된 코드이다. ㅋㅋ.... 

- 자바 구현 자체도 return add(E e)이다.

- offerFirst, offerLast 전부 동일한 사유이다.

peek()

- 가장 앞에 있는 값을 보여준다. null 체크 후 first의 값을 반환한다.

- peekFirst(), peekLast() 동일하다.

poll()

- 앞에서부터 이번에는 뽑아간다. 즉 인덱스 및 총사이즈가 변경되는 함수이다.

- 나의 구현 : null check 이후 first를 다음 first 로 바꿔주고 바꾸는 과정 중 잠시 데이터를 가지고 있다 리턴한다.

- first 를 받아서 unlinkFirst 함수를 실행한다. 이 함수는 first 자체를 null로 바꿔주는 코드가 있다. 왜? 가비지컬렉션에 도움이 되기 위해 이 코드를 작성했다고 되어있다. 와... 이런 부분까지 신경 쓰는지 몰랐다. 

- 이 함수에서는  놓친 부분이 많다. null을 이용해 gc에 도움을 주고, total의 수도 줄여주지 않았다. 이런 실수를 줄여야 하는데 후...

- o(1) 시간복잡도라고 믿어 의심치 않는다.

- pollFirst(), pollLast() 도 동일하게 구현되어 있다. pollLast()는 unlinkLast 함수이고 first와 동일한 로직이다.

pop(), push()

- stack을 표현하기 위해서 작성된 함수이다. 각각 addFirst , removeFirst 등의 함수를 각각호출한다.

remove(int index)

- 나의 구현 : index 가 0 인경우 혹은 size와 같은 경우는 바로 리턴을 해주는 최적화를 적용했다.

함수 내부적으로 count와 previous, current 3개 의 변수를 두어 index까지 조회하고 previous.next = current.next를 이용해 지워 주었다. 이렇게 보니 이렇게 되면 gc에서 삭제된 current를 즉각 회수하지 않는다. 계속 힙메모리를 차지하고 있는 반쪽 자리이다.

- 위에서 한번 언급한 node(index)를 이용해 해당 노드를 가져온다. 이렇게 해도 되는 이유는? 필드 내부적으로 전 그리고 다음 노드가 있기에 가능한 방법이다. unlink에서 역시나 삭제된 노드는 바로 null 처리를 통해 메모리 최적화가 진행되어 있다.

removeFirst(), removeLast() 모두 위에 언급한 unlinkFirst, unlinkLast를 이용해 사용된다.

사실 LinkedList 클래스 내부적으로 이 위의 함수들의 구현된 사항은 몇 줄 되지 않는다.

list-iterator, 직렬화, clone을 위한 코드가 400줄 이 넘는다. 그중 list-iterator에 대해 말하고 싶다.

위에서 언급한 ConcurrentModificationException 은 이 친구가 뱉어준다.

Iterator 가 만들어진 이후 remove 혹은 add를 이용해 수정을 한다면? 저 위의 에러가 뱉어진다.

checkForComodification을 이용해 modCount와 expectedModCOunt를 비교해 빠르게 에러를 뱉어준다. 위에서 add, remove 함수에서 전체 개수 외에 modCount 도 같이 체크해준 이유가 된다. 

LinkedList , ArrayList 내가 전에 사용하던 느낌이 맞다. 두 클래스 모두 다중 스레드에서는 안전하지 않는다.

무언가 를 추가하고, get()의 사용빈도가 적다? 여지없이 LinkedList를

그게 아닌 get(), set()의 빈도가 높다면 ArrayList의 선택이 타당하다.

CS 적으로 생각해 보자.

ArrayList는 하나의 긴 띠 안에 자료들이 오와 열을 맞춰 정렬되어 있다. 그러나 LinkedList는? 여기저기 흩뿌려져 있다. 하드웨어 적으로 이는 낭비를 의미할 수도 있다. 

다시 말해 속도의 측면 만 이 아닌 공간적 측면을 보더라도 어느 정도의 cost 가 각각 있다. 

Think Data Structures 책에서는 다음과 같이 언급한다.

 

1. 응용프로그램 의 실행 시간이 중요하다.

2. 응용 프로그램의 실행시간이 선택한 자료구조에 의존한다.

3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제크기가 충분히 크다. 

 

즉 작업하는 리스트 가 어마무시하게 크지 않다면 기대하는 성능을 얻기 어려울지도 모른다. 작은 문제에서는 이차 알고리즘 이 선형 알고리즘 보다 빠르기도 하고 선형 알고리즘이 상수시간 보다 빠르기도 하다.

LinkedList를 공부하면서 예전에 잠깐 읽은 블록체인 이 생각난다. 블록체인 또한 현재의 해쉬값 에는 전 해쉬 값이 포함되기 때문에 생각이 났다. 이런 기술에서도 이런 자료구조 가 접목 되어 있는 부분이 있어 자료구조 의 명확한 이해가 보다 중요해지는 거 같다.

그리고 최근 읽은 블로그 글이 생각난다.  C++, C 등의 언어가 다시 떠오르고 있다고 한다 왜? 클라우드 서비스를 이용하는 최신 서비스 들은 메모리의 성능, 하드웨어의 사용 은 즉각적인 비용으로 청구되기 때문에 이에 대한 최적화를 위해 migration 진행하는 곳도 많다는 Medium 블로그 글을 읽은 적이 있다. 

GC의 최적화 보다 메모리 관리를 직접 하는이 언어 들은 어느 정도 의 큰 데이터를 다뤄야 다른 언어에서 넘어갈 만큼 의 효율이 있는지도 궁금하다. 책에서는 어느정도 큰 데이터를 다루지 않는다면 유의미한 성능을 얻기 어렵다고 말한다. 그렇다면 다시 말해 그만큼 jvm 메모리에서 들고 있어줘야 한다는 소리인데. 이런 경험을 해보려면 도대체 얼마나 많은 양의 리스트를 들고 있어야 하는지 느낌도 없다.

이번 공부를 통해서 나름의 ArrayList와 LinkedList의 사용의 내 나름의 기준이 세워졌다. 전에 생각하던 이유에 몇 개 더 추가되진 않은 것 같지만 이렇게 java의 코드를 이렇게나마 볼 수 있어 좋은 시간을 보냈다.

코드 전문

특정 자료구조가 필요할 때 배열의 길이가 명확하지 않다면 주로 arrayList를 사용했다.
데이터를 앞에서부터 넣는다고 한다면 linkedList를 사용했다. (최신순으로 Queue의 느낌이 필요하다면)

깊이 있게 공부해 보고 싶어서 내가 제일 사용을 많이 하는 이 2개부터 파보려고 한다. 저 2가지 이유 이외에 보다 명확한 이유와 나 자신을 설득시키기 위해 오늘 공부해본 걸 작성해보고자 한다.

ArrayList를 그냥 내가 생각하는 느낌대로 Class를 작성해 구현해 보자.

(E 타입을 받아 제네릭 하지 않게 그냥 단순 숫자 배열로 만 작성해 보자.)

package datastructure;

public interface ArrayListInterface {
    // 뒤에부터 추가
    boolean add(int num);
    // 인덱스 에 의한 추가
    boolean add(int num,int idx);
    // 처음 발견한 숫자 삭제
    boolean removeByNum(int num);
    // 인덱스 에 의한 삭제
    boolean removeByIdx(int idx);
    // 인덱스 로 값 가져오기
    int get(int idx);
    boolean isEmpty();
    boolean contains(int num);
    int size();
}

ArrayList라고 하면 이 정도로 내가 제일 많이 사용하는 것 같다.

구현

package datastructure;

import java.util.Arrays;

public class GuiwooArrayList implements ArrayListInterface{
    private int[] guiwoo;
    private int total;

    public GuiwooArrayList() {
        this.guiwoo = new int[10];
        this.total = 0;
    }
    @Override
    public boolean add(int a){
        expendArray();
        guiwoo[total++] = a;
        return true;
    }

    @Override
    public boolean add(int num, int idx) {
        if(idx >= this.size()) throw new ArrayIndexOutOfBoundsException();
        expendArray();
        int[] temp = new int[this.size()-idx-1];
        System.arraycopy(guiwoo,idx,temp,0,temp.length);
        System.arraycopy(temp,0,guiwoo,idx+1,temp.length);
        guiwoo[idx] = num;
        total++;
        return true;
    }
    private void expendArray(){
        if(this.size() == guiwoo.length){
            int[] next = new int[this.size()*2];
            System.arraycopy(this.guiwoo,0,next,0,guiwoo.length);
            guiwoo = next;
        }
    }

    @Override
    public boolean removeByNum(int num){
        int idx = -1;
        for(int i=0;i<this.size();i++){
            if(num == guiwoo[i]){
                idx = i;
                break;
            }
        }
        return this.removeByIdx(idx);
    }
    @Override
    public boolean removeByIdx(int idx){
        if(idx == -1) throw new IllegalArgumentException("없어요");
        int[] temp = new int[this.size()-idx-1];
        System.arraycopy(guiwoo,idx+1,temp,0,temp.length);
        System.arraycopy(temp,0, guiwoo,idx,temp.length);
        total--;
        return true;
    }
    @Override
    public int get(int idx){
        if(idx >= this.size()){
            throw new ArrayIndexOutOfBoundsException("허용 인덱스 범위  초과");
        }
        return this.guiwoo[idx];
    }
    @Override
    public boolean isEmpty(){
        return this.size() == 0 ;
    }

    @Override
    public boolean contains(int num) {
        for(int target : guiwoo){
            if(target == num) return true;
        }
        return false;
    }

    @Override
    public int size(){
        return this.total;
    }
    public String toString(){
        return Arrays.toString(this.guiwoo);
    }

}

테스트

package datastructure;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class GuiwooArrayListTest {
    @Test
    void addTest(){
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        Assertions.assertSame(target,guiwoo.size());
    }

    @Test
    void addNumByIdx(){
        int targetNum = 100;
        int targetIdx = 5;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < 5; i++) {
            guiwoo.add(i);
        }
        Assertions.assertThrows(ArrayIndexOutOfBoundsException.class,
                ()->guiwoo.add(targetNum,targetIdx));
    }

    @Test
    void addNumByidx(){
        int targetNum = 100;
        int targetIdx = 2;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < 5; i++) {
            guiwoo.add(i);
        }
        guiwoo.add(targetNum,targetIdx);
        Assertions.assertEquals(guiwoo.get(targetIdx),targetNum);
        Assertions.assertEquals(guiwoo.size(),6);
    }

    @Test
    void removeTestByNumber() throws Exception{
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        guiwoo.removeByNum(6);
        Assertions.assertSame(guiwoo.size(),target-1);
        guiwoo.add(15);
        Assertions.assertSame(15,guiwoo.get(guiwoo.size()-1));
    }

    @Test
    void removeByIdx(){
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        guiwoo.removeByIdx(6);
        Assertions.assertSame(7,guiwoo.get(6));
    }
}

스프링 부트가 아닌 그냥 자바 프로젝트라서 라이브러리에 junit을 추가해줘서 테스트 코드를 돌렸다.

나름 예쁘게 작성해보고 싶어서 30분 정도 투자해서 코드를 작성한 것 같다.

특별할 것 없이 최초 생성 시 10 개의 배열 사이즈를 고정해서 사용하는 로직이다. 배열의 범위가 가득 찾을 때 확장을 시켜주는 로직이다.

이중 System.arrayCopy를 정말 많이 사용했는데 한번 살펴보자.

먼저 설명을 읽어보자.

length의 숫자만큼 src에서 가져와 dst로 복사한다.라는 첫 번째 문단이 있고 두 번째 문단을 보면 내 코드의 문제점 이 보인다.

동일한 src와 dst를 참조할 경우 자체적으로 copy를 실시해 내부적으로 수행이 된다는 의미이다. 

즉 제거할 때 capacity의 변화가 없는 경우 라면 나의 코드처럼 temp 변수를 사용할 이유가 없어지는 것이다.

removeByIdx의 함수만 수정 후 테스트를 돌려보자.

이렇게 테스트 가 잘 통과되니 기분이 좋다.

계속해서 arrayCopy를 읽어보자. 어느 경우에 안되는지 에 대한 예시를 들어주고 있다. 배열이 아닌 경우, 인덱스 의 숫자가 - 인 경우 등등 (ArrayStroeException, IndexOutOfBounds,...) 

@IntrinsicCandidate

함수를 보면 IntrinsicCandidate 어노테이션과, native라는 생전 처음 보는 친구들이 달려있다. 살펴보자.

instrinsic 내장함수 란 각 언어마다 컴파일러, 혹은 인터프리터 등이 있는데 이 두 친구들이 특별하게 핸들링하는 함수들을 지칭한다.

즉 최적화된 내장함수들을 의미한다는 소리이다.

다시 말해 low 한 레벨 어셈블리 어 같은 언어로 jvm에서 호출하는 것을 의미하는 것 같다. 

다양한 글들을 읽어보면 significant performance benefits이라고 한다. 하나의 테스트를 예로 보여주는데 sqrt를 100k 번 하는 클래스 호출 함수와 내장 함수 의 속도 비교를 보여주는 데 무려 35%가량의 속도 차이가 발생한다.

심지어 JVM 마다 호출하는 경우가 있고 아닌 경우도 있다고 한다. 즉 저 어노테이션 이 있으면 low level 코드를 불러 최적화된 성능을 보여준다는 소리임과 동시에, 다른 JVM, OS 등에서 실행했을 경우 다른 성능을 보여줄 수 있다는 의미이기도 하다. 

조심해서 사용해야 할 이유가 있다는 소리이다. 이런 low level 문제가 발생된다면 버그 찾기가 정말 어려워질 것으로 보인다. 

한 블로그 포스팅에서는 우리가 종속성 및 런타임을 최신 상태로 유지해야 할 이유라고 말한다.

native

java native interface에서 구현된 함수를 지칭할 때 이 예약어를 사용한다.

C로 작성한 main에서 호출해보려고 이것저것 시도하다가 실패했다. 추후 go 언어로 함수하나 작성해서 컴파일해서 해볼 예정이다.

dll 파일 혹은 so 확장자의 파일이 필요하고 이걸 lib에 추가해야 System.load 가 가능한 것으로 보이는데 추후 도전해보자 오늘 목표로부터 너무 멀어졌다.

위와 같은 방식으로 arrayList를 구현해 보았다. 실제 구현된 코드를 보면서 차이점을 한번 살펴보자.

ArrayList를 가서 읽어보자.

가장 첫 줄에 List 인터페이스 의 크기조절 이 가능한 자료구조라고 설명 되어 있다. null을 포함한 모든 object를 받을 수 있으며 size manipulating 한다고 작성되어 있다. vector 자료구조 와 다른 점이라고 한다면 단순 동기화를 지원하지 않는다는 점이다.

저 단순한 동기화 지원하지 않는 것 때문에 arrayList의 자료구조 가 더 생긴 건가 라는 의문이 생긴다.

찾다가 흥미로운 글이 있어 작성한다. arrayList와 vector의 차이점 중 뚜렷한 부분 중 하나는 바로 최적화 부분인데 확장을 함에 있어

arraylist는 >>1 이 연산자를 이용해 50% 를 확장, vector는 100% 를 확장한다.

Synchronized 동기화는 좋은 작업인가 에 대한 의문점을 가질 필요가 있다. 물론 동기화 가 보장된다면 좋다고 생각할 수 있다. 그러나 동기화를 하는 데 있어 비용이 든다. 시간 혹은 메모리가 이 말은 즉 느리다는 소리다. 지난번 스트링 버퍼와 스트링 빌더 의 차이에서 볼 수 있듯이 동기화에 드는 비용은 커지면 커질수록 확연한 속도차이가 발생한다.

단일 스레드 의 경우 이런 동기화 비용을 지불할 필요도 없을뿐더러 위와 같은 확장성에 있어서도 불필요한 소요가 생긴다.

이런 부분에서 본다면 내가 작성한 커스텀 arrayList 매번 *2 만큼 확장하는데 말할 것도 없이 최적화가 필요한 부분이다.

이런 부분 때문에 새로운 프로젝트 라면 항상 arrayList를 사용할 것을 권장한다.

동기화 부분 은 컬렉션 함수로 아래와 같이 제공되어 arrayList 또한 동기화 작업을 진행할 수 있다.

Collections.SynchronizedList(arrayList);

add(int n) vs add(E e)

동일한 방법으로 뒤에 추가하면서 total size를 이용해가면서 추가한다. 사이즈 가 같다면 grow()라는 함수를 이용해 capacity를 증가시켜 준다. 이렇게 뒤로 항상 추가를 하게 된다면 평균 constant 시간 즉 o(1)의 시간 값을 소모한다고 판단해도 좋을 것 같다. 

왜? 이미 증가한 배열에 [total++] 이런 식으로 디렉트로 넣어주면 된다. 

*2 만큼의 사이즈 증가로 인한 속도의 차이가 궁금하니 100k 기준으로 테스트 코드를 돌려보자.

몇 번을 돌려도 그렇게 유 의미한 차이는 나지 않는다. 동일한 로직을 이용했기 때문인가 최적화 부분 에서 의 차이를 검증하기 위해

BenchMarkTest를 이용해 보자.

이렇게 벤치마크 추가해 주고(jmh.core, jmh.generator.annprocess) 

간단한 클래스 만들어서 돌려주자. (추후 benchmark 블로그 포스팅도 하겠다.)

package datastructure;

import org.openjdk.jmh.annotations.*;

import java.util.ArrayList;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 10)
@Fork(1)
@Measurement(iterations = 100)
public class GuiwooBenchMark {

    @Param({"10","1000000"})
    public int size;

    @Benchmark
    public void arrayList(){
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
    }
    @Benchmark
    public void arrayListCustom(){
        GuiwooArrayList list = new GuiwooArrayList();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
    }
}

mili 초에서 차이가 별로 없기에 나노 초 재확인했다. 여전히 나의 custom list 가 더 빠른 것이 확인된다. 

grow()와 expend() 함수 의 최적화 차이 여부로 판별된다. 즉 최적화 간에 호출되는 함수 들에 따라 arrayList의 함수가 더 느리다는 결론이 나왔지만 아직 찝찝하다.

add(E el, int idx)

다만 이렇게 인덱스에 의해 추가가 되는 경우는 생각을 해보아야 한다. 중간 인덱스에 끼이면 arrayCopyOf를 사용해 중간에 추가해서 밀어 넣어주는 방식이다. 중간검증을 통해 grow 여부를 판별하고, 밀어 넣어주기 때문에 copy 될 배열의 for loop 한번 돌 시간이 필요하기 에 o(n) 시간이 소요된다.

get(int idx)

그렇다면 다시 말해 이렇게 get으로 뽑아온다면? 배열에서 디렉트로 뽑아오는데 당연히 o(1)의 속도를 보여준다. 

isEmpty(), size()

이 두 친구 들은 클래스 내부적으로 필드를 가지고 있어 바로 호출하면 되기 때문에 o(1)의 속도를 보여준다.

remove(E el)

내가 작성한 것과 동일하게 최초발견된 오브젝트를 삭제한다. object 찾는 for loop 한번, 지우는 로직을 위해 arrayCopy 한번 

통상 o(n) 시간복잡도를 가질 것으로 보인다.

remove(E el, int idx)

o(n) 시간복잡도를 가질 것이다. for loop을 이용해 탐색, arrayCopy를 통해 밀어줄 것들 복사해서 밀어준다면 동일한 시간복잡도가 나와야 한다. 

contains(E el)

o(n) 시간복잡도를 가질 것이다. for loop을 이용해 탐색을 한다 다만 흥미로운 점은 arrayList 상에서는 indexOf(E el)을 이용해 > 0을 이용해 반환 값을 결정한다.

위에 구현한 함수 상에서 비슷한 로직을 이용해 arrayList 함수 또한 구현되어 있다. 이외에 궁금한 게 있으니 api documentation을 보자 가독성이 20000배 좋다.

놓친 부분으로는 addAll, forEach(), iterator(), etc... (https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/ArrayList.html)

list의 capacity 즉 size 최적화를 위한 trimToSize 도 존재한다. 신기한 함수다. 얼마큼 유동적인 listSize를 운용해야 메모리 낭비를 줄이기 위해 이 함수를 사용할지 느낌조차 없다.
(추가적으로 검색해보니 늘어난 배열에 대해서 가바지 컬렉터 에서 수거하거나, 줄이는 신비한 묘책이 없기때문에 이러한 함수가 제공된다.)

다만 웃긴 점이 하나 있는데 retainAll이라는 함수에서는 파라미터로  받는 컬렉션을 제외한 나머지를 삭제한다. 이때 batchRemove()라는 함수이름을 사용하지만, addAll 은 이런 게 없어서 아쉬웠다. removeAll, retailAll 이 2 경우 모두 사용하기 위해서 이렇게 함수로 뺀 것처럼 보이지만. 아쉬운 부분이긴 하다.

ArrayList 하나 알아보기 위해서 이렇게 시간을 오래 들여서 보니 부족한 게 너무 많아서  어디부터 손봐야 할지 모르겠다.. 

어렴풋이 나마 느꼈던 것이 맞았다는 기분이 들어 좋았고, vector 같은 쓰면 안 되는 이유, synchronized 하지 않는 이유 등 모른 부분을 보다 명확히 알게 돼서 나름 보람찬 공부였다.

상수시간 을 가지는 add, size 등 을 자주 사용하게 된다면 비교할것도 없이 ArrayList 를 사용하면 된다. 

그게 이 ArrayList 자료구조 가 의 존재 이유라고 생각된다.

트리 내에 존재하는 엣지 를 타고 가장 합이 높은 부분을 구하는 문제이다. 어제와 유사한 문제라고 생각해서 비슷하게 접근했으나 머리가 대차게 깨져버렸다.

어제 와 유사한 코드로 접근하였으나 - 값의 여부와 한가지 패스 안에서는 길을 타고 다시 거슬러 올라오면 안 된다는 부분에서 신경이 쓰여 preorder를 사용했다. 중복을 처리해줄 방법이 없어 생각보다 애를 많이 먹었다... 

if를 이용해서 틀릴 때마다 처리를 해주었으나. 99개 테스트 케이스에서 56 이 한계였다. preOrder, postOrder 전부 실패했다. prefix를 이용하기 위해 리스트 넘기는 방법, max를 이용해 현재 비교대상을  3번 비교하는 방법 전부 실패했다.

뭔가 잡힐듯 말듯한데 자꾸 실패해서 분하다...

약 1시간 정도 풀다가 실패해서 discuss를 보고 오니 내가 구해야 할 명확한 목적을 알고 나니 풀이가 쉬워졌다.

머리 깨진 풀이

class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        max = Integer.MIN_VALUE;
        helper(root, list);
        int total = list.get(list.size()-1);
        for (int i = 0; i < list.size()-1; i++) {
            max = Math.max(Math.max(total,total-list.get(i)),max);
        }
        return max;
    }

    public void helper(TreeNode node, List<Integer> list){
        if(node == null) return;
        helper(node.left, list);
        int previous = list.size() == 0 ? 0 : list.get(list.size()-1);;
        list.add(previous+node.val);
        max = Math.max(max,node.val);
        helper(node.right,list);
    }
}

트리 순회를 위해 helper를 선언해 중위 순회를 선택했다. 이유는 후위 순회를 하게 된다면 리프부터 타고 올라가야 하는데 이 기준점을 정해주기 가 생각보다 어려웠다. prefix를 사용해야 한다는 압박감 때문 인지. 후위 순회를 하게 되니 오류가 많이 생겼다. 

디스커스에서 읽고 바로 풀이 방법을 바꾼 힌트 를 보자.

우리가 구해야 할 4가지 경우의 수가 있다.

1. 왼쪽 패스 + 현재 값

2. 오른쪽 패스 + 현재 값

3. 왼쪽 패스 + 오른쪽 패스 + 현재 값

4. 현재 값 자체로 위 값보다 큰 경우

이 4 가지를 명확히 하고 갔어야 했는데 이게 안되니 null 이 여러 번 들어간 깊이 있는 트리인 경우 오답이 나게 되는 것이다. ㅠ

위 4가지 힌트를 얻어서 작성한 풀이법이다. 

class Solution{
	int max = Integer.MIN_VALUE;
    
	public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    public int helper(TreeNode node){
    	if(node == null) return Integer.MIN_VALUE;
        int left = helper(node.left);
        int right = helper(node.right);
        
        max = Math.max(max,Math.max(left,right));
        max = Math.max(max,node.val);
        max = Math.max(max,node.val+Math.max(left,0)+Math.max(right,0));
        return node.val + Math.max(0,Math.max(left,right));
    }
}

max 값을 비교할 Integer를 선언해주고 , 현재 값이 - 값이라면 무조건 0으로 초기화시켜주었다. 

left 패스, right 패스를 각각 구하고 현 max와 패스의 합 +현재 값

그리고 현재 값에 패스 값 중 높은 값을 다음으로 넘겨주는 재귀를 작성하였다. 

class Solution{
	int value = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        int temp = process(root);
        return Math.max(temp, value);
    }

    public int process(TreeNode head){
        if(head == null){
            return 0;
        }
        int leftTree = Math.max(0, process(head.left));
        int rightTree = Math.max(0, process(head.right));
        value = Math.max(value, leftTree + rightTree + head.val);
        return Math.max(leftTree, rightTree) + head.val;
    }
}

이 사람도 보면 참 깔끔하게 작성한 거 같다. 왼쪽 패스, 오른쪽 패스를 나누고 현재 값의 맥스를 왼쪽 오른쪽의 합과 현재 값을 이용하고 다음 재귀로 왼쪽 오른쪽 중 큰 값을 현재 값에 더해 넘겨준다.

maxValue = Math.max(maxValue, left + right + node.val);

작성할 때 난감 했던 부분이다. maxVaule를 현재 와 왼쪽 오른쪽 그리고 노드의 값을 합친 값으로 업데이트를 하는 것이 아닌가.

문제의 포인트를 잡지 못해서 이상한 풀이법으로 나가 결국 맞지 못한 문제였다.

주어진 이진트리에서 하나의 엣지 를 잘라서 각각의 서브 트리를 만들 때 두 서브 트리 합의 곱이 가장 큰 값을 리턴하는 문제이다.

10**4 까지 노드 가 주어진다고 가정한다면 9999개 의 엣지가 생길 수 있고 완탐 때려도 충분히 가능하다고 생각해 규칙을 찾기 시작했다. 

주어지는 트리가 이진트리 라고 가정한다면 최초 만나는 이중 노드에서 각각의 서브 트리 연산을 진행해 최소 최대 값을 구해 곱해주면 된다고 생각했다.

첫 번째 코드를 보자.

class Solution {
    int total = 0;
    int module = (int) Math.pow(10,9)+7;
    public int maxProduct(TreeNode root) {
        if(root == null) return 0;
        TreeNode hasSubNodes = getTotalBeforeSplit(root);
        
        int subTotalLeft = getSubTotal(hasSubNodes.left);
        int subTotalRight = getSubTotal(hasSubNodes.right);
        total += Math.min(subTotalLeft, subTotalRight);
        return (total * Math.max(subTotalLeft,subTotalRight))%module;
    }
    public int getSubTotal(TreeNode node){
        int subTotal = 0;
        if(node == null) return subTotal;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(node);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            subTotal += cur.val;
            if(cur.left != null) q.offer(cur.left);
            if(cur.right != null) q.offer(cur.right);
        }
        return subTotal%module;
    }

    public TreeNode getTotalBeforeSplit(TreeNode root){
        total = (total+root.val)%module;
        if(root.left != null && root.right == null){
            return getTotalBeforeSplit(root.left);
        }
        if(root.right != null && root.left == null)
            return getTotalBeforeSplit(root.right);
        return root;
    }
}

getTotalBefoeSplit을 이용해 최초 만나는 이중 노드까지 의 합과 현재 노드의 위치를 기록했다. 

getSubTotal을 이용해 좌우 값을 모두 연산해 주었다. 

테스트 코드는 잘통과 된다. 바로 제출했다. 실패 ㅠㅠ

내 로직의 문제점 이 발생했다. 편향 트리인경우 내 로직이 작동하지 않는다... 노드를 끝까지 탐색해 결국 0이라는 답이 나온다. 

if를 넣어 편향 트리인 경우를 핸들링하려고 했으나 깊이를 알 수 없기 때문에 불가능하다는 결론에 도달.

만약 배열에서 내가 이걸 계산한다면 어떻게 할까 고민 하다 보니 prefix를 이용한 배열을 이용해 구한다는 생각에 도달했다.

 1. 모든 노드 의 합을 구한다.

2. 모든 노드 의 합을 구하는 히스토리를 입력해 prefix를 작성한다.

3. prefix 기준으로 각 서브트리의 합은 prefix , 모든 노드의 합 - prefix이다.

로직 이 보다 명확해졌다.

사실 long 타입을 쓰기 싫어서 모듈을 각각 연산마다 해주려고 했더니 prefix 본질에 어긋나 버린다. 만약 1e9 + 7의 값이 넘어가 버린다면 모듈 된 값이 prefix에 기입되어 명확한 토털 값 계산이 되질 않는다. 

이렇게 두개의 값을 이용해 차이 값을 구할때 prefix 합을 염두해 두고 풀이법 을 생각해보는것도 좋은것 같다.