프로그래머스 코딩테스트 KAKAO (JavaScript)

카카오 코딩테스트 문제를 풀이하며, 주로 고민했던 내용들 입니다. 주로 아쉬웠던 부분을 정리했습니다.

• 이진트리
• 데이터 테이블 생성
• 엣지케이스(MECE)
• 선언적 코드 ↔ 절차적 코드(count변수, index변수, start변수, end변수 .... 예측불가. 과연 맞나?)
  메모이제이션 배열 개수
• MECE
• 정규표현식
• 효율성
• 특이한 케이스
• 시간복잡도와 중첩 반복문
• 나쁜 코드 작성 습관(미리 일부 케이스를 셋팅해놓기, answer에 해당하는지를 먼저 if문으로 작성해서 인덴트 증가, 많은 조건문)
• 제너레이터 사용으로 early return
• 함수화 하는 이유: 모듈화 및 테스트
• 정보를 분리해서 생각하기(서로 어떤 시점의 데이터가 필요한지. 뭔가를 합쳐서 생각하고 있을 수도)
• 반례 찾기 연습
• 선언적으로 작성하는 방법 고찰. . . 

JS 메소드

메소드	내용 정리
Array.prototype.splice()	(시작인덱스:음수 가능, 삭제할 개수:0이면 삽입, 삽입할 아이템) return 제거한 요소를 담은 배열(원본 수정) 배열을 splice하면 index++ 하지 않아도 된다. 다시 사용하지 않는 경우, 코드를 삭제해서 간결하게 만들 수도 있다.
Array.prototype.slice()	string도 slice 가능 return 새로운 배열(원본 유지)
String.prototype.substring()	return 부분 문자열
String.prototype.replace()	정말 신기한건, replace의 두번째 인자로 함수가 가능하다는 것!! 즉, (word) => word === 'something' ? 'changed' : 'maintain'
Array.prototype.sort()	문자열 정렬은 조건 분기, return 1, -1, 0
String.prototype.localeCompare()	위의 문자열 정렬에서 조건문으로 분기하지 않고, 직접 문자열을 비교하는 메소드  referenceStr.localeCompare(compareString)
parseInt
toString	N진법으로 바꾸는 방법 number.toString(N)
String.prototype.substring()	인자가 2개면, 시작점과 마지막 인덱스를 나타냄 인자가 1개면, 시작점부터 문자열 가장 마지막까지를 나타냄

 
정규표현식(RegExp)

()
{}
[]
'^'
/\^/

 

2021 KAKAO BLIND RECRUITMENT 순위 검색

이진트리

index 삽질
- 이진트리의 index를 제대로 관리하려면, -1과 +1 및 종료조건에 등호가 필요하다.
- 그리고, 범위에 들어온다면 값을 저장하기
- 재귀 형태외에 간단하게 while문으로 구현이 가능하다.

데이터 테이블 생성 (mapping)

어떤 것을 기준으로 테이블을 만들까?

1.모든 가능성
2.사용자 입력(info) 기반
3.쿼리문(query) 기반

- 합리적으로(?) 봤을 때 개발 언어 3종류, 직군 2가지, 경력구분 2가지, 소울푸드 2가지
→ 4*3*3*3 개의 key를 만들고, 하나씩 대입하는 방법이 맞을거라 생각했다. ▶ 1번
- 일반적으로 입력은 어떻게 들어올지 모르기 때문에, 가능성 모두를 마련해야 한다고 생각했다.
- 그런데, 효율성 테스트를 통과하지 못해서 한참 고민했는데 info를 기준으로 조금이라도 반복문 자체에 진입하는 것을 줄였더니 통과했다.
- key를 공백없이 join하는 방법도 있지만, 경우에 따라 글자가 이어져서 단어를 구성하는 경우도 있어서 그럴 일이 없는지 확인이 필요하다.

엣지케이스

- 떠오르지 않을 수 있고, 테스트케이스에서는 다 맞는 것처럼 보일 수 있다.
- 이 때 내 코드가 MECE로 표현되었는지 확인해보자, if-else 문 확인하기부터 시작한다.
틀리고 나서 어떤 특정한 케이스를 떠올리는건 어려우니까, 연습할 때만이라도..
MECE(Mutually Exclusive Collectively Exhaustive의 약자, 상호배제와 전체포괄)는 항목들이 상호 배타적이면서 모였을 때는 완전히 전체를 이루는 것
 
생각보다 다른 사람의 코드를 읽고 내 코드와 비교하는데 시간이 필요하다.
하나씩 고쳐가면서 오답노트를 해야해
가장 중요한건 내가 모르는 지점이 어디이고 계속 어디를 빙글빙글 고치고 있는지를 확인해야 한다는 건데
생각보다 RegExp를 익혀두고
 메소드를 잘 익혀두어야 코드가 간결해지고, 선언적 프로그래밍이 가능한 것 같다.
 
2020 KAKAO BLIND RECRUITMENT 괄호 변환
array와 string을 왔다갔다 했는데, 그럴 필요가 있었을까.
- 굳이 array로 변환하지 않아도 된다. push는 += '' 로 대체할 수 있고, slice splice는 substring으로 대체가 가능하기 때문
if - else에서 count +=를 한다면?
 
replace()를 효율적으로 사용하는 방법을 다른 분들의 코드를 보고 배웠다. word.replace( /\(|\)/g , w=> w ==="(" ? ")" : "(" );
length를 꺼내서 쓰지 않고도 가능한 방법이 있을까?

2018 KAKAO BLIND RECRUITMENT [3차] 파일명 정렬
정규표현식
각 요소로 정렬할 수 있는지 확인
 
2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기
조건1: 0P0, P0, 0P, P 에 해당하는 수 찾기
조건2: P가 소수인지 확인

선언적 코드

조건을 구분했고,
조건 1을 stack에 push하는 방법으로 구했다. 그런데 역시나 조건문이 들어가면서 코드가 복잡 (완전히 절차적)
조건 2에서, 가장 큰 수를 기준으로 메모이제이션을 하면 낭비가 줄어드는 것 같아서 코드를 작성했지만, 런타임 에러 혹은 실행 시간 초과
 
조건 1의 경우 코드가 조악하더라도, 더 조악해지지 않아서 다행이라고 생각했는데, (내 경우에는 stack, 0만나면 pop)
선언적으로 작성한다면 split('0')이 가능했다. 맙소사. 다들 어떻게 이런 방법을 생각해내는 거지..
내 경우에는 조건을 하나씩 경우에 따라 구분하면서 if문으로 분기를 만들었지만,
다른 분들은 결과를 분석해서 문장으로 표현하셨던 것 같다.
 
조건문이 if if if .. 계속 중첩되면 코드가 이해하기 복잡해지고.. 특히 count, index, 이런 변수들이 늘어나면 예측 가능성이 떨어지는 것 같다. 어떻게든~~ 조건을 세분화해서.. 하려고 한 결과가 오히려 코드를 더 복잡하게 만드는 것 같다. 매번 조건문을 붙여가면서.. 뭔가를 하려고 하는데 여기서부터 문제인 것 같다는 생각이 든다..
중첩 반복문이 겁난다면.. 분리를 해주면 되나?
인덴트가 너무 들어가게 되면 다른 방법이 가능한지를 생각해보는게 맞을까? 아니면 함수화를 하는게 맞을까?
 

메모이제이션 배열 개수

조건 2의 경우, 합리적이라고 생각했지만 비합리적인 결과를 초래했다.
왜? 메모이제이션의 경우 배열의 갯수까지 헤아려야 했기 때문인데.. 만약 가장 큰 수가 111,111,111 이런 자릿수를 갖게 된다면 배열 길이가 1억개 이상이 되어야 한다.
시간초과 문제가 있는줄 알았기 때문에, 반복문 효율성 문제인줄 알았는데 오히려 아니었음.
 
소수
 
2022 KAKAO BLIND RECRUITMENT 양궁대회

백트래킹

 

MECE

백트래킹에서 early return 하기 위한 방법이 오히려 재귀 최고 깊이를 초과해버리는 결과를 발생시킴
n이 3일 때, [3,1,1,0,0,0,0,0,0,0] 여기서 index가 3에 왔을 때 rest가 0이니까 멈춘다고 생각했는데,
[3,1,0,0,0,0,0,0,0,0]이 상황에 rest 는 1이고 멈출 방법이 없었다.
 
currentIndex를 단일 종료조건으로 두면 낭비가 심할 것 같다는 생각이었기 때문에
push와 pop대신 대입하는 방법을 사용해보려고 했는데 오히려 재귀 깊이가 너무 깊어졌다...
 
생각보다 MECE를 못하나보다. . .
0이니까 멈춘다 에서 그치는게 아니라,
생각하지 못했던 방식으로 동작하는 경우
0이 아니기 때문에 멈추지 않는 조건을 생각해보는게 맞겠지. 0이 아니면서 마지막 인덱스에서 멈추지 않는 이유

조건문의 반대의 경우도 떠올려봐야 하고
조건문 안에 포함되는 세부 조건도 생각해봐야 할 것 같다
 
2018 KAKAO BLIND RECRUITMENT [3차] n진수 게임
첫 코드에 굉장하게 절차적인 코드를 사용해서 마음이 좋지 않았던 문제.
왜 그렇게 낭비를 줄이려고 했을까
조금이라도 줄여보려고 여러가지 변수를 만들어서 했는데(start,end,count ... ), 복잡한 코드가 되어버렸다..
 
2019 카카오 개발자 겨울 인턴십 불량 사용자
정규표현식을 사용하고 싶었지만, 못해서 반복문으로 일치 여부를 판단했다.
이스케이프 문자
 

특이한 케이스

예시 케이스 , 의문이 생기는 케이스
(중복되는 경우가 있는지)
 
효율성
효율성을 통과하려면 코드라인을 늘리는 것 외에 줄이는 방법도 생각해야 하는거 아닐까? if문 늘리기는 복붙하면 쉬우니까.. 그렇지만 연산량이 늘어나는 것 같다. 덩달아 시간도..
그런데 단순히 조건문을 붙인다고 효율성을 통과하는건 아닌 것 같다. 아예 반복문을 줄이는 방법?
1. 맨 처음 모든것을 다 데이터 테이블에 넣지 않아보기 (위에서도 발생한 문제였지만)
2. 투포인터의 경우에 (이진탐색도 ?) 반복문 안의 반복문은 더 빠르게 감소시킬 수 있다. 오히려 반복문을 배제하려는 생각이 문제해결을 어렵게 만드는 것 같다.
3. 꼭 하나씩 남는 경우가 있는데..

2019 카카오 개발자 겨울 인턴십 징검다리 건너기

시간복잡도와 중첩 반복문

처음 접근 방법
1. k 구간내에서의 최소값과 최대값의 차가 가장 작은 구간 찾기
2. 시간복잡도 문제가 있기 때문에, 한번 순회에 해결해야 ..
3. 문제는 구간 내의 최소값과 최대값 관리를 어떻게 할 수 있지? Map? 최소힙이어도.. 정렬하는데 시간이 소요되는데..
 
정렬 NlogN보다 더 줄일 방법이 있나? 를 더 고민했는데
이진탐색 logN..
순회해야 할 요소가 많기 때문에, 반복문 안에 반복문이 들어가면 안된다고 생각했는데.. 
O(N)이더라도, logN이라면 가능하고, 이보다 더 작다면 가능한 방법이었다.
 
if문 내 조건이 2개 이상이라면? (조건 하나만 생각하는 것 말고)
 
이진탐색은 정렬된 요소에서만 가능하다는 선입견이 있었는데.
최소값과 최대값이 있기 때문에 어떤 값을 기준으로 해서 돌다리 숫자를 빼줄지가 중요했다.
 
Math.max(...array)를 할 때 주의점. 인자가 배열이 아니기 때문에, 런타임 에러가 발생할 수 있다.
 
결국 생각해보면,
중첩 반복문을 피하려고 하는건 잘못됐고,
최소 최대가 있다고 해서 무조건 이진탐색을 떠올린다기 보다, 
몇 개를 돌다리에서 빼야 하는지가 결국 힌트일지도. 브루트포스 말고(?) 직관적이게..?
 
2020 카카오 인턴십 보석 쇼핑
효율성
spread 연산자의 시간복잡도는 O(n). size property 사용하기 (length인줄 알아서 없다고 생각했는데 size..였음)
early return을 위해 if문이 있는건 연산량에 미미한 차이가 있지만, 없다면 꽤 시간이 많이 차이나게 되는 경우가 존재
 

나쁜 코드 작성 습관

코드를 작성할 때 습관이 있다는 것을 알게됨
1. 가장 처음에 뭔가 정리해놓고 시작함. 처음 n개의 보석을 미리 맵에 저장하고 반복문을 시작함.
2. 조건문이 많다. (인덴트가 많이 필요함)
3. 처음 반복문 진입시 딱 그 조건에 해당하는(answer를 찾는) 경우를 먼저 작성함. 그래서 분기가 생김. 그래서 가장 마지막에 늘 항상 연산이 남게되고, 그래서 반복문을 탈출했어도 스택을 비우거나 하는 상황이 필요해서 또 중복으로 코드를 작성하게 됨 (생각의 방향을 완전히 거꾸로).. 체크를 가장 마지막에 하는 방법
 
 
2020 카카오 인턴십 경주로 건설
최단거리가 아니어도 가능한데..
만약 dfs라면.. 시간이 꽤 걸릴 수 있다?
중간에 조건문을 추가하면서 일부는 효율성을 통과했지만, 더 줄여야 했다.
조건처럼, 직선이 더 많은 편이 가장 좋은데. 직선을 먼저.. 방문하는 방법? .. 직선인 경우부터 먼저 direction에 넣기까지 했는데도 시간초과 4개 케이스.. (10,11,18,19)
방향을 3개로(이전에 왔던 곳 제외) 해도 통과가 안됐고
 
2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠
왜 너무 당연하게 0,0에서 시작했을까. (n-1,n-1)까지는 했는데
 
제너레이터 사용
 
 
함수화하는 이유
모듈 단위로 분리하면서 코드 테스팅이 간단하다.
 
2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물

정보를 분리해서 생각하기

 
누적합을 생각해보기는 했는데, 이끌어내지는 못했다.
왜? 이 문제는 ‘건물 하나’의 상태를 구하는 것이지, x개 건물 상태의 합이 아니라고 생각했기 때문에.
누적합을 적용한 대상이 틀렸다.
 
다만 최악의 경우 25,000개의 데이터를 100*100을 하는건 말이 안되기 때문에
(1) 일단 25,000개는 25,000개 순회하는 것으로 그쳐야 한다는 생각을 했고
(2) 2중 반복문을 내부에 두면 안되고
(3) 어쨌거나 특정 구간에서 모두 같은 데미지를 입는다. (어떻게 생각하면 중복)
(4) 파괴와 회복을 분리 한다면? 그렇다고 하더라도 최악의 경우라면 동일하다.
 
한번에 처리해야 한다는 생각을 하게 되면서,
 
순회할 때마다 Set add delete는 마찬가지로 효율상 안되고,
Map은? 구간을 모두 순회하면서 일단 mapping을 하나? (X) 꽤 많은 조합이 발생하고, key를 구간으로 하고 배열을 넣는다고 하더라도.. 결국 파괴된 부분을 위해서는 중첩 반복문이 필요하다고 생각했다. (그냥 skill을 하는 것과 똑같은 ..)
 
결론적으로 25,000을 한 번만 순회하려면
r1,c1,r2,c2 좌표를 다른 방식으로 이용해야 하고,
해당 구간에서는 모두 동일한 정도로 효과가 발생한다. 여기서 누적합 느낌이 들었던 것 같다.

그런데 반복문을 지연하는 방법이 있나? 특정 구역이 정해지면 반복문을 돌려야 하는데.. 반복을 나중으로 어떻게 미루지? 모든 degree에 대한 반복을 나중에 전체 순회하는 것으로 한번만 하고싶은데.
결과적으로 (중첩된) 그림만 그리지 말고, 특정 값들이 어떻게 중첩되어 표현되는지를 직접 배열에 나타내봤어야 했다.
 
내가 놓쳤던 부분은 정보를 분리하지 못했다. 앞서 말한 문제 때문에..
한번에 동일하게 적용되어야 하는건 degree에 대한 데이터지, 건물 상태 데이터가 아니다.
한끗 차이인데 ‘아 건물 내구도는 배열 요소 각각이 다르니까 적용하지 못할 것 같아’라고 생각해서..
두개의 데이터를 분리해서 생각해보자
 
2018 KAKAO BLIND RECRUITMENT [1차] 셔틀버스
 

반례 찾기 연습

문제에도 나와있듯이, 

선언적 코드 고찰

1. 배열 기준
흠...
이번에도 버스 배차 시간표를 먼저 초기화 했다.. 정리부터 해야 한다고.. 생각해서.. 그래서 코드가 또 길어짐
정리를 하고, 마지막 부터 앞으로 와야지 했던 문제.
처음에 초기화를 ([09:00, 09:01, ... ]) 하지 않았다면, 배차 횟수를 기준으로 반복하면서 배차시간 업데이트가 동시에 이루어질 수 있다.
"마지막 시간" (1) 보다 작아야 (2) 같다면 (3) 크다면 
 
어떻게 해야 절차적으로 생각하지 않고, 선언적으로 생각할 수 있는걸까
내 코드가 복잡하고 길어지는 가장 큰 이유는 if 조건문들이 많고, 특히나 과정 중심으로 서술되어 있다.
문제를 풀 수는 있지만, 코드를 작성하면서도 이건 좀 아니지 않나 싶은 경우가 특히 코드가 한줄한줄 서술된 경우.
뭘 하고, 뭘 하고, 뭘 하고, 뭘 하고...
 
시간의 경우는 가장 마지막에만 특정 형식으로 반환해줄 수 있다. 사용할 때는 시*60+분을 사용하기.
 
배열을 splice하면 index++ 하지 않아도 된다. 다시 사용하지 않는 경우, 삭제해서 코드를 간결하게 만들 수도 있다.
 
조건문으로 먼저 나누면서 생각하지 말고, 한번에 관통하는 규칙이 있는지를 생각해보는게 도움이 되려나?
이번에는 n번째 요소와 n-1번째 요소를 비교하면서 생각했기 때문에
n-1번째 요소가 n번째  요소보다 작다면 n번째 요소에서 -1을 했다.
그런데 이 부분을 n번째를 가장 마지막 요소로 치환하더라도 결국 같은 결과..

경주장 건설
어려웠던 점
visit관리(복사량 장난 아님)
백트래킹이 답은 아님. 결국 bfs +메모이제이션

틀린 코드를 비교하면서 잘 된 코드와 차이를 잘 모르겠다는 생각이 들고 좌절함
일단 visit을 복사하는건 느낌만으로도 틀렸다는건 알겠음
두번째 시도에서 왜 일부케이스가 틀렸는지 느낌이 오는 한 줄이 있었는데, 여차저차 해서 그렇게 생각이 흘러간 것이 어떻게 못 고치나… 싶어서 속상했음
그래서 되짚어봤는데, 문제는
1. 다음을 예측한 것임 (현재만 충실할 것)
2. 이상하게 하면 애매해짐 : 커브 구간을 어떻게 표현할지
나머지는 3차원 배열이 어떻게 생겼는지
반례에 딱 걸리는 경우는 케이스를 잘 나누지 않아서 생기는데
종종 그런 부분이 너무 어려웠음
위에서 언급한 것처럼 미래에 대해 케이스를 나누면 좀 복잡해지고 딱 지금 할 것만 경우를 잘 나누면 어느정도 가능할 것 도 같다(지금 느끼기에는)
그리고 커브 구간 정의를 잘 해야 함. 언제 더해줄지 지금 더할지 다음에 더할지, 다음에 더한다는건 어떤 연산을 하는지
뭐 그런거.. js로 풀면서 shift연산 속도를 조금 의심했지만 이 문제는 shift 효율성 문제는 아니었음
3차원 배열도 어떤걸 저장할지 그리고 그 물리적인 형태를 떠올리느라 조금 어려웠던 것이랑, 결정적으로는 미래의 어떤 지점에 연산되는 내용이 단순히 직전 값을 더하는 것과 다르다는 점

 

광고 삽입

 

[새로운 생각] 예측되지 않는 것을 생각해봤다.
(예측이 되는 것은 생각 못함)

 

어쨌든 문제에서 logs는 300,000 인데 이건 순회 한번으로 어떻게 처리해야 한다는 의미가 있다.

n^2이면 시간초과가 되니까 logs를 일단 어떻게 해야한다는 의미라고 생각했다.

 

일단 구해야 하는건 시간과 겹치는 횟수인데,

이 때 겹치 구간이 몇 개 인지는 예측을 할 수 없다. 그리고 시간이 얼마나 걸리는지도 데이터에 따라 다름.

 

...

처음엔 종료시간, 시작시간 기준으로 정렬을 해서, 시작시간과 종료시간으로 시간 핑을 찍어주고 Set에 저장

그 상태에서 새로운 핑 기준으로 다시(..) 배열을 순회하면서(..) 핑이 포함되는 구간들을(..) 넣어주는데

..

 

이렇게 하면 문제가 제거해야 하는 것을 찾아야 하는데도 순회가 필요하다.

Map으로 어찌어찌 정리한다고 하더라도 지금 이 모든 과정이 일단 너무 복잡하다.

뭔가 잘못됐다는 생각이 들고... 예측되지 않는 요소(결국 순회하게 되는 결과)가 너무 많다.

일단 예측되지 않는걸 뭔가 하려고 하면 굉장히 복잡하게 계산되는 문제였음.

 

사실 가능한가?..

 

근데 문제를 풀 때마다 생각하는건, 매번 새로 접근하는 느낌이 아니라(문제를 많이 풀어보는 것도 중요하지만)

접근법을 매뉴얼화 하고 싶었다.

너무 디테일하게 하지는 못하더라도, 가끔씩 생각이 엇나가게 되는 부분이 있어서 뭐가 문제인지는 짚어보자는 생각으로

 

그런데 다시 뒤집어서 생각해보면 "예측 할 수 있는 것"이 있다.

 

시간에서, 구간 개념을 정의 할 수 있다. 초당 시간이다. 1초는 1초다.

 

코딩테스트 연습

... 문제를 순서대로 푼다는 생각을 못했다.

시간이 초과되더라도 더 많은 능력치가 오르는게 나은가?

 

표 편집

양방향 링크드 리스트
[문제 봉착]
어떤 방법으로 링크드 리스트를 구현 할지
'C'(삭제) 일 때 - (1) 노드 자체를 삭제한다 (2) prev next를 null로 바꾼다 (3) 그냥 무시하고 prevNode의 next, nextNode의 prev를 바꾼다

 

C를 (1) 노드 자체를 삭제한 경우로 정했을 때,

Z(되돌리기)하면서 문제가 됐던건 반복문인데, 처음엔 삭제 한 것의 prev와 next를 어떻게 알지? 였다.

앞에 n개 중 삭제되지 않은걸 어떻게 찾지?

그런데 C에서 노드를 삭제하지 않고, (3) 번처럼 무시한 경우 prev가 prev로 유지된다. 이건 직접 노드들을 펼쳐놓고 삭제하고 되돌리기를 해봐야(... 내 경우는..) 아는데,

해당 노드를 삭제하기 전 까지는 prevNode, nextNode도 존재했었다는 의미다.

 

그러니까, 만약 1, 2, 3, 4, ...... 23, 24 노드가 있는데, 4번부터 23 노드를 전부 삭제했음. 그러면

1,2,3,24 노드가 남아있는 거고, 이 때

value	prev	next
1	null	2
2	1	3
3	2	24
24	3	null

여기서 3번 노드를 삭제하면 1,2, 24노드는 아직 남아있는 중.

value	prev	next
1	null	2
2	1	24
24	2	null

삭제한 노드 3번은 다음과 같다

value	prev	next
3	2	24

근데 여기서 만약 2를 삭제하면 1,24 노드가 남아있는데

value	prev	next
1	null	24
24	1	null

삭제한 노드들을 보면 다음과 같다.

value	prev	next
3	2	24
2	1	24

 

여기서 2를 보면 1과 24가 prev next인데, 아직 삭제되지 않은 노드들로 구성된다.

그리고 여기서 중요한건, C로 삭제되는 노드들은 stack 형태로 차곡차곡 쌓이게 된다. 그러니까 일단 스택에 먼저 들어온 노드들은 그 이전에 삭제된 노드들을 prev와 next로 갖지 않는다. 아래 표를 보면, 2는 3보다 나중에 삭제되는 것을 확인할 수 있다.

value	prev	next
3 (먼저 스택에 쌓임)	2	24
2 (3보다 나중에 스택에 쌓임)	1	24

그리고 삭제된 노드 스택에서 pop을 해야지만 이전 노드들을 또 되돌리기 할 수 있기 때문에 

복귀를 하면 prev를 갖고있게 된다.

 

그러면 실제로 prev와 진짜 앞 노드가 같은 건가??

이때 current와 헷갈리면 안되는데

C를 해야 Z를 할 수 있는거라서 직전에 삭제한건 Z를 하면 직전의 것이 그냥 복귀되는 것임.

 

처음에는 while로 prev를 찾아나섰는데(물론 그렇게 하면 시간초과가 날거라 생각했지만)

바보같이 확신하지 못했다.

이 문제는 삭제를 어떻게 정의 할 지 생각해보고, undo를 헷갈리지 않았으면 풀 수 있었던 문제다.

그리고 또 시간초과 문제는 초반 초기화 할 때.. if 조건을 줄이기