4/18 화 (문제풀이) TIL

※ 이하는 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

[프로그래머스] 문자열 밀기

https://school.programmers.co.kr/learn/courses/30/lessons/120921

나의 풀이:

// 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이었음을 복습함.

[프로그래머스] 종이 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/120922

풀이 과정:

일단 잘라야 하는 총 단면은 총 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