코드 한 줄

이 문제는 두 개의 포인터를 쓰면 쉽게 풀린다.

첫 번째 포인터를 먼저 N만큼 보낸다.

그리고 첫 번째 포인터와 두 번째 포인터를 동시에 하나씩 움직인다.

첫 번째 포인터의 다음 노드가 null의 값을 가지게 되면, 두 번째 포인터의 다음 노드는 끝에서 N 번째 노드가 된다.

그 노드를 제거 한 뒤 머리 노드를 리턴하면 된다.

중요한 엣지 케이스는, 첫 번째 노드를 N 번째 옮긴 후 노드의 값이 null이라면 끝에서 N 번째 노드는 첫 번째 노드임으로 헤드를 업데이트 한 후 리턴해준다.

Node solution(Node head, int n) {
    if (head == null) {
        return null;
    }
    Node first = head;
    Node second = head;
    for (int i = 0; i < n; i++) {
        first = first.next;
    }
    if (first == null) {
        head = head.next;
        return head;
    }
    while (first.next != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return head;
}

이 문제는 가장 긴 공통된 접두사가 첫 단어라고 가정하고, 각 문자마다 모든 단어에 비교한다.

비교하는 방식은 단어의 같은 위치에 문자가 있는지 확인한다.

만약 문자가 다르거나, 문자가 없으면 현재의 문자 위치까지만 공통된 접두사이다.

int longestPrefixLength(String[] arr) {
    if (arr.length == 0) {
        return 0;
    }
    String max_prefix = arr[0];
    for (int i = 0; i < max_prefix.length(); i++) {
        char c = max_prefix.charAt(i);
        for (int j = 1; j < arr.length; j++) {
            if (i == arr[j].length() || arr[j].charAt(i) != c) {
                return i;  
            }
        }
    }
    return max_prefix.length();
}

이 문제는 “Quick Select”의 알고리즘을 사용하는 대표적인 문제이다.

Quick select는 퀵 정렬(quick sort)를 이용하는 알고리즘이다.

퀵 정렬의 pivot을 정하고 1차 정렬을 하면 pivot의 원소 위치는 최종 정렬된 배열의 위치가 된다.

이것을 이용하여 모든 배열을 정렬 하지 않고, pivot의 값을 비교하여, 찾는 값에 따라 pivot의 왼쪽이나 오른쪽만 정렬하는 알고리즘이다.

int quickselect(int[] arr, int k) {
    return quickselect(arr, 0, arr.length - 1, k - 1);
}

int quickselect(int[] arr, int first, int last, int k) {
    if (first <= last) {
        int pivot = partition(arr, first, last);
        if (pivot == k) {
            return arr[k];
        }
        if (pivot > k) {
            return quickselect(arr, first, pivot - 1, k);
        }
        return quickselect(arr, pivot + 1, last, k);
    }
    return Integer.MIN_VALUE;
}

int partition(int[] arr, int first, int last) {
    int pivot_spot = first;
    for (int i = first; i < last; i++) {
        if (arr[i] > arr[last]) {
            swap(arr, i, pivot_spot);
            pivot_spot++;
        }
    }
    swap(arr, pivot_spot, last);
    return pivot_spot;
}

void swap(int[] arr, int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

여기서 중요한 것은 나누기 사용이 안된다는 것과 O(n) 시간 복잡도여야 한다는 것이다.

여기 input 예제를 보면

Input a = [a[0], a[1], a[2], a[3], a[4]]
output =
[
a[1]*a[2]*a[3]*a[4],
a[0]*a[2]*a[3]*a[4],
a[0]*a[1]*a[3]*a[4],
a[0]*a[1]*a[2]*a[4],
a[0]*a[1]*a[2]*a[3]
]

int one[N]; int product = 1;
for(int i = 0; i < N; i++) {
    one[i] = product;
    product *= input[i]; 
}
int two[N]; int product = 1;
for(int i = N-1; i >= 0; i--) {
    two[i] = product;
    product *= input[i];
}

int[] one = [ 
1, 
a[0], 
a[0]*a[1], 
a[0]*a[1]*a[2], 
a[0]*a[1]*a[2]*a[3]
]
int[] two = [
a[1]*a[2]*a[3]*a[4], 
a[2]*a[3]*a[4], 
a[3]*a[4],
a[4],
1
]
int[] output = [
a[1]*a[2]*a[3]*a[4], 
a[0]*a[2]*a[3]*a[4], 
a[0]*a[1]*a[3]*a[4],
a[0]*a[1]*a[2]*a[4],
a[0]*a[1]*a[2]*a[3]
]

int output[N]
for(int i = 0; i < N; i++) {
    output[i] = one[i]*two[i];
}

이 문제는 해쉬맵(hashmap)을 써서 A의 문자를 B의 문자 매칭을 저장하면 된다.

A의 문자가 해쉬맵의 키로 있다면, B의 문자와 해쉬맵의 있는 값과 비교한다.

A의 문자가 해쉬맵의 키로 없다면, B의 문자가 해쉬맵의 값으로 있는지 확인하고 없으면 해쉬맵에 더해준다.

bool solve(String a, String b) {
    HashMap<char, char> map = new HashMap<>();
    for (int i = 0; i < a.length(); i++) {
        char c1 = a.charAt(i);
        char c2 = b.charAt(i);
        if (map.containsKey(c1)) {
            if (map.get(c1) != c2) {
                return false;
            }
        }
        else {
            if (map.containsValue(c2)) {
                return false;
            }
            map.put(c1, c2);
        }
    }
    return true;
}

이 문제는 해쉬맵을 사용하여 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)