class Solution {
public boolean isPalindrome(String s) {
boolean result = true;
s= s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
int end = s.length()-1;
int start = 0;
while (end > start) {
if (s.charAt(end) != s.charAt(start)){
result = false;
break;
}
end--;
start++;
}
return result;
}
}
간단한 문제였다. 정규식으로 처리하면 예쁠 것 같아서 위와 같이 해결했다.
다른 사람들이 푼 것을 보니까 처음부터 lowercase 로 해서 A-Z를 삭제하던데 좋은 방법인 것 같다.
class Solution {
public boolean isSubsequence(String s, String t) {
int sIdx = 0;
if (s.length() == 0) {
return true;
}
for (int i = 0; i < t.length(); i++){
if (s.charAt(sIdx) == t.charAt(i)){
sIdx++;
if (sIdx > s.length()-1){
return true;
}
}
}
return false;
}
}
이문제도 easy 인 것 답게 쉬웠는데 s 문자열이 빈 문자열인 경우 때문에 에러가 발생하는 것만 조심하면 되었다.
167. Two Sum II - Input Array Is Sorted
조건 : contant extra space -> 배열 사용 x
답은 배열 안에 무조건 존재하며 1개의 답밖에 없다. 2개를 조합하면 나온다.
1. 시간복잡도를 무시하고 풀기 -> 2인 수열조합을 전부 구한다음에 합이 정답과 같은 것을 고른다.
이 친구는 파이썬으로 하는게 아니면 수제로 구현해야하는 걸로 아는데 상당히 귀찮다.
1.1 두개의 정답밖에 없다는 것을 고려해서 2중 for문으로 모두 확인한다.
2. 투 포인터를 사용해본다. 양쪽 끝단부터 넘치면 하나씩 옮기면서 확인하는 방법이면 되지 않을까?
합이 정답보다 크다면 end--, 합이 정답보다 작다면 start++; 로 하면 좋을 것 같다.
class Solution {
public int[] twoSum(int[] numbers, int target) {
int start = 0;
int end = numbers.length-1;
int[] answer = new int[2];
while (start < end) {
if (numbers[start]+numbers[end] == target){
answer[0] = start+1;
answer[1] = end+1;
break;
}else if (numbers[start]+numbers[end] > target){ // 큰 경우
end--;
}else{ // 작은경우
start++;
}
}
return answer;
}
}늘 시간복잡도를 버린채로 풀었었는데 정석 풀이가 이거였구나....
오늘도 하나 배우고 갑니다 리트코드
이 문제의 경우에도 투포인터 문제이다.
start 와 end를 각각 언제 증가, 감소할지가 관건인데..
더 작은 쪽이 움직이는 게 맞겠지?
class Solution {
public int maxArea(int[] height) {
int start = 0;
int end = height.length - 1;
int answer= 0;
while (start < end){
int water = 0;
if (height[start] < height[end]){
water = height[start] * (end-start);
start++;
}else{
water = height[end] * (end-start);
end--;
}
if (water > answer){
answer = water;
}
}
return answer;
}
}애도 완료했다!
오늘은 쉬운 문제가 많으니 여기까지 풀고 스프링 공부해야겠다.
일단 정렬을 하면 좋지 않을까? 뭘 사용해야할지 감이 안온다.
정렬을 하면 1번 문제의 경우 [-4, -1, -1, 0, 1, 2] 가 된다.
start, end 포인터를 사용하고 남은 수를 바탕으로 계산하면 될 것 같다?
그런데 문제가 발생했다.
나는 java 에서 새로운 요소 넣는 법을 모른다.
정적으로 배열 만들면 안될텐데...?
답 구하는 법은 알았는데.. 배열을 어떻게 정의해야하지
이럴 땐 물어볼 수 있는 친구가 있다.
java 에도 list 같은 애가 있었구나. 그래 없을리가 없었지
아무튼 저거 사용해서 예쁘게 만들어보자
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int start = 0;
int end = nums.length-1;
Arrays.sort(nums);
List<List<Integer>> answer = new ArrayList<>();
while (start < end) {
int doubleSum = nums[start] + nums[end];
// 언제 start end 를 줄이고 늘리지?
for (int i = start + 1; i < end; i++){
if (doubleSum + nums[i] == 0){
List<Integer> tripleSum = Arrays.asList(nums[start], nums[i], nums[end]);
answer.add(tripleSum);
}
}
}
return answer;
}
}여기까지 진행을 했는데 포인터 증감문제가 발생했다.
0과 가장 비슷한 수를 바탕으로 - 이면 start 증가, + 이면 end 감소로 해본다!
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int start = 0;
int end = nums.length-1;
Arrays.sort(nums);
List<List<Integer>> answer = new ArrayList<>();
while (start < end) {
int doubleSum = nums[start] + nums[end];
// 언제 start end 를 줄이고 늘리지?
int closeZeroIdx = start+1;
for (int i = start + 1; i < end; i++){
if (doubleSum + nums[i] == 0){
List<Integer> tripleSum = Arrays.asList(nums[start], nums[i], nums[end]);
answer.add(tripleSum);
closeZeroIdx = i;
break;
}
if (Math.abs(doubleSum + nums[i]) <Math.abs(doubleSum + nums[closeZeroIdx])){
closeZeroIdx = i;
}
}
if (doubleSum + nums[closeZeroIdx] < 0) {
start++;
}else{
end--;
}
}
return answer;
}
}호기롭게 작성했으나 다음에서 문제가 발생했다.
왜 저게 1개만 나와야하는거지? 문제 이해를 잘못했나 했지만... 음.. 역시 내가 잘못 읽었다.
Notice that the solution set must not contain duplicate triplets.
그래서 중복 제거하는 로직을 작성해본다.
파이썬의 not in 함수가 정말 그립다...
자바에서도 contains 라는 함수가 있어서 다행이였다. for 문은 사용하기 무서워서...
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int start = 0;
int end = nums.length-1;
Arrays.sort(nums);
List<List<Integer>> answer = new ArrayList<>();
while (start < end) {
int doubleSum = nums[start] + nums[end];
// 언제 start end 를 줄이고 늘리지?
int closeZeroIdx = start+1;
for (int i = start + 1; i < end; i++){
if (doubleSum + nums[i] == 0){
List<Integer> tripleSum = Arrays.asList(nums[start], nums[i], nums[end]);
if (!answer.contains(tripleSum)) {
answer.add(tripleSum);
}
closeZeroIdx = i;
break;
}
if (Math.abs(doubleSum + nums[i]) <Math.abs(doubleSum + nums[closeZeroIdx])){
closeZeroIdx = i;
}
}
if (doubleSum + nums[closeZeroIdx] < 0) {
start++;
}else{
end--;
}
}
return answer;
}
}근데 여기서도 문제가 발생했다.
흠.. 그래서 그냥 답안을 보기로 했다. 더 이상 푸는 건 하드코딩이 될 것 같았기 때문이다.
그래서 답안은 다음과 같았다.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i<nums.length; i++){
if (i > 0 && nums[i] == nums[i-1]){
continue;
}
int j = i+1;
int k = nums.length -1;
while (j<k){
int total = nums[i] + nums[j] + nums[k];
if (total > 0){
k--;
}else if (total < 0){
j++;
}else{
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
while (nums[j] == nums[j-1] && j < k){
j++;
}
}
}
}
return res;
}
}꽤나 재밌는데 나와는 다르게 분할정복..? 방식으로 푸셨다. for 문 돌리면서 합이 첫번째것과 합쳐서 0이 나올 수 있도록 만드셨었다. 확실히 풀고서 보니까 좀 더 머리에 잘 들어오는 것 같기도하고.. 아무튼 리트코드 완 ㅇㅅㅇ!
'공부용 > 연습장' 카테고리의 다른 글
| [리트코드] 10일차 (0) | 2025.02.12 |
|---|---|
| [리트코드] 9일차 + python radon 사용해보기 (0) | 2025.02.10 |
| 오늘 한 일 (0) | 2025.02.05 |
| [리트코드] 3문제 + 아이디어 생성기 (1) | 2025.02.04 |
| [리트코드 문제 해결하기] (0) | 2025.02.03 |
