코드 한 줄

이 문제는 해쉬맵을 사용하여 char와 char의 인덱스를 저장하여 풀면 된다.

string의 각 char를 보면서 해쉬맵에 있다면 substring 시작점을 char의 인덱스+1 로 두면 된다.

그리고 현재 char의 인덱스와 시작점의 거리를 계속 계산하여 가장 큰 값을 리턴하면 된다.

int longestSubstringLength(String s) {
	int ret = 0;
	int start = 0;
	Map<char, int> map = new HashMap<>();
	for (int j = 0; j < s.length(); j++) {
		if (map.containsKey(s[j])) {
			start = Math.max(map.get(s[j]), start);
		}
		ret = Math.max(ret, j - start + 1);
		map.put(s[j], j + 1); // 캐릭터 인덱스 저장
	} 
	return ret;
}

이 문제는 0을 오른쪽으로 옮기는 것보다 0이 아닌 정수를 왼쪽으로 옮긴다고 생각하면 쉽게 풀 수 있다.

void solve(int[] input) {
    int position = 0; // 0이 아닌 정수가 들어갈 곳

    for (int i = 0; i < input.length; i++) {
        if (input[i] != 0) {
            swap(input, i, position);
            position++;
        }
    }
}

void swap(int[] arr, int a, int b) {
    if (a == b) return;
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

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

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

중요한 엣지 케이스는 배열이 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)