알고리즘19 [leetcode] 205. Isomorphic Strings [leetcode] 205. Isomorphic Strings 문제 풀이 주어진 두 문자열이 Isomorphic 이면 true를 반환, 아니면 false를 반환하면 되는 문제 map를 하나 생성해서 두 문자열을 매핑하고 비교하면 된다. 하지만 한 가지 주의해야 할 점은 두 문자가 같은 문자에 맵핑될 수 없다는 점이다. 즉 아래와 같은 경우는 o가 a와 r에 매핑되므로 false가 반환되어야 한다. f -> b o -> a o -> r 아래와 같은 경우 역시 b와 d가 b에 매핑되고 a와 c가 a에 매핑되므로 false가 반환되어야 한다. b -> b a -> a d -> b c -> a s -> t 로 매핑되는 맵과 t -> s 로 매핑되는 맵 2가지를 만들어서 계산하면 위 같은 케이스를 구분할 수 있다.. 2023. 1. 10. [leetcode] 724. Find Pivot Index [leetcode] 724. Find Pivot Index 풀이 왼쪽 값들의 합과 오른쪽 값들의 합이 일치하는 pivot 인덱스를 찾는 문제이다.찾지 못하면 -1를 반환하면 된다.전체 값의 합을 구한 다음, 해당 값을 이용해서 오른쪽 값들의 합을 구하면 된다. 오른 쪽 값들의 합 = 전체 값의 합 - pivot - 왼쪽 값들의 합 참고로 Java Stream API 를 이용해서 Array의 sum 값을 구할 수 있다. Arrays.stream(array).sum(); 코드 class Solution { public int pivotIndex(int[] nums) { var total = Arrays.stream(nums).sum(); var leftSum = 0; for(int i=0; i 2023. 1. 9. [leetcode] 11. Container With Most Water [leetcode] 11. Container With Most Water 문제 풀이 투 포인터로 풀면 된다. 배열의 처음(left)과 배열의 맨 끝부분(right)의 포인터를 이동하면서 가장 큰 area를 구하면 된다. - area = (right - left) * min(height[left], height[right]) 포인터의 이동은 left와 right의 height를 비교해서 left가 더 크면 right를 왼쪽으로 이동해주고 아니면 left를 오른쪽으로 이동해주면 된다. left가 right보다 크면 loop를 종료하면 된다. 코드 Java class Solution { public int maxArea(int[] height) { int area = 0; int left = 0; int ri.. 2022. 8. 13. [leetcode] 238. Product of Array Except Self [leetcode] 238. Product of Array Except Self 문제 배열에서 자신을 제외한 나머지 요소의 곱셈 결과를 출력하는 문제. O(n)에 나눗셈을 하지 않고 풀어야 한다. 풀이 나눗셈을 하지 않고 O(n)에 풀어야 하니깐 왼쪽 와 오른쪽의 곱셉 결과를 이용하면 된다.result[n] 은 왼쪽의 n-1까지의 곱셈 결과 * 오른쪽 n+1까지의 곱셈 결과이다. 인풋이 [-1,1,0,-3,-3] 일 경우 result[2]은 왼쪽부터 1번 요소까지의 곱셈 결과(-1 * 1) * 오른쪽부터 3번 요소까지의 곱셈 결과( 3 * -3) = -1 * -9 = 9 가 된다. 코드 class Solution { public int[] productExceptSelf(int[] nums) { int .. 2022. 7. 18. [leetcode] 468. Validate IP Address [leetcode] 468. Validate IP Address 문제 주어진 문자열이 유효한 IPv4 형식인지 유효한 IPv6 형식인지 확인하는 문제이다. 풀이 주어진 문자열이 특정한 구분자로 나눠지는 확인하고 dot(.) 3개로 구분되어 있으면 IPv4로 간주하고 유효한 지 확인한다. colon(:) 7개로 구분되어 있으면 IPv6로 간주하고 유효한 지 확인한다. 그 외의 경우는 “Neither” 를 반환한다. 유효한 IPv4 확인하는 방법은 dot(.)으로 나눈 substring 마다 아래의 경우를 확인한다. 0-255 사이에 위치한 숫자여야 함 0이 아닌 경우를 제외하면 0으로 시작하는 경우가 없어야 함 유효한 IPv6 확인하는 방법은 colon(:)으로 나눈 substring 마다 아래의 경우를 .. 2022. 3. 15. [leetcode] 189. Rotate Array [leetcode] 189. Rotate Array 문제 풀이 첫 번째 예제(nums = [1,2,3,4,5,6,7], k = 3)를 그리면 아래와 같다. 초록색 네모 그룹을 1번 그룹이라고 하고 파란색 동그라미 그룹을 2번 그룹이라고 할 때 결과는 2번 그룹과 1번 그룹의 순서를 서로 바꿔주면 된다. 1번 그룹 : 0 ~ k-1 2번 그룹 : k ~ input.length-1 다시 그림으로 간략하게 표현하면 다음과 같다. 화살표는 숫자의 오름차순 정렬을 표현했다. 결과가 나오려면 3번의 reverse를 수행해야 한다. 2번 그룹 reverse 1번 그룹 reverse 전체 그룹 reverse reverse 과정을 그림으로 표현하면 아래와 같다. 코드 class Solution { public void .. 2021. 10. 15. 이전 1 2 3 4 다음
