코드 한 줄

이 문제는 가장 큰 값을 구하는 로직과 거의 똑같다.

가장 큰 값과 두 번째 큰 값을 저장할 변수를 만들고 배열 원소들과 비교하면 된다.

중요한 엣지 케이스는 배열이 0 이나 1개의 원소를 가지고 있으면 두번째 큰 값이 존재 하지 않는 것과

[3, 3, 3] 같은 경우처럼 두 번째로 큰 값은 존재 하지 않는다.

이를 계산하기 위해 두 번째 큰 값을 저장할 변수를 Integer.MIN_VALUE로 두고

for루프가 끝난 뒤 값이 변했는지 체크하면 된다.

void secondLargest(int[] arr) {
    int first, second;

    if (arr.length < 2) {
        print("두번째로 큰 값은 없습니다.");
        return;
    }

    first = second = Integer.MIN_VALUE;

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > second && arr[i] != first) {
            second = arr[i];
        }
    }

    if (second == Integer.MIN_VALUE) {
        print("두번째로 큰 값은 없습니다.");
    } else {
        print(second);
    }
}

이 문제는 긴 String 을 각 단어로 나눈 다음, 각 단어를 거꾸로 하고, 모든 단어들을 합치면 풀 수 있다.

public String reverseString(String s) {
    String words[] = split(s);
    StringBuilder res = new StringBuilder();
    for (String word: words)
        res.append(reverse(word) + " ");
    return res.toString().trim();
}

public String[] split(String s) {
    ArrayList <String> words = new ArrayList <>();
    StringBuilder word = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ') {
            words.add(word.toString());
            word = new StringBuilder();
        } else
            word.append(s.charAt(i));
    }
    words.add(word.toString());
    return words.toArray(new String[words.size()]);
}

public String reverse(String s) {
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < s.length(); i++)
        res.insert(0,s.charAt(i));
    return res.toString();
}

문제의 어려운 점은 간격 원소들이 무작위로 순서가 돼있는 것이다.

주로 이런 경우엔 자료구조를 써서 무작위 원소들을 쉽게 정리하거나, 원소들을 정렬하면 된다.

이 문제에선 간격 원소들을 정렬해보겠다.

간격 원소가 {start, end}로 나누어 있다고 가정하고, start로 정렬한다.

int compare(Interval a, Interval b) {
    return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
sort(intervals, compare);

정렬은 언어마다 있는 정렬 함수를 써도 되고, 아니면 직접 정렬 알고리즘을 써서 정렬 해도 상관없다.

정렬된 원소들은 처음부터 하나씩 보면서 현재 원소의 end 값과 다음 원소의 start 값을 비교하여 겹쳐지면 두 원소를 합치면 된다.

int compare(Interval a, Interval b) {
    return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}

List<Interval> merge(List<Interval> intervals) {
    sort(intervals, compare);

    LinkedList<Interval> solution = new LinkedList<Interval>();
    solution.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        Interval interval = intervals[i];
        if (solution.getLast().end < interval.start) {
            solution.add(interval);
        }
        else {
            solution.getLast().end = 
                Math.max(solution.getLast().end, interval.end);
        }
    }
    return solution;
}

시간 복잡도 : O(n*log(n))

공간 복잡도 : O(n)

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

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

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에 더해도 도움이 되지 않기 때문이다.