※ 이하는 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※
[프로그래머스] 문자열 밀기
[프로그래머스] 문자열 밀기
나의 풀이:
// 016-문자열 밀기.js
// 시간복잡도는 O(N)
function solution(A, B) {
if (A === B) {
return 0;
}
// 오른쪽으로 미는 것이므로 만들어지는 순환 문자열은 잘리는 부분 i가 오른쪽 끝부터 왼쪽으로 이동해야 함.
for (let i = A.length - 1; i > 0; i--) {
// 시간복잡도 O(1)
const newString = A.slice(i) + A.slice(0, i);
if (newString === B) {
// 반환하는 값은 length - i
return A.length - i;
}
}
return -1;
}
테스트 코드:
// 016-문자열 밀기.test.js
const { solution } = require('./016-문자열 밀기')
describe('String push', () => {
[
{ A: 'a', B: 'a', result: 0 },
{ A: 'ab', B: 'ab', result: 0 },
{ A: 'ab', B: 'ba', result: 1 },
{ A: 'abc', B: 'abc', result: 0 },
{ A: 'abc', B: 'cab', result: 1 },
{ A: 'abc', B: 'bca', result: 2 },
{ A: 'abc', B: 'cba', result: -1 },
{ A: 'hello', B: 'ohell', result: 1 },
{ A: 'apple', B: 'elppa', result: -1 },
{ A: 'atat', B: 'tata', result: 1 },
{ A: 'Alex, listen. Theres only one way for us to win this.', B: 'ten. Theres only one way for us to win this.Alex, lis', result: 44 },
].forEach(({ A, B, result }) => {
it(`should return ${result} when string A and target B are [${A}, ${B}]`, () => {
expect(solution(A, B)).toBe(result);
})
})
})
알게된 것:
- 자바스크립트 V8 엔진의 string.slice()의 시간복잡도는 O(1)로, O(N)이 아니라고 한다. (참조: https://stackoverflow.com/questions/47733645/what-is-the-algorithmic-complexity-of-string-slicing-practical-real-world)
- === 연산자의 뜻은 ‘값이 같고 참조 주소도 같다’가 아니라 ‘값과 타입이 같다’는 의미의 strict equal이었음을 복습함.
[프로그래머스] 종이 자르기
[프로그래머스] 종이 자르기
풀이 과정:
일단 잘라야 하는 총 단면은 총 n(m-1) + m(n-1) = 2mn - m - n개이다. 거기서 '절약될 수 있는 단면 가위질 수'를 빼면 된다.
절약될 수 있는 단면 가위질 수 = (m-1) * (n-1)
따라서 총 단면 - 절약되는 단면 = 2mn - m - n - (mn - m - n - 1) = mn + 1(?!!!)
다른 관점:
=> 겹쳐서 자를 수 있었다면, (m-1)(n-1)이었을 것.
=> 겹쳐서 자를 수 없을 땐 우선 m-1번만큼 길~게 길게 자르고, 그 후 생긴 m개의 1 x n 조각을 n-1번만큼씩 잘라야 하므로 (m-1) + m(n-1)가 된다.
풀이 코드:
// 015-종이 자르기.js
function solution1(m, n) {
const totalUnit = n * (m - 1) + m * (n - 1) // = 2mn - m - n
const totalSaved = (m - 1) * (n - 1) // = mn - m - n - 1
return totalUnit - totalSaved; // = mn - 1;
}
// 식도 더 깔끔히
function solution2(m, n) {
return m * n - 1;
}
module.exports.solution = solution2;
테스트 코드:
// 015-종이 자르기.test.js
const { solution } = require('./015-종이 자르기');
describe('Cut paper', () => {
// 한 변이 1인 경우
it('should return 0 when given size is (1 x 1)', () => {
expect(solution(1, 1)).toBe(0);
})
it('should return 1 when given size is (1 x 2)', () => {
expect(solution(1, 2)).toBe(1);
})
it('should return 3 when given size is (4 x 1)', () => {
expect(solution(4, 1)).toBe(3);
})
// 양 변이 같은 경우
it('should return 3 when given size is (2 x 2)', () => {
expect(solution(2, 2)).toBe(3);
})
// 양 변 길이가 다른 경우
it('should return 9 when given size is (2 x 5)', () => {
expect(solution(2, 5)).toBe(9);
})
it('should return 19 when given size is (4 x 5)', () => {
expect(solution(4, 5)).toBe(19);
})
})
Uploaded by N2T