Eunbibibi

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

이진탐색 두번 시행

1. 시작지점 찾기

2. 끝나는 지점 찾기

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int start = -1;
        int end = -1;

        int left = 0;
        int right = nums.length - 1;
        // start 위치 찾기
        while (left <= right) {

            int mid = (left + right) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            if (nums[mid] == target) {
                start = mid;
            }
        }

        //end 위치 찾기

        left = 0;
        right = nums.length - 1;
        while (left <= right) {

            int mid = (left + right) / 2;

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            if (nums[mid] == target) {
                end = mid;
            }
        }

        return new int[]{start, end};
    }
}

https://leetcode.com/problems/array-nesting/description/

public int arrayNesting(int[] nums) {
        // 방문했는지 체크하는 임시배열 -1:방문 / 0:방문안함
        int[] tmp = new int[nums.length];
        int res = 0;
        
        for (int i = 0; i < nums.length; i++) {
            //방문한 원소면 스킵하기
            if (tmp[i] == -1) continue;
            
            int cnt = 1;    //방문한 원소 갯수 저장하는 변수
            tmp[i] = -1;
            int next = nums[i]; //다음 방문할 인덱스

            while (tmp[next] == 0) {
                tmp[next] = -1;
                cnt++;
                next = nums[next];
            }

            res = Math.max(res, cnt);
        }

        return res;
    }

https://leetcode.com/problems/max-consecutive-ones-iii/description/

풀이

1. r값이 0인지 체크해서 k값 조정

2. k값이 0보다 작으면 l이동

  2-1 > l값이 0인지 체크해서 k값 조정

  2-2 > l값 이동

3. 가장 긴 길이 저장 

public static int longestOnes(int[] nums, int k) {
        int left = 0;
        int right;
        int res = 0;

        //right 움직이기
        for (right = 0; right < nums.length; right++) {
            //rigth 값이 0이면 k--
            if (nums[right] == 0) {
                k--;
            }

            //k 값이 음수면 left 움직이기
            if (k < 0) {
                if (nums[left] == 0) k++;
                left++;
            }

            //가장 긴값 설정
            if (k >= 0)
                res = Math.max(res, right - left + 1);

        }
        return res;
    }

https://school.programmers.co.kr/learn/courses/30/lessons/132265

import java.util.*;

class Solution {
     public static int solution(int[] topping) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        int res = 0;
        int[] reverseTopping = new int[topping.length];
        for (int i = 0; i < topping.length; i++) {
            reverseTopping[topping.length - 1 - i] = topping[i];
        }

        //list를 채우는 메서드
        fillList(list1, topping);
        fillList(list2, reverseTopping);
        Collections.reverse(list2);

        //토핑 갯수가 동일한 구간 구하기
        for (int i = 0; i < list1.size() - 1; i++) {
            if (list1.get(i).equals(list2.get(i + 1))) res++;
        }

        return res;
    }

    static void fillList(List<Integer> list, int[] topping) {
        Set<Integer> set = new HashSet<>();
        int cnt = 0;

        for (int j : topping) {
            if (!set.contains(j)) {
                set.add(j);
                list.add(++cnt);
            } else {
                list.add(cnt);
            }
        }
    }
}

원래 값 비교 부분에서 == 을 이용해서 답이 안나왔다.

if (list1.get(i) == list2.get(i + 1)) res++;

Boxed primitive 또는 Wrapper class(Integer) 끼리 비교 하는 경우, 

== 연산자는 각 객체의 주소 값을 비교 하게 된다. 값끼리의 비교는 equal 메소드를 사용해야한다.

if (list1.get(i).equals(list2.get(i + 1))) res++;

참고

https://marobiana.tistory.com/130

https://leetcode.com/problems/jump-game-ii/description/

문제

nums[i]의 값만큼 인덱스를 점프해서 마지막 인덱스까지 도달하는 최소한의 점프 값을 구해야 한다.

tmp 배열을 하나 만들어서 배열의 인덱스 i 까지 올수 있는 최소한의 점프 수를 저장한다.

배열에 이미 값이 있으면 그 값이 최소값이므로, 이미 있는 값이 0 일때만 tmp[출발한 인덱스]의 값에 +1 해준다.

코드

package LeetCode;

public class L45 {
    public int jump(int[] nums) {
        int[] tmp = new int[nums.length];

		//tmp 배열 만들기
        for (int i = 0; i < nums.length; i++) {
        	// 인덱스값이 배열의 길이를 넘지 않게 해준다.
            for (int j = 1; j < nums[i] + 1 && (i + j) < nums.length; j++) {
            	// 값이 0일때만 새로운 값 지정하기
                if (tmp[i + j] == 0) tmp[i + j] = tmp[i] + 1;
            }
        }

        return tmp[nums.length - 1];
    }
}

https://leetcode.com/problems/find-peak-element/description/

문제

peek 은 양 옆의 수보다 큰 수 

peek을 찾는 문제 

배열의 처음-1 과 마지막+1 자리는 가장 작은 수 되어 있어서 처음이나 마지막 원소가 그 전 원소보다 크면 peek이다

you must write an algorithm that runs in O(log n) time.

> 이진 탐색으로 풀어라

코드 

public class L162 {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

https://leetcode.com/problems/remove-all-occurrences-of-a-substring/

풀이

StringBuilder 에 indexOf 메서드를 쓰면 part가 포함되어있는 idx를 알려준다. 없으면 -1 리턴.

 -1 이 나올때까지 (포함되어있지 않을때까지) 반복문을 돌리면서 포함되어있으면 delete 해준다.

public static String removeOccurrences(String s, String part) {
    StringBuilder sb = new StringBuilder(s);

    while (sb.indexOf(part) != -1) {
        sb.delete(sb.indexOf(part), sb.indexOf(part) + part.length());
    }
    return sb.toString();
}

https://leetcode.com/problems/compare-version-numbers/description/

버전2개를 비교하는 문제 

풀이

version 2개를 "." 를 기준으로 split하고

길이를 맞춰서 ArrayList에 넣어줬다. 모자른 부분은 0으로 채워둠.

ArrayList 두개 비교 

class Solution {
     public int compareVersion(String version1, String version2) {

        // . 을 기준으로 split
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int maxLength = Math.max(v1.length, v2.length);

        // 0 을 채워 size 동일한 ArrayList 만들기
        List<String> arr1 = getArr(v1, maxLength);
        List<String> arr2 = getArr(v2, maxLength);

        // 크기 비교
        for (int i = 0; i < maxLength; i++) {
            if (Integer.parseInt(arr1.get(i)) > Integer.parseInt(arr2.get(i))) return 1;
            else if (Integer.parseInt(arr1.get(i)) < Integer.parseInt(arr2.get(i))) return -1;
        }

	// 버전이 동일하면 0
        return 0;

    }

    ArrayList<String> getArr(String[] str, int maxLength) {
        ArrayList<String> arr = new ArrayList<>(Arrays.asList(str));

        while (arr.size() != maxLength) {
            arr.add("0");
        }
        return arr;
    }
}