Two pointer
문제링크: https://leetcode.com/problems/reverse-words-in-a-string-iii/description/
557. Reverse Words in a String III
문자열 s가 주어진다. 공백을 기준으로 단어들을 reverse해서 return해라
Ex)
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
제약사항
s.length는 1이상 5*10^4 이하이다.
s는 프린트 가능한 ASCII 문자를 포함. s는 앞 뒤에 공백이 없다. 적어도 하나의 단어가 존재. 단어는 공백 하나로 구분된다.
아이디어:
s의 길이 때문에 O(n^2) 불가
문자열이고 O(n^2)이 안되면 투포인터가 생각난다. subarray의 합과도 무관한것같으니 투포인터로 가보자.
1. 공백에 따라 단어 범위 설정 (left, right)
2. 단어 리버스
3. 다음 공백이 없다면 그것까지 리버스하고 끝내기
class Solution {
public String reverseWords(String s) {
// 변수 선언
char[] arr = s.toCharArray();
int left = 0;
int right = 0;
boolean isEnd = false;
while(!isEnd){ // 마지막 단어까지
int nextWhiteSpaceIdx = s.indexOf(" ", left); // 다음 공백 인덱스
if (nextWhiteSpaceIdx == -1){ // 다음 공백이 없다면
isEnd = true; // 마지막 단어란 뜻
right = s.length() - 1;
} else { // 다음 공백이 있다면
right = nextWhiteSpaceIdx - 1; // 다음 공백 전
}
while(left < right){ // 투포인터로 reverse
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
left = s.indexOf(" ", left) + 1; // 다음 공백 + 1
}
return new String(arr);
}
}
문제링크: https://leetcode.com/problems/reverse-only-letters/description/
917. Reverse Only Letters
문자열 s가 주어진다. 다음 rule에 따라 reverse해라
- 영어가 아닌 문자는 그 자리에 냅둔다.
- 영어인 문자는 reverse한다.
Ex)
Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
제약사항
s.length는 1이상 100 이하이다.
s는 범위가 33 ~122인 ASCII 문자를 포함. '\"', '\\' 포함안한다.
아이디어:
투포인터를 이용해서 left와 right 둘 다 알파벳이면 바꾸고 left가 알파벳이 아니면 left++, right가 알파벳이 아니면 right--하자.
방법1:
class Solution {
public String reverseOnlyLetters(String s) {
char[] arr = s.toCharArray();
int l = 0;
int r = arr.length - 1;
char temp;
while(l < r){
if (!Character.isAlphabetic(arr[l])){ // 왼쪽 문자가 알파벳이 아니면
l++;
continue;
}
if (!Character.isAlphabetic(arr[r])){ // 오른쪽 문자가 알파벳이 아니면
r--;
continue;
}
// 둘 다 알파벳이면
temp = arr[l];
arr[l++] = arr[r];
arr[r--] = temp;
}
return new String(arr);
}
}
시간이 조금 더 줄일 수 있는 방법이 있구나를 알고 고민한 결과, isAlphabetic의 문제이지 않을까하고 조사했다.
알고보니 isAlphabetic은 단순히 A-Z, a-z만이 아니라 유니코드 표준에서 알파벳으로 분류된 문자들 전부를 포함. 한글, 그리스어도 포함된다. 그래서 A-Z, a-z로만 판단하는 함수를 만들어서 갈아끼웠다.
방법2:
class Solution {
private boolean isAlphabet(char ch){
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
public String reverseOnlyLetters(String s) {
char[] arr = s.toCharArray();
int l = 0;
int r = arr.length - 1;
char temp;
while(l < r){
if (!isAlphabet(arr[l])){
l++;
continue;
}
if (!isAlphabet(arr[r])){
r--;
continue;
}
temp = arr[l];
arr[l++] = arr[r];
arr[r--] = temp;
}
return new String(arr);
}
}
인사이트: isAlphabetic()는 유니코드 범위를 고려하므로 내부적으로 많은 분기와 매핑 로직이 들어있어서 루프에서 반복 호출하면 성능이 아쉬울 수 있다!
문제링크: https://leetcode.com/problems/minimum-common-value/description/
2540. Minimum Common Value
오름차순으로 정렬되어있는 두 개의 정수 배열 num1, num2가 주어진다.
두 개의 어레이에서 공통된 원소 중에 가장 작은 값이 반환해라. 없으면 -1 반환
Ex)
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
2, 3이 공통된 원소지만 2가 제일 작다.
제약사항
두 배열의 길이 범위는 1 ~ 10^5이다.
두 배열의 원소값의 범위는 1 ~ 10^9이다.
둘 다 오름차순으로 정렬되어있다.
아이디어:
배열의 길이 범위 때문에 O(n^2) 안된다.
원소값의 범위를 보아하니 반환되는 값은 int로도 충분하다.
둘 다 오름차순이기 때문에 앞에서부터 비교하면서 같은 값이면 그게 제일 작은 값이다.
두 배열에 각각 포인터를 두고 비교한다. (p1, p2)
둘이 같으면 (nums1[p1] == nums2[p2]) return 그 값
nums1[p1]이 더 크면 p2를 올린다.
nums2[p2]가 더 크면 p1 포인터를 올린다.
class Solution {
public int getCommon(int[] nums1, int[] nums2) {
int p1 = 0;
int p2 = 0;
while(p1 < nums1.length && p2 < nums2.length){
if (nums1[p1] > nums2[p2]) p2++;
else if (nums1[p1] < nums2[p2]) p1++;
else return nums1[p1];
}
return -1;
}
}
이유는 모르겠지만 if와 else if의 조건을 바꾸면 2ms -> 1ms로 더 빨라진다,,
문제링크: https://leetcode.com/problems/move-zeroes/description/
283. Move Zeroes
nums라는 정수 배열이 주어질 때, 모든 0을 끝으로 옮겨라. 0이 아닌 원소들의 상대 순서를 지키면서!
반드시 배열 복사본을 만들지 말고 해결해라
Ex)
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
제약사항
배열의 길이 범위는 1 ~ 10^4이다.
배열 원소값의 범위는 -2^31 ~ 2^31 - 1
아이디어:
배열의 길이 범위 때문에 O(n^2) 간당간당할지도 안될지도.
원소값의 범위를 보아하니 반환되는 값은 int는 4byte니까 딱 맞겠다.
투 포인터로 left와 right의 자리를 바꾸는 식
- right를 움직이면서
- nums[right]가 0이 아니라면 nums[left]랑 바꾼다. 그리고 left++
- nums[right]가 0이라면 right++
class Solution {
public int[] moveZeroes(int[] nums) {
int l = 0;
int temp = 0;
for(int r = 0; r < nums.length; r++){
if(nums[r] != 0){
temp = nums[l];
nums[l++] = nums[r];
nums[r] = temp;
}
}
return nums;
}
}
문제링크: https://leetcode.com/problems/reverse-prefix-of-word/description/
2000. Reverse Prefix of Word
문자열 word, 문자 ch가 주어질 때, 인덱스 0 ~ ch가 처음 등장하는 인덱스까지의 word를 Reverse해라.
만약 ch가 없다면 아무것도 하지말아라.
Ex)
Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Input: word = "abcd", ch = "z"
Output: "abcd"
제약사항
문자열의 길이 범위는 1 ~ 250이다.
word는 영어 소문자로 이루어져있고 ch도 영어 소문자이다.
아이디어:
이제 뭔가 reverse하면 투 포인터가 효율적이구나를 느낀다.
1. ch의 인덱스를 구한다. 없다면 바로 word 리턴
2. 있으면 투 포인터를 이용하여 reverse 해준다.
class Solution {
public String reversePrefix(String word, char ch) {
int r = -1;
for(int i = 0; i < word.length(); i++){
if(word.charAt(i) == ch){
r = i;
break;
}
}
if(r == -1) return word;
char[] arr = word.toCharArray();
int l = 0;
char temp;
while(l < r){
temp = arr[l];
arr[l++] = arr[r];
arr[r--] = temp;
}
return new String(arr);
}
}