코드 한 줄

이 문제는 해쉬맵을 사용하여 원소 값과 원소 인덱스를 저장하면 쉽게 풀 수 있다.

각 배열의 원소마다 (타겟 - 원소 값)이 해쉬맵에 있는지 확인하면 된다.

int[] solution(int[] input, int target) {
    Map<int, int> map = new HashMap<>();
    for(int i=0; i<input.length; i++) {
        int complement = target - input[i];
        if(map.containsKey(complement)) {
            return [map.get(complement), i];
        }
        map.put(input[i], i);
    }
    return [-1, -1];    // No Solution
}

일단 엣지 케이스를 살펴보자. 정수가 마이너스면 팰린드롬이 될 수 없다.

그리고 0이 아닌 정수가 0으로 끝난다면 이 경우 역시 팰린드롬이 될 수 없다.

주어진 숫자를 전반부와 후반부로 나눈다. 예를 들어 1233210이 주어지면, 123이 전반부이고 321이 후반부이다.

전반부(123)가 거꾸로 된 후반부(123)와 같다면 팰린드롬이다.

정수를 전반부와 거꾸로 된 후반부로 나누려면 while문을 써서 정수의 일의 자리수를 뽑아낸 후 정수를 10으로 나누면 정수의 각 숫자를 얻어낼 수 있다.

123321 -> 12332, 1 -> 1233, 2 -> 123, 3

이제 거꾸로 된 후반부는 10으로 곱한 뒤 뽑아낸 일의 자리 숫자를 더하면 된다.

0 + 1 -> 10 + 2 -> 120 + 3 = 123

이 방법을 거꾸로 된 후반부가 전반부보다 크거나 같을 때까지 반복하면 된다.

만약 주어진 숫자의 길이가 홀 수라면, 거꾸로 된 후반부에서의 1의 자리수를 없애주면 된다.

12321 - > 전반부(12), 거꾸로된 후반부(123)

전반부 = input

거꾸로된 후반부 = revertedHalf

bool IsPalindrome(int input) {
      if(input < 0 || (input % 10 == 0 && input != 0)) {
          return false;
      }

      int revertedHalf = 0;
      while(input > revertedHalf) {
          revertedHalf = revertedHalf * 10 + input % 10;
          input /= 10;
      }
      return input == revertedHalf || input == revertedHalf/10;
}

시간 복잡도 : O(log n)            // 숫자의 길이만큼 반복된다.

공간 복잡도 : O(1)

주로 조합을 구하거나 답의 양이 많을 경우는 재귀함수를 사용하면 된다.

empty string 부터 시작하여 "("를 더하고 재귀함수를 부르고, ")"를 더하고 재귀함수를 부르면 된다.

여기서 중요한 건, 현재 몇 개의 여는 괄호를 사용 하였는지와 몇 개의 닫는 괄호를 사용 하였는지 알아야 한다.

괄호 조합을 왼쪽에서 오른쪽으로 읽을 때, 닫는 괄호가 여는 괄호 개수보다 많으면 정당한 조합이 될 수 없다.

그러므로, 재귀함수에서 여는 괄호가 n보다 작을 때 여는 괄호를 더한 재귀함수를 만들고,

닫는 괄호 개수가 여는 괄호 개수보다 작을 때 닫는 괄호를 더한 재귀함수를 만들면 된다.

재귀함수에 주어진 문자열이 (n*2) 길이를 가진다면 알맞는 괄호 조합이니, 리스트에 더해주면 된다.

List<string> parenthesisPairs(int n) {
    List<string> ans = new ArrayList();
    recurse(ans, "", 0, 0, n);
    return ans;
}

void recurse(List<string> ans, String cur, int open, int close, int n){
    if (str.length() == n * 2) {
      ans.add(cur);
      return;
  }
    if (open < n) {
      recurse(ans, cur + "(", open + 1, close, n);
    }
    if (close < open) {
      recurse(ans, cur + ")", open, close + 1, n);
    }
}

이 문제는 n보다 클 때까지 피보나치의 수를 구하며 짝수인 피보나치 수를 다 더해주면 된다.

int evenFibSum(int N) {

    int sum = 0;
    int x = 1;
    int y = 2;

    while (x <= N) {
      if (x % 2 == 0) {
        sum += x;
      }
      int z = x + y;
      x = y;
      y = z;
  }

    return sum;
}

여기서 피보나치 수가 0이 아니고 1부터 시작하는 이유는 x가 0일 경우 sum에 더해도 도움이 되지 않기 때문이다.

이 문제는 두 개의 정수 변수로 현재의 합(currentSum)과 전체의 제일 큰 합(maxSum)을 저장해야 합니다.

각 원소마다 (currentSum + 원소) 값을 원소 값이랑 비교하고, 더 큰 값이 currentSum이 됩니다.

maxSum은 currentSum이 바뀔 때마다 체크하여 제일 큰 값을 저장하면 됩니다.

int solution(int[] arr) {

    int maxSum = arr[0];
    int currentSum = arr[0];

    for(int i = 1; i < arr.length; i++) {
      currentSum = Math.max(currentSum + arr[i], arr[i]);
      maxSum = Math.max(currentSum, maxSum);
    }

    return maxSum;
}