본문 바로가기

전체 글657

[leetcode][191] Number of 1 Bits 문제 : leetcode.com/problems/number-of-1-bits/ 부호없는 정수 값이 input 값으로 주어질 때, 1비트 수를 구해라. brian kernighan's algorithm을 사용. n & (n-1) 연산을 n이 0이 될 때까지 반복한다. 연산 횟수가 1의 개수가된다. 시간복잡도는 O(logN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/191.%20Number%20of%201%20Bits.cpp 2021. 2. 2.
[programmers][2021카카오공채] 신규 아이디 추천 문제 : programmers.co.kr/learn/courses/30/lessons/72410 하라는대로 하면 된다. 입력값으로 받은 문자열을 앞에서부터 탐색하면서 6(길이가 16이상), 1(대문자 -> 소문자), 2(맞지않은 기호 패스), 4(콤마인데 정답 문자열이 비어있거나 정답문자열의 마지막이 콤마인지) 순으로 체크하고 문제없으면 answer 문자열의 뒤에 추가한다. 탐색이 끝난 후 4(정답 문자열의 뒤가 콤마라면 제거), 5(빈 문자열이면 'a' 추가), 7(길이가 3이상이 될때까지 가장 뒤에있는 문자를 추가) 순으로 조건을 만족하는 문자열을 만든다. 시간복잡도는 O(N). N은 문자열의 길이다. 소스코드 : github.com/fpdjsns/Algorithm/blob/master/program.. 2021. 2. 1.
[leetcode][1675] Minimize Deviation in Array 문제 : leetcode.com/problems/minimize-deviation-in-array/ n개의 양의 정수를 가지는 배열이 주어진다. 수가 짝수이면 2로 나눌 수 있고 홀수면 2를 곱할 수 있다. (복수번 적용 가능) 배열의 편차는 두가지 요소의 차이 중 최대 값이다. 구할 수 있는 배열의 편차 중 최소 값을 구하여라. 짝수면 감소. 홀수면 증가시킬 수 있다. 짝수를 2로 나누면 짝수 혹은 홀수가 나온다. 하지만 홀수를 2로 곱하면 반드시 짝수가 된다. 즉, 모든 요소들의 최대값들은 그 자신의 수(짝수인 경우)거나 x2한 수(홀수인 경우)이다. 따라서 모든 수들을 먼저 최대값으로 만든 뒤, 최대값을 감소시키면서 배열의 편차의 최소 값을 구한다. 구현은 set을 이용했고, 최대 최소는 set의 .. 2021. 1. 31.
[java] Enum 열거타입이다. 타입을 가지기 때문에 타입도 같이 체크할 수 있다. Enum 또한 클래스이기 때문에 멤버변수, 함수를 가질 수 있다. 정의하는 방법 public enum Week { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY } enum 키워드를 사용하여 정의한다. public enum Week { MONDAY("월요일"), TUESDAY("화요일"), WEDNESDAY("수요일"), THURSDAY("목요일"), FRIDAY("금요일"), SATURDAY("토요일"), SUNDAY("일요일"); private String desc; Week(String desc) { this.desc = desc; } public String getD.. 2021. 1. 30.
[leetcode][987] Vertical Order Traversal of a Binary Tree 문제 : leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/ 이진 트리 노드의 루트 노드가 주어진다. 루트 노드는 (0, 0) (x,y) 위치를 가지고 왼쪽 자식 노드, 오른쪽 자식 노드로 갈수록 (x-1, y-1), (x+1, y-1) 위치 값을 가진다. 동일한 x 좌표 값을 가지는 노드들의 val 값의 배열을 x 좌표의 오름차순 정렬하여 구하라. 만일 동일한 x 좌표 값을 가진다면 y 좌표의 오름차순 정렬된 배열을 가진다. y좌표도 동일하다면 노드의 val 값을 오름차순 정렬한다. dfs로 풀 수 있다. 루트노드로부터 왼쪽, 오른쪽 자식으로 탐색하면서 (x-1, y-1), (x+1, y-1)로 좌표 값을 갱신시킨다. x 좌표를 키값, (.. 2021. 1. 30.
[leetcode][23] Merge k Sorted Lists 문제 : leetcode.com/problems/merge-k-sorted-lists/ k개의 오름차순정렬된 ListNode 포인터 배열이 주어진다. 배열의 모든 ListNode를 오름차순 정렬된 하나의 ListNode로 만들어라. 오름차순 정렬되어있기 때문에 k개의 배열을 탐색하면서 가장 작은 노드를 구하고 이를 정답 리스트노드 다음에 추가한다. 추가한 노드는 다시 탐색되지 않게 하기 위해 next 노드를 보게 갱신한다. 항상 k개의 배열을 탐색하는데, 이를 정답 ListNode를 만들때까지 실행될 것이기 때문에. N = k, M = 정답 ListNode 배열 크기라 할 때, 시간복잡도는 O(NM). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/.. 2021. 1. 26.

티스토리툴바