악역영애의 개발일지

연결리스트가 팰린드롬 구조인지 판별하라.

input : 1 -> 2 -> 3 -> 2 -> 1

output : true

ListNode 란 ? java에서 기본적으로 제공하는 형태가 아니고 leetCode에서 제공하는 형태이다.

문제를 보면

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
    
    }
}

ListNode가 어떤 클래스인지 명시해준다.

int val 이라는것을 값으로 쓰고

next 라는것으로 다음 노드를 지칭한다.

해당 자료형이 java 에서 내가모르는 자료형이 있던가? 고민하지말자.

일단 ListNode는 List<String> 과 같은 ArrayList완 다르다.

index를 쓸수없고, ListNode 에 [1,2,3] 이 담겨있다고하면 얘네는 앞에서부터 순차적으로 가져올수있다.

또한 가져올때 head 라는 요소를 사용하여 순차적으로 가져올수있다. head는 해당 리스트의 시작을 나타내는 포인터 개념이다.

이것은 한번 사용하면 오염되어, 다음 문제때 head 즉 시작위치를 알 수없게 되기때문에 사용할때 유의해야한다.

해당 문제는 ListNode가 팰린드롬인가? 를 묻는 문제이기 때문에 해당 리스트를 뒤집은 결과가 해당리스트와 동일한지 체크하겠다.

리스트 추출방법 1 - Stack

Stack 을 활용하여 리스트를 추출해보자.

class Solution {
    public boolean isPalindrome(ListNode head) {
    	Stack<Integer> stack = new Stack<>();
    }
}

이런식으로 선언하면 안된다고 책에 써있긴 했지만 일단, ListNode 를 담을 스택을 선언해준다.

그리고 파라미터로 들어온 head, 즉 팰린드롬인지 알고싶은 데이터를 사용하면 head위치가 손상되어버리기때문에

별도 ListNode에 해당데이터를 넣어준다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        LisNode node = head;

    }
}

이제 node 에 있는 값을 순서대로 stack 에 쌓아준다

ListNode 는 index를 쓸 수 없고 순차적인 접근밖에 지원되지 않으므로 while문을 써준다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        LisNode node = head;

        while(node != null) {
            stack.add(node.val);
            node = node.next;
        }
    
    }
}

이렇게 담은 node와 head가 같은지 비교해준다

만약 head.val 과 stack.pop 이 한번이라도 같지않을 경우에는 무조건 팰린드롬이 아니기때문에 false를 보내주고

해당 if문에 걸리지않을 동안에는 계속 순차적으로 비교해야하기때문에 next를 처리해준다

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        LisNode node = head;

        while(node != null) {
            stack.add(node.val);
            node = node.next;
        }

        while (head != null) {
            if (head.val != stack.pop()) {
            	return false;
            }
            head = head.next;
        }
    	return true;
    }
}

stack 은 후입선출이기때문에 stack.pop() 처리를 하면 스택에서 해당값을 꺼내고 해당값은 없애준다.

그래서 얘도 별도로 index 를 지칭해주지않아도 된다.

if문에 걸리지않았다면 true 이므로 true 반환하고 끝.

리스트 추출방법 2 - Deque

Stack 보다 빠르게 처리될 수 있는 Deque를 사용해보자.

여기서의 Deque 구현은 LinkedList로 했는데, 다른 식으로 구현이 가능하다.

하지만 현재는 연결리스트를 공부하고있으므로 LinkedList로 구현했다.

class Solution {
    public boolean isPalindrome(ListNode head) {
    	Deque<Integer> deque = new LinkedList<>();
    }
}

그리고 Stack 과 동일하게, 별도 node를 만들어줘서 head를 저장할 필요가 없다.

우리는 Deque 의 앞뒤를 비교할것이기때문에 !

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> deque = new LinkedList<>();

        while(head != null) {
            deque.add(head.val);
            head = head.next;
        }
    
    }
}

deque 에서도 add를 써준다.

Deque 는 앞/뒤에서 모두 추출 가능하므로 Deque 의 맨앞 & 맨뒤를 비교하면 팰린드롬인지 알수있다.

그리고 만약 해당 리스트가 짝수면 list.size 는 0이 되겠지만, 홀수라면 list.size = 1 이 되어버리므로, 1 이하였을때 종료되도록 해주자

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> deque = new LinkedList<>();

        while(head != null) {
            deque.add(head.val);
            head = head.next;
        }
        
        while(!deque.isEmpty() && deque.size() > 1 ) {
        	if(deque.pollFirst() != deque.pollLast()) {
            	return false;
            }
        }
    	return true; 
    }
}

이렇게하면 deque가 empty 이면 (짝수) 종료되고, size가 1이어도 (홀수) 종료된다.

pollFirst() , pollLast() 는 각각 값을 꺼내오고 해당값을 탈출시키기때문에 deque 에서 값이 계속 빠져나간다.

Deque 문법

• 앞쪽에서 작업:
  • addFirst(E e) - 맨 앞에 요소 추가
  • removeFirst() - 맨 앞의 요소 제거
  • peekFirst() - 맨 앞의 요소를 반환 (제거하지 않음)
• 뒤쪽에서 작업:
  • addLast(E e) - 맨 뒤에 요소 추가
  • removeLast() - 맨 뒤의 요소 제거
  • peekLast() - 맨 뒤의 요소를 반환 (제거하지 않음)
• 일반 큐 작업:
  • offer(E e) - 맨 뒤에 요소 추가 (큐의 add와 동일)
  • poll() - 맨 앞의 요소 제거 및 반환
  • peek() - 맨 앞의 요소를 반환 (제거하지 않음)
• 스택 작업:
  • push(E e) - 맨 앞에 요소 추가 (스택의 push와 동일)
  • pop() - 맨 앞의 요소 제거 및 반환 (스택의 pop과 동일)

기존의 stack 에서는 본체 node와 stack 을 비교했다면 deque 를 사용할 경우 해당 Deque 하나에서 앞뒤를 구분한다.

리스트 추출방법 - Runner

팰린드롬 연결 리스트 문제를 푸는 정공법은 러너기법이라고 한다.

ListNode 2개를 만들어서 한개는 .next.next 나머지한개는 .next 를 하게해서 빠른러너/느린러너를 생성한다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
    }
}

두 ListNode 모두 head 를 담아놓고 초기화를 시켜준다.

그리고 fast 가 2칸 (.next.next)을 가고 slow가 1칸 (.next)을 가게 해준다.

그러면 결국에는 fast가 끝에다다랐을때 slow는 딱! 중간에 위치하게된다.

하지만 이것은 홀수의 이야기이고, 만약 짝수일때는 이미 .next 까지만 값이 있고 .next.next 에는 값이없다!

때문에 홀수/짝수를 모두 생각해서 조건을 넣어준다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        
        while(fast != null && fast.next != null {
            fast = fast.next.next;
            slow = slow.next;
        }
    }
}

fast == null 이면 홀수로 끝났고 fast != null 이지만 fast.next == null 일때는 짝수로 끝나기때문에 저렇게 조건을 해준다.

그런데 여기까지만처리해주면 여전히 slow는 1칸을 마저 가지못하고 남아있기때문에 한칸을 마저 옮겨준다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        
        while(fast != null && fast.next != null {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        if (fast != null) {
        	slow = slow.next;
        }
        
    }
}

이렇게까지 되면 fast 는 head 를 모두 끝냈고, slow 는 head의 딱 정중앙에 있는것이다.

fast 는 slow를 구하기위해 희생된 느낌이다.

자 이제 배열의 정중앙에 있는 slow를 이용해서 팰린드롬 여부를 확인해보자.

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        while (fast != null && first.next != null) {
            fast = fast.next.next;
            slow = slow.next
        }

        if (fast != null) {
            slow = slow.next;
        }

        ListNode rev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = rev;
            rev = slow;
            slow = next;
        }
    }
}

여기서 뇌정지가 왔는데 하나하나 살펴보자.

첫번째 루프

ex) [1, 2, 3, 4, 3, 2, 1]

ListNode rev = null;
while (slow != null) {
    ListNode next = slow.next; // next = 3
    slow.next = rev;  // slow.next = null
    rev = slow;     // rev = 4
    slow = next;    // slow = 3
}

현재 slow : 4 -> 3 -> 2 -> 1

next 에 slow.next 를 담아둔다

slow.next = rev;

이 행위로 slow.next 를 null로 만들어줬다.

지금 slow는 4 -> null 인것이다!!! 

왜냐면 현재 slow는 냅두고 slow.next 를 덮어씌우기 해버렸으니까!

rev = slow;

이걸로 rev 에 현재 slow. 즉 4 -> null 를 담았다.

slow = next;

아까 저장해둔 slow.next 를 현재 slow 에 넣어준다.

그러면 4 -> null 이 아니라 다시 3 -> 2 -> 1 이 된다.

결국 rev : 4 -> null / slow : 3 -> 2 -> 1

두번째 루프

[1, 2, 3, 4, 3, 2, 1]

ListNode rev = null;
while (slow != null) {
    ListNode next = slow.next; // next = 2
    slow.next = rev;  // slow.next = 4
    rev = slow;     // rev = 3
    slow = next;    // slow = 2
}

다시 next 에 2 -> 1  넣어두고 slow.next = 4 -> null 을 해뒀다.

이때 slow는 3 -> 4 -> null 이 된다 !! 

그럼 그것을 rev 에 넣고  slow 에는 2 -> 1 을 (slow.next)를 넣어준다.

rev : 3 -> 4 -> null

slow : 2 -> 1

세번째 루프

[1, 2, 3, 4, 3, 2, 1]

ListNode rev = null;
while (slow != null) {
    ListNode next = slow.next; // next = 1
    slow.next = rev;  // slow.next = 3
    rev = slow;     // rev = 2
    slow = next;    // slow = 1
}

slow.next = rev 를 해주면 현재 slow 는 2 -> 3 -> 4 -> null

rev : 2 -> 3 -> 4 -> null

slow : 1

네번째 루프

[1, 2, 3, 4, 3, 2, 1]

ListNode rev = null;
while (slow != null) {
    ListNode next = slow.next; // next = null
    slow.next = rev;  // slow.next = 2
    rev = slow;     // rev = 1
    slow = next;    // slow = null
}

rev : 1 -> 2 -> 3 -> 4 -> null

slow : null

이렇게 루프를 돌아서 연결리스트의 반절 ~ 후반부를 rev에 저장했다.

뒤쪽에 쌓이는게아니라 앞에 쌓이는게 어색하지만.. 여튼 완료. 이제 이것과 원래 head를 비교해보자

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        ListNode rev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = rev;
            rev = slow;
            slow = next;
        }

        while (rev != null) {
            if (head.val != rev.val) {
                return false;
            }
            rev = rev.next;
            head = head.next;
        }
        return true;
    }
}

어짜피 rev는 head의 반절만 있으니까 while 문 조건으로 rev가 null이면 빠져나오게했다

왜이렇게 어렵게해서 만든담?!! 속도때문이지만... ㅠㅠ

문제 링크 : https://leetcode.com/problems/two-sum/description/

처음 submit 한 코드

public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        boolean isBreak = false;
        for (int i = 0; i < nums.length; i++) {

            if (isBreak) break;

            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    isBreak = true;
                    break;
                }
            }
        }
        return result;
    }
}

불필요한 break가 많다. 전체적으로 보기 불편하다

개선된 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        boolean isBreak = false;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return result;
    }
}

바로 return 시켜버리면 된다

폴더 depth 파악문제

문제 링크 : https://leetcode.com/problems/crawler-log-folder

내가 푼 문제

class Solution {
    public int minOperations(String[] logs) {
        int result = 0;
        for (String log : logs) {
            if (log.equals("./")) {
                result += 0;
            } else if (log.equals("../")) {
                if (result <= 0) {
                    result = 0;
                } else {
                    result -= 1;
                }
            } else {
                result += 1;
            }
        }
        return result;
    }
}

if 밭이다 밭.

이걸 개선

class Solution {
    public int minOperations(String[] logs) {
        int depth = 0;
        for (String log : logs) {
            if (log.equals("../")) {
                if (depth > 0) {
                    depth--;
                }
            } else if (!log.equals("./")) {
                depth++;
            }
        }
        return depth;
    }
}

차라리 상단에서 depth 를 -- 주고 ./ 가 아닐때만 ++ 하면 됨

주어진배열에서 제일 많이 나온 값을 도출

array = {1,3,3,4,4,4,4,5}

= 4

int[] array = {1};

        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
		
        if (array.length == 1) return array[0];
        
        int[] list = array;
        int t = 1;
        for (int i = 0 ; i<array.length ; i++) {
            for(int j = 1 ; j < list.length-1 ; j ++) {
                if (list[j] == array[i]) {
                    t++;
                    map.put(list[j],t);
                }
            }
            t = 0;
        }

        int test = 0;
        for(int key : map.keySet()) {
            if (map.get(key) > test) {
                test = map.get(key);
                answer = key;
            } else if (map.get(key) == test) {
                answer = -1;
            }
        }
        return answer;

이렇게 했는데 한 케이스만 안됐다.

맵으로 어케안되나? 생각하던 중 아래 케이스를 발견했다.

성공적인 케이스

import java.util.*;
class Solution {
    public int solution(int[] array) {
        int maxCount = 0;
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int number : array){
        
           // count = 맵에 저장된 number의 카운트+1 혹은 0 +1
            int count = map.getOrDefault(number, 0) + 1;
            
            //최초 & 기존에 저장된 number를 다시만났을때 오는 곳
            if(count > maxCount){
                maxCount = count;
                answer = number;
            }
            else  if(count == maxCount){
            //count = 1 즉 해당글자가 첫번째 글자일때 들어오는 공간
                answer = -1;
            }
            map.put(number, count);
        }
        return answer;
    }
}

캬

처음엔 아스키코드로 더하고뺄까 했다.

// a ~ z 97 ~122
// A ~ Z 65~90

그런데 Charater 를 사용하면 손쉽게 확인할수있었다..

class Solution {
    public String solution(String my_string) {
        String answer = "";
       for(int i = 0; i < my_string.length() ; i ++) {
           if (Character.isUpperCase(my_string.charAt(i))) {
               answer += Character.toLowerCase(my_string.charAt(i));
           } else {
               answer += Character.toUpperCase(my_string.charAt(i));
           }
       }
        return answer;
    }
}

다른 풀이

class Solution {
    public String solution(String my_string) {
        String answer = "";
        for(int i=0; i<my_string.length(); i++){
            char c = my_string.charAt(i);
            if(Character.isUpperCase(c)){
                answer += String.valueOf(c).toLowerCase();
            }else{
                answer += String.valueOf(c).toUpperCase();
            }
        }
        return answer;
    }
}