코딩테스트 문제풀기 09: 명확하게 풀지 못한 문제 (수 조작하기 2)

(버그가 있는지 사진이 2개로 올라가져 있네요. 고쳐도 수정이 안되네요...)

코드 문제 풀이

function solution(numLog) {
	let answer = "";
    
    for (let i = 1; i < numLog.length; i++) {
    	if (numLog[i] - numLog[i - 1] === 1) {
        	answer = answer + "w";
        } else if (numLog[i] - numLog[i - 1] === -1) {
        	answer = answer + "s";
        } else if (numLog[i] - numLog[i - 1] === 10) {
        	answer = answer + "d";
        } else if (numLog[i] - numLog[i - 1] === -10) {
        	answer = answer + "a";
        }
    }
    return answer;
}

사실 이 문제는 이 numLog[i] - numLog[i - 1] 조건문을 완전히 파악 못했습니다.
문제 본문에 numLog[i] - numLog[i - 1] 이 적혀 있어서 이 조건이구나 생각하고 진행했습니다.

이부분은 chatGPT에 물어봐서 어느정도 파악했는데 마이너스 - 마이너스에서도 갑자기 안하던 산수를 하다가 막혀서 물어보고 파악해온 내용을 설명하겠습니다.

1. for문의 let i = 1 로 변수 선언하고 numLog의 길이만큼 i를 반복합니다.
2. numLog[i]는 numLog의 인덱스 1, 2, 3, 4... 인덱스 11까지 for문을 반복합니다. 인덱스는 1부터 시작하니 배열 속의 값도 1이네요.
3. numLog[i]의 첫번째 인덱스 값은 [0, 1, 0, 10, 0, 1, 0, 10, 0, -1, -2, -1] 에서
   두번째 숫자 1입니다.
4. numLog[i] - 1은 numLog[i]가 1이었죠. 그 이전 값 인덱스 0에 있는 0입니다.
5. 1 - 0 = 1이죠. +1은 w라 했으니 answer + "w"로 1은 w인걸 추가 해줍니다.
6. 이제 3-6번까지 반복합니다. numLog[i]의 두번째 인덱스 값은 0입니다.
7. numLog[i] - numLog[i] - 1 은 0 - 1 = -1 이 됩니다. 그럼 -1에 해당되는 "s"가 됩니다.
8. numLog[i] - numLog[i] - 1 을 계산하면 10 - 0 = 10 입니다. 이건 "d"
9. numLog[i] - numLog[i] - 1 을 계산하면 0 - 10 = -10 입니다. 이건 "a"
10. numLog[i] - numLog[i] - 1 을 계산하면 1 - 0 = 1 입니다. 이건 "w"
11. numLog[i] - numLog[i] - 1 을 계산하면 0 - 1 = -1 입니다. 이건 "s"
12. numLog[i] - numLog[i] - 1 을 계산하면 10 - 0 = 10 입니다. 이건 "d"
13. numLog[i] - numLog[i] - 1 을 계산하면 0 - 10 = -10 입니다. 이건 "a"
14. numLog[i] - numLog[i] - 1 을 계산하면 -1 - 0 = -1 입니다. 이건 "s"
15. numLog[i] - numLog[i] - 1 을 계산하면
    마이너스와 마이너스 계산은 -2 - (-1)이 되서 = -2 + 1이 됩니다. 그래서 -1, "s"
16. numLogi - numLogi - 1 을 계산하면 -1 - (-2) = -1 + 2 = 1이 됩니다.
    그래서 "w" 입니다.

여기 일일이 적으면서 조금씩 이해되는 것 같습니다.

---

다른 답 파악하기

function solution() {
	const convert = {
      	"1": "w",
     	"-1": "s",
      	"10": "d",
      	"-10": "a",
  	}
    return numLog.slice(1).map( (v, i) => {
    	return convert[v - numLog[i]];
    }).join();
}

1. const로 convert를 객체로 선언합니다.
2. convert 객체 안에는

키: "1" 값 "w"
키: "-1" 값 "s"
키: "10" 값 "d"
키: "-10" 값 "a"

을 대입합니다.

3. 반환하여 numLog의 첫번째를 slice로 첫번째 값을 잘라줍니다.
   (numLog 안에 배열은 [0, 1, 0, 10, 0, 1, 0, 10, 0, -1, -2, -1] 인 상태이며
   배열 맨 앞에 0은 계산할 때만 사용하고 실제로 사용하지 않음)
4. map함수를 사용해 v는 현재 값, i는 이전 값을 비교해 변화되는 값을 계산합니다.

v - numLog[i] 를 하면

[0, 1, 0, 10, 0, 1, 0, 10, 0, -1, -2, -1]
이 배열의 아주 맨 처음인 1(인덱스 1번째) - 0(인덱스 0번째)부터 시작합니다.

1 - 0 = 1
0 - 1 = -1
10 - 0 = 10
0 - 10 = -10
1 - 0 = 1
0 - 1 = -1
10 - 0 = 10
0 - 10 = -10
-1 - 0 = -1
-2 - (-1) = -2 + 1 = -1
-1 - (-2) = -1 + 2 = 1

을 계산합니다. convert에 담긴 1의 결과는 "w", -1에는 "s" 10에는 "d" -10에는 "a"
을 반환홥니다.
그러면 convert[v - numLog[i]] 는 배열 속에 결과 값인 ["w", "s", "d", "a", "w", "s", "d", "a", "s", "s", "w"] 가 나오고

5. 배열을 join("")하면 문자열로 바뀌어져서 "wsdawsdassw"가 됩니다.

---

풀어낸 문제 복잡도 분석하기

저는 일단 빅오 표기법 및 시간 복잡도, 공간 복잡도, 코드 최적화에 대해
깊은 이해가 없습니다. 그래서 chatGPT의 도움을 받아 작성하겠습니다.

요약의 내용은
시간 복잡도는 O(n)이며 numLog 배열의 길이만큼 반복하는 상태입니다.
공간 복잡도는 O(n)이며 결과 문자열이 반복 횟수만큼 길어져서 O(n) 입니다.

1. 시간 복잡도

   이 코드가 실행되는데 얼마나 시간이 걸리는 가? 를 계산하는 방법으로
   입력값이 클수록 얼마나 느려지는지를 확인

for (let i = 1; i < numLog.length; i++) {
	// 반복 내부 코드들
}

• 이 numLog 배열의 길이가 10개면 반복문은 9번 실행
• numLog 배열이 100개면 반복문은 99번 실행
• 배열 길이만큼 반복하는데 이거를 n만큼 반복한다고 표현합니다.
• 그래서 시간 복잡도는 O(n) 이며 n은 numLog.length
• (n은 입력으로 주어진 배열의 길이)

2. 공간 복잡도

   이 코드가 실행될 때 얼만큼 메모리를 사용하는가? 를 계산합니다.

let answer = ""; // 이 새로운 문자열을 하나 생성하면

• 반복문이 실행되면서 하나씩 글자가 붙게 됨 (for문 실행해서 저기에 넣음)
• 이 for문이 실행되는 게 9번 돌면 글자가 9개짜리 문자열이 만들어 짐

즉, 이 변수는 n에 비례해서 커짐 (반복 횟수와 동일)

그래서 공간 복잡도도 O(n)인데 이는 n이 numLog의 길이를 나타냅니다.

예시를 들자면

let numLog = [0, 1, 0, 10] // 일 때
for는 3번 반복합니다.
answer는 문자열이 3번 생깁니다.