두 번째 날도 아직 Easy 난이도만 풀고 있다. 다행히 아주 다 잊어버리진 않은 것 같아서 다행이다. 그런데 CS 기본이나 면접 질문들은 언제 준비하고 이력서는 언제 업데이트할지.. 할 일이 태산이지만 문제부터 풀어보자.
1071. Greatest Common Divisor of Strings
두 문자열 s, t가 있을 때 s가 t로만 구성돼있는 경우 나눌 수 있다. 이때 str1, str2를 나누는 가장 긴 문자열을 구하라는 문제다.
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
일종의 최대공약수를 구하는것이 때문에 해당 문자열의 후보군을 제한하는 것부터 시작해 보자. str1, str2를 모두 나눌 수 있어야 하기 때문에 처음 시작은 str1, str2 중 작은 문자열로 시작한다(candidate). 그리고 후보의 문자열 길이가 1일 때까지 줄이면서 두 문자열을 나눌 수 있는지 확인한다. 최종적으로 후보가 없다면 빈 문자열을 반환한다.
class Solution {
public String gcdOfStrings(String str1, String str2) {
int maxLen = Math.min(str1.length(), str2.length());
for (int i=maxLen; i >= 1; i--) {
String candidate = str1.substring(0, i);
if (isCommon(candidate, str1) && isCommon(candidate, str2)) {
return candidate;
}
}
return "";
}
private boolean isCommon(String candidate, String str) {
int found = str.indexOf(candidate);
if (found != 0) { // 1 엣지 케이스
return false;
}
while (found >= 0) {
if (found + candidate.length() == str.length()) {
return true;
}
int nextFound = str.indexOf(candidate, found+candidate.length());
if (found + candidate.length() != nextFound) { // 2 엣지 케이스
return false;
}
found = nextFound;
}
return false;
}
}쉽다면서 솔루션을 제출한 순간 틀린 테스트케이스가 나왔다. 라이브 코딩 테스트를 한다는 생각으로 꼭 엣지케이스를 만들어서 돌려보는 습관을 들여야 할 것 같다. 내가 틀린 테스트케이스는 ["BELEETLEET", "LEET"], ["LEETBELEET", "LEET"] 같은 경우이다.
첫번째 테스트 케이스는 1번 엣지케이스에서 판별이 되는데, substring의 매칭이 문자열의 시작이 아닌 경우이다. 문자열 전체가 substring으로만 이뤄져야 나눠진다고 보기 때문에 확인해줘야 한다. 두 번째 테스트 케이스는 2번 엣지케이스인데, 중간에서 매칭이 될 때도 인덱스가 중간에 떠버리는 경우가 없는지 체크한다고 보면 된다.
시간 복잡도는 candidate에 대해서 반복적으로 str1, str2를 나눌 수 있는지 비교해야 하기 때문에 두 문자열의 길이를 각각 m, n이라고 했을 때 O(min(m, n) * (m + n))이 된다. 공간 복잡도는 candidate를 저장하기 위한 공간 O(min(m, n))이 필요하다.
솔루션을 찾아보니 더 나은 답변(수학적인)도 있다. 역시 면접에서는 '더 나은' 솔루션이 없는지 물어볼 수 있기 때문에 추가적으로 봐두도록 하자.
392. Is Subsequence
다음 문제를 보자. subsequence를 정의하는데, 한 문자열이 원래 문자열 일부로 구성되어 있고 순서는 그대로인 경우라고 한다. 예시는 'ace'가 'abcde'의 subsequence라고 한다.
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
직관적이니 바로 문제를 풀어보자.
class Solution {
public boolean isSubsequence(String s, String t) {
int i=0;
int j=0;
while(i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else {
j++;
}
}
return i == s.length();
}
}
Two pointer의 전형적인 문제라고 할 수 있는데 각 문자열의 인덱스를 저장하는 변수를 각각 선언하고 반복문을 돌면서 s의 각 문자가 t 문자열 내에 순서대로 존재하는지 확인한다. 그리고 s가 subsequence라면 반복문을 나왔을 때 인덱스 i가 문자열 s의 길이와 같아야 한다.
시간 복잡도는 두 문자열의 길이를 m, n이라고 했을 때 원래 문자열을 끝까지 확인해야 하기 때문에 O(max(m, n))이다. 공간 복잡도는 O(1).
1732. Find the Highest Altitude
고도의 변화를 저장하고 있는 배열이 있고, 첫번째 포인트의 고도는 0이다. 이때 가장 높은 고도의 값을 리턴해야 한다.
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
고도의 변화값만 저장하고 있기 때문에 시작이 0이고, 그 다음부터 값을 더해가면서 최댓값을 저장하면 된다.
class Solution {
public int largestAltitude(int[] gain) {
int max = Math.max(0, gain[0]);
for(int i=1; i<gain.length; i++) {
gain[i] = gain[i] + gain[i-1];
max = Math.max(max, gain[i]);
}
return max;
}
}한 가지 주의할 점이라면 max값을 초기화할 때 0을 빼먹는 실수를 하면 실패하는 테스트 케이스가 있다. (그 실수를 한 사람...✋) 그래서 초기값을 0과 gain[0] 중 최댓값으로 초기화하고, 그다음은 in-place로 gain 값을 누적하면서 max값을 체크하면 된다.
시간 복잡도는 O(n), 공간 복잡도는 O(1).
