Back to basics

문제 풀이 투 포인터로 풀면 된다. 배열의 처음(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 right = height.length - 1; while (left < ri..

문제 배열에서 자신을 제외한 나머지 요소의 곱셈 결과를 출력하는 문제. 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 left = 1; int right = 1; int[] result = new i..

문제 주어진 문자열이 유효한 IPv4 형식인지 유효한 IPv6 형식인지 확인하는 문제이다. 풀이 주어진 문자열이 특정한 구분자로 나눠지는 확인하고 dot(.) 3개로 구분되어 있으면 IPv4로 간주하고 유효한 지 확인한다. colon(:) 7개로 구분되어 있으면 IPv6로 간주하고 유효한 지 확인한다. 그 외의 경우는 “Neither” 를 반환한다. 유효한 IPv4 확인하는 방법은 dot(.)으로 나눈 substring 마다 아래의 경우를 확인한다. 0-255 사이에 위치한 숫자여야 함 0이 아닌 경우를 제외하면 0으로 시작하는 경우가 없어야 함 유효한 IPv6 확인하는 방법은 colon(:)으로 나눈 substring 마다 아래의 경우를 확인한다. 길이가 1 이상 4 이하여야함 hexadecimal에 ..

문제 풀이 첫 번째 예제(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 rotate(int[] nums, int k) { i..

문제 풀이 기본적으로 탐색하는 character가 문자면 소문자, 대문자로 변환하고 숫자면 다음 character로 넘어갔다. 마지막까지 완료하면 새로운 문자열을 반환하였다. 개념을 그림으로 표현해봤다. 주어진 문자열이 "a1b2" 이면 결과로 ["a1b2", "a1B2", "A1b2", "A1B2"] 가 반환된다. dfs 함수를 만들고 character가 문자면 두 갈래(소문자, 대문자)로 나눠서 계속 함수를 호출해 풀었다. 코드 class Solution { fun letterCasePermutation(s: String): List { val result = arrayListOf() dfs(s.toCharArray(), 0, result) return result } fun dfs(target: C..

문제 풀이 a + b + c = 0 인 경우를 찾는 문제이다. 투 포인터를 이용해서 풀었다. 우선 정렬을 한 다음에 for 루프를 돌면서 nums[index] 가 a 라고 할 때 포인터를 이동하면서 b 와 c 값을 찾았다. 문제에서 답에 중복을 허용하지 않기 때문에 중복인 경우는 다시 계산하지 않게 처리했다. [0, 0, 0, 0, 0, 0] 와 같은 인풋이 들어왔을 때 한 번만 계산하고 스킵하게 된다. 시간복잡도는 O(N^2) 이 된다. => 정렬하는 데 O(NlogN) + for 루프 돌면서 b와 c값 찾는 데 O(N^2) 코드 fun threeSum(nums: IntArray): List { nums.sort() val result: MutableList = mutableListOf() for (i..