Back to basics

문제 배열에서 특정 요소가 과반수 이상 등장하는 경우 그 요소를 찾는 문제입니다. 과반수 요소는 배열의 길이 n의 절반 이상 등장하는 요소로 정의됩니다. 주어진 배열 nums에서 과반수 요소를 찾는 문제입니다. 과반수 요소는 항상 존재한다고 가정합니다.  풀이해당 문제는 Hash Map를 이용해서 풀 수 있습니다. 하지만 이 문제의 추가 조건으로 로 “문제를 O(n) 시간 복잡도와 O(1) 공간 복잡도로 해결할 수 있는지”가 주어졌습니다. Hash Map를 이용하면 공간복잡도가 O(n)으로 해당 조건을 만족할 수 없습니다. 해당 조건에 맞춰 문제를 해결하려면  Boyer–Moore majority vote algorithm를 이용하여 풀 수 있습니다.Boyer–Moore majority vote algo..

문제 주어진 문제는 Tribonacci 수열에서 n번째 항의 값을 구하는 것입니다. Tribonacci 수열은 이전 3개의 항을 더한 값으로 다음 항을 계산하는 특징을 가지고 있습니다. 풀이 주어진 문제를 해결하기 위해 다이나믹 프로그래을 활용할 수 있습니다. 다이나믹 프로그래밍은 중복되는 계산을 피하기 위해 계산 결과를 저장하여 재활용하는 기법입니다. Tribonacci 수열의 n번째 항의 값을 구하기 위해 다음과 같은 접근 방식을 사용합니다: 초기값 설정: dp 리스트를 생성하고 초기값으로 dp[0] = 0, dp[1] = 1, dp[2] = 1을 설정합니다. 반복문을 통한 값 계산: dp[i] = dp[i-3] + dp[i-2] + dp[i-1]을 반복문을 통해 계산하여 dp[n]의 값을 구합니다...

문제 주어진 문자열에서 모음(vowels)들만 뒤집어 반환하는 문제입니다. 모음은 'a', 'e', 'i', 'o', 'u' 다섯 가지로 구성되어 있으며, 대소문자를 구분하지 않습니다. 풀이 문자열을 처리하기 위해 투포인터를 활용하여 문제를 해결할 수 있습니다. 주어진 문자열을 리스트로 변환합니다. 이렇게 하면 문자열의 각 문자에 직접 접근하여 값을 변경할 수 있습니다. 파이썬에서 문자열은 불변한 자료형이므로 리스트로 변환하여 가변한 형태로 다루는 것이 유용합니다. 왼쪽 인덱스(left_index)를 문자열의 시작 위치(0)로, 오른쪽 인덱스(right_index)를 문자열의 끝 위치(len(s) - 1)로 초기화합니다. 왼쪽 인덱스와 오른쪽 인덱스가 만나기 전까지 다음 작업을 반복합니다: 만약 왼쪽 인..

문제 풀이 주어진 두 문자열이 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가지를 만들어서 계산하면 위 같은 케이스를 구분할 수 있다. 그런데 자바 HashMap에는 값이 있는 지 확인할 수 있는..

문제 풀이 왼쪽 값들의 합과 오른쪽 값들의 합이 일치하는 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

문제 풀이 주어진 2차원 배열에서 상하좌우 4방향으로 시작위치의 색과 같은 색이면 새로운 색으로 칠하면 되는 문제이다. dfs, bfs 풀이로 풀면 된다. 처음에 아래와 같이 작성했다가 Time Limit Exceeded 나왔다. class Solution { fun floodFill(image: Array, sr: Int, sc: Int, newColor: Int): Array { val baseColor = image[sr][sc] fun fill(row: Int, col: Int) { if (row !in image.indices || col !in image[0].indices || image[row][col] != baseColor) { return } image[row][col] = newCo..