문제 + 생각의 방향(Optional) + 코드
codility는 문제 저작권 문제로 문제는 복붙 불가...
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given a 32-bit signed integer, reverse digits of an integer.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the
reversed integer overflows.
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Follow up:
Coud you solve it without converting the integer to a string?
string으로 바꾸면 분명 쉽게 풀릴거 같았지만, 숫자로만 컨트롤 하다보니, 쉬운 문제임에도 머리를 꽤나 많이 썼다.
최소한의 반복문을 통해 각 자릿수 비교를 정확하게 해내는게 관건인거 같다.
더보기
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if (x < 0) return false;
if (x < 10) return true;
if (x < 100 && x % 11 === 0) return true;
if (x < 100 && x % 11 !== 0) return false;
if (x % 10 === 0) return false;
let digit = 3;
while (true) {
if (x - Math.pow(10, digit) < 0) break;
digit += 1;
}
let halfDigit = Math.floor(digit / 2);
let forward;
if (digit % 2 === 0) {
forward = Math.floor(x / Math.pow(10, halfDigit));
} else {
forward = Math.floor(x / Math.pow(10, halfDigit + 1));
}
let backward = x % Math.pow(10, halfDigit);
if (digit === 3 && (forward === backward)) return true;
let reverseBackward = 0;
for (let i = halfDigit; 0 < i; i--) {
reverseBackward += (backward % 10) * Math.pow(10, i - 1);
backward = Math.floor(backward / 10);
}
if (reverseBackward === forward) return true;
return false;
};
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
더보기
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
const symbol = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000
}
let result = 0;
const sLen = s.length;
if (sLen === 1) return symbol[s];
for (let i = 0; i < sLen; i++) {
if (symbol[s.charAt(i)] < symbol[s.charAt(i + 1)]) {
result += symbol[s.charAt(i + 1)] - symbol[s.charAt(i)];
i++;
} else {
result += symbol[s.charAt(i)];
}
}
return result;
};Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
더보기
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if (s.length % 2 === 1) return false;
if (s.length === 0) return true;
for (let i = 0, sLen = s.length; i < sLen / 2; i++) {
s = s.replace("{}", "").replace("()", "").replace("[]", "");
if (s.length === 0) return true;
}
return false;
};Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
더보기
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (!needle) return 0;
return haystack.indexOf(needle);
};Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5 Output: 2
Example 2:
Input: [1,3,5,6], 2 Output: 1
Example 3:
Input: [1,3,5,6], 7 Output: 4
Example 4:
Input: [1,3,5,6], 0 Output: 0
더보기
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
if (target === 0) return 0;
let result = nums.indexOf(target);
if (result !== -1) {
return result;
} else {
for (let i = 0, len = nums.length; i < len; i = i + 2) {
if (nums[i] > target) return i;
if (!nums[i + 1] || nums[i + 1] > target) return i + 1;
}
return nums.length;
}
};처음 받아본 피드백
아래 바이너리갭 알고리즘 풀면서 처음으로 받아본 피드백.
진짜 잘하시는 시니어 개발자에게 피드백을 받을 기회를 얻은 것만으로도 열심히 산 값어치가 있는거 같다. 나도 계속 성장해서 나와 같은 개발자들을 많이 도와줘야겠다.
1. 자연스럽게 코드를 짜라.
생각해 보이면, 겉멋인지 몰라도 적은 연산, 복잡한 로직에 초점을 맞춘거 같다. 생각해 보면 나는 알고리즘 경연대회에 나가는게 아닌데, 왜 계속 그 부분에 목맸는지 모르겠다.
2. return문을 줄여라.
return문이 많다는건 그만큼 로직이 복잡하고 잘못되었다는 것이다.
3. 고민하고 생각해라.
바로 코딩부터 하지말고, 어떻게 해결하면 될지 전략을 짜라. 개발자가 실제로 코드를 치면서 개발하는 시간은 전체 시간 중에 50%를 넘지 않는다. 나머지 시간에는 모두 생각하고 생각하고 정리하며, 문서화하는 시간이다.
지금부터 다시 알고리즘을 공부한다는 생각으로 다시 해보자.
가장 큰 binaryGap을 구하는 문제
예) 1001 -> 2
예) 1000 -> 0
예) 1010001 -> 3
예) 10100100000 -> 2
더보기
function solution(N) {
let n = N;
// Create binary arrary
const digits = n.toString(2).split("");
console.log("digits", digits);
// Define
let start = 0;
let end;
let gap = 0;
// Loop
for (let i = 1, len = digits.length; i < len; i++) {
if (digits[i] === "1") {
end = start;
start = i;
// 현재 gap이 더 작은 경우만
if (gap < start - end - 1) {
gap = start - end - 1;
}
}
}
return gap;
}순환 로테이션
정수로된 배열 A을 K번 순환시켰을 때의 배열을 반환해라.
ex) A = [3, 8, 9, 7, 6], K = 3
[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
A) solution(A, K) = [9, 7, 6, 3, 8];
ex) A = [1, 1, 1], K = 10000
A) solution(A, K) = [1, 1, 1];
1) 풀이1
더보기
function solution(A, K) {
let arr = A;
let index = K;
let lastValue;
if (arr.length) {
while (index !== 0) {
lastValue = arr.pop();
arr.unshift(lastValue);
index--;
}
}
return arr;
}
2) 풀이2 - pop(), unshift() 쓰지 말고 구현해보라고 하셔서, 다시 한번 구현
더보기
function solution(A, K) {
let arr = A;
let arrLength = arr.length;
let k = K % arrLength;
let result = [];
if (arrLength !== 0) {
for (let i = 0; i < arrLength; i++) {
if (i + k >= arrLength) {
result[i + k - arrLength] = arr[i];
} else {
result[i + k] = arr[i];
}
}
} else {
result = A;
}
return result;
}주어지는 배열에서 unpair한 값을 찾아내기.
ex) N=[3, 6, 6, 7, 3] // pari [3,..., 3] [6, 6]
solution(N) => 7
ex) N=[3, 6, 6, 7, 3, 7, 1] // pari [3,..., 3] [6, 6] [7, ..., 7]
solution(N) => 1
더보기
Time complexity: O(N) or O(N*log(N))
function solution(A) {
let arr = A;
let hashtable = {};
for (let i = 0, arrLen = arr.length; i < arrLen; i++) {
if (!hashtable[arr[i]]) {
hashtable[arr[i]] = arr[i];
} else {
hashtable[arr[i]] = undefined;
}
}
return Object.values(hashtable).filter(v => !!v)[0];
}function solution(X, Y, D) {}
3개의 양의 정수가 주어짐, X는 D만큼 증가하며, Y보다 작거나 클때까지 증가.
X >= Y 가 되는 최소한의 횟수를 구하면 끝
더보기
// O(1)
function solution(X, Y, D) {
let x = X;
let y = Y;
let d = D;
let result = Math.ceil((y - x) / d);
return result;
}function solution(A);
A = [1 ... (N+1)]
N = [0...100,000]
A 배열에서 비어있는 엘리먼트를 찾기
ex) A[0] = 3 A[1] = 2 A[2] = 1 A[3] = 5
정답은 4
더보기
// O(N) or O(N* log(N))
function solution(A) {
let n = A;
let newN = new Array(n.length);
for (let i = 0, newNLen = newN.length; i < newNLen; i++) {
newN[n[i] - 1] = n[i];
}
return newN.findIndex(v => !v) + 1 || newN.length + 1;
}반응형