반응형

알고리즘 24

[leetcode] 733. Flood Fill

문제 풀이 주어진 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..

알고리즘 2021.10.03

[leetcode] 278. First Bad Version

문제 풀이 bool isBadVersion(version) 함수가 주어지고 Bad가 처음 발생한 버전을 찾는 문제이다. 이진 탐색을 이용해서 풀면 되는 문제다. Kotlin으로 풀었는데 한 가지 주의할 점은 middle를 구할 때 (high + low)/2 이용하면 Integer 범위를 초과할 수 있어 Time Limit Exceeded 이 나온다. 대신에 low + (high - low)/2 를 이용하면 해결할 수 있다. (low + high)/2 = low + (high-low)/2 코드 /* The isBadVersion API is defined in the parent class VersionControl. def isBadVersion(version: Int): Boolean = {} */ c..

알고리즘 2021.09.26

[leetcode] 15. 3Sum

문제 풀이 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..

알고리즘 2021.08.07

[leetcode] 937. Reorder Data in Log Files

문제 인풋으로 주어진 로그는 식별자와 내용으로 구성되어 있다. 로그의 타입은 숫자로만 이뤄진 숫자 로그와 알파벳으로만 이뤄진 문자 로그로 구분된다. 로그의 순서는 다음과 같아야 한다. 숫자 로그는 문자 로그의 뒤에 와야 한다. 문자 로그 간의 순서는 내용의 사전식 순서여야 한다. 문자 로그의 내용이 같다면 식별자의 사전식 순서로 정렬한다. 숫자 로그 간 순서는 유지해야 한다. 풀이 로그가 숫자 로그인지 문자 로그인지를 구분하는 함수를 만들었다. 그리고 문자 로그 리스트를 아래 조건대로 정렬한 다음 숫자 로그 리스트를 덧 붙여서 해결했다. 식별자를 제외한 로그의 알파벳 순서 비교 만약 같다면 식별자의 알파벳 순서 비교 코드 그냥 생각의 흐름대로 풀었다. 나중에 solution이랑 discuss 확인해서 더..

알고리즘 2021.06.28

[leetcode] 125. Valid Palindrome

문제 풀이 주어진 문자열이 팰린드롬인지 확인하는 문제이다. 팰린드롬은 뒤집어도 같은 말이 되는 단어 또는 문장을 말한다. 문제에서 팰린드롬인지 확인할 때 알파벳과 숫자만을 대상으로 하고 대소문자를 구분하지 않는다고 했다. 우선 주어진 문자열을 다 소문자로 바꾼다. 그리고 정규식으로 알파벳과 숫자가 아닌 불필요한 문자를 제거한다. 이제 for 문을 돌면서 왼쪽 인덱스의 값과 오른쪽 인덱스의 값이 같은지를 확인한다. 왼쪽은 한 칸씩 오른쪽으로, 오른쪽은 한 칸씩 왼쪽으로 이동하면서 비교한다. 만약 비교한 값이 다르면 팰린드롬이 아니고 모두 같으면 팰린드롬이다. 코드 class Solution { public boolean isPalindrome(String s) { s = s.toLowerCase(); St..

알고리즘 2021.06.22

[leetcode] 771. Jewels and Stones

문제 풀이 문자열(stones)에 원하는 문자(jewels)가 몇 개가 포함되어 있는 지를 세는 문제이다. 대소문자를 구분하고 인풋은 영어 문자만 들어온다. 코드 jewels 를 Set으로 만들고 각 stone마다 순회하면서 포함되어 있으면 카운트를 늘리는 방식으로 풀었다. class Solution { public int numJewelsInStones(String jewels, String stones) { Set jewel = jewels.chars() .mapToObj(e->(char)e) .collect(Collectors.toSet()); int result = 0; for(Character stone : stones.toCharArray()){ if(jewel.contains(stone)){..

알고리즘 2021.06.19
반응형