감공사

Code

😢 보자마자 위에서 표시해 놓은 부분들이 눈에 띄었다.
각 범위를 한 바퀴 돌고 다음 범위로 넘어가는 부분인데, 각 수를 계산해보니 6, 12, 18, 24로 등차수열을 이루고 있었다.
그래서 등차수열을 이용해서 푸는 문제인가? 하고 계산식을 넣으려고 하다가 시간을 좀 낭비했다.

😊 패턴을 찾았다면 프로그래밍적으로 단순하게 작성해 나가면 된다.
최소 거리는 1부터 시작할 것이고, 범위도 1부터 시작한다. 
증가하는 범위는 1,(2~)7, (8~)19, (20~)37...이므로 '기존 범위+(count된)최소 거리*6' 이다.
while loop을 이용해 범위가 입력 받은 N보다 작을 때까지 반복해주면 된다.

Full Code (https://github.com/DasolPark/Algorithm_JavaScript/tree/master/Baekjoon)

Q. 입력 받은 Tree의 root를 이용해 Tree 각 층의 Node 너비(=개수)를 알아내는 function 작성하라.

--- Example
Given:
0
  / |  \ 
1   2   3
|       |
4       5

Answer: [1, 3, 2]

🎈 Tree traverseBF(BFS) method와 비슷하다.
배열을 선언해 초기 값으로 root와 각 층의 끝을 알려주는 문자('s')를 넣어주고, 이런 형식으로 반복 해주면 된다.
또한, 이 과정에서 각 층의 Node를 count해줘야 한다.

🧨 위의 이미지를 보며 어떻게 풀어나갈 지 생각해보자

1. []의 초기값 선언
2. while 조건문은 어떻게?
3. while 내부에서 's'처리는 어떻게?
4. count 방식은 어떻게?

위 4가지만 잘 생각해주면 문제는 생각보다 쉽게 해결된다.

🔮 arr 배열에 [ root, 's' ]를 넣어주고 시작해야 한다. while 조건문으로 arr.length > 1을 줄 것이기 때문이다.
위와 같이 조건문을 작성하면, 마지막 's'가 남았을 때 while을 끝낼 수 있다.
여기서 counters 배열에 0을 넣고 시작하는 것도 중요한 팁이다.
보통 counter를 한다고 생각하면, count변수를 따로 만들어 count++를하고 반환할 결과 배열에 push(count)할 것이다.
하지만, 방금 작성한 방법을 사용하면 위의 while에서는 마지막 count를 결과 배열에 push하지 못한다.

전 글의 Tree traverseBF(orDF) method에서 했던 것처럼, arr.shift()을 해서 가장 첫 번째 index 값을 가져온다.
만약 's'면, 해당 width count는 끝났으며, 다음 level의 children이 모두 arr에 push된 것이므로,
새로운 counters를 push해줌과 동시에 해당 width의 끝을 알리는 's'도 push해준다.
's'가 아니라면, 위와 반대로 해당 level을 count하고 있으며, 다음 level의 children을 push하고 있는 것이므로
arr.push와 counters++를 진행해준다.

Full Code

Code

😢 이런저런 조건들을 떠올리다보니 산으로 갔던 문제
역시 조건 그대로 코드를 작성하기 보다는, 다른 시각으로 바라보는 조건이 핵심

😊 가장 최고의 조건을 걸어두고 하나씩 물러나며 최선의 조건을 찾아야한다.

최종 제출 답안)

bigMax 변수에 가장 큰 봉지인 BIG(5)으로 설탕 무게를 나눴을 때, 나오는 숫자를 저장한다.
그리고 bigMax가 음수로 떨어지지 않을 때까지 while loop을 열어준다.

임시로 만든 tempSugar 변수에는 앞에서 계산한 bigMax 무게만큼 SUGAR를 빼준다.
만약 tempSugar가 작은 봉지인 SMALL(3)으로 나눴을 때 나머지가 없다면 최선의 조건이기 때문에 출력하고 계산을 끝내준다.
하지만, 만약 조건에 맞지 않는다면 bigMax를 1만큼 빼준다.
그런 후 tempSugar의 크기를 5만큼 높여주고 다시 3으로 나눠본다.

이런식으로 계속 반복하며 다시 5씩 늘려보고 다시 3으로 나눠봤을 때 나머지가 0이라면 계산이 가능한 설탕 무게이고,
그렇지 않고 bigMax가 음수로 떨어진다면 그건 계산할 수 없는 설탕 무게이므로 -1을 출력한다.

다른 정답자들 중에 배울 수 있었던 답안)

😊 먼저, SMALL(3)의 개수를 담아두기 위한 bags 변수를 선언해준다. while loop을 무한으로 돌리면서,
설탕을 BIG(5)으로 나눴을 때 나머지가 0이라면 BIG으로 나눈 값과 bags를 합쳐 출력한다.
그리고 만약 SUGAR가 0이하로 떨어지면 -1을 출력해준다.
둘 다 해당되지 않으면 설탕을 SMALL(3)만큼 빼주고, bags를 1 증가시켜준다. (설탕을 3으로 나눈 것과 같은 의미)

즉, 이것도 역시 최고의 방법인 5를 우선으로 나눠주고, 그게 되지 않는다면 3을 하나씩 늘려가는 방법으로 해결했다.
이것도 굉장히 훌륭한 방법이라고 생각한다.

Full Code (https://github.com/DasolPark/Algorithm_JavaScript/tree/master/Baekjoon)

Code

😢 21억 조건을 못 보고 반복문을 돌려 counter를 하나씩 증가시키려고 했다.. 잘못된 방법!

😊 역시나 수학 카테고리답게 다항식을 이용해서 풀면 쉽게 풀 수 있다.
A는 고정 비용, B는 가변 비용, C는 판매 가격이다.
판매 누적 금액이 고정비용+가변 누적 비용을 넘어서면 손익분기점을 넘어간다.
식을 만들어 본다면, A + Bx < Cx로 만들 수 있다. 
식을 정리해보자. A < Cx - Bx로 Bx를 넘겨주고, A < (C-B)x 로 정리해주면 조금 더 보기 쉽다.
즉, C-B가 0이하(즉, 0 또는 음수)로 떨어지면 손익분기점은 없다. 계속 적자다..ㅎㅎ

손익분기점이 없어서 '-1'을 출력하는 조건문은 2가지 정도로 표현할 수 있다.
1. if(C-B <= 0) { console.log(-1); }
A < (C-B)x 식을 생각해서 C-B가 0이하면 손익분기점은 없다고 표현할 수 있다.
2. if(C <= B) { console.log(-1); }
C-B > 0이 돼야하므로, C <= B으로 정리해주면 손익분기점이 없다고 표현할 수 있다.

Full Code

Code

😢 간단한 문제지만, 어떻게 하면 효율적으로 풀 수 있을까 고민했던 문제. 결과적으로 그다지 효과적이지 않은..

😊 결국 중첩 for loop을 이용해서 각 word의 문자를 체크하는 방법으로 풀었다.
Object를 하나 만들어주고, 해당 문자가 이미 사용되었다면 charMap에 '문자': true로 넣어주었다.
만약 charMap에 이미 해당 문자가 있다면 해당 word의 index-1과 같은지 비교해주었다.
같다면 그룹단어, 그렇지 않다면 더 이상 검사할 필요가 없기 때문에 counter를 감소시켜주고, break으로 내부 for loop을 끝냈다.

다른 정답자들의 풀이도 좋은 소스가 되었다.

Full Code

Q. Linked Lists의 마지막 Node에서 n번째 앞에 Node를 반환하는 function을 작성하라.

---Examples;
const list = new List();
list.insertLast('a');
list.insertLast('b');
list.insertLast('c');
list.insertLast('d');
fromLast(list, 2).data; // 'b'

🎈첫 번째에서부터 다음 n번째 Node와, 마지막에서부터 앞으로 n번째 Node의 간격은 같다. 생각의 전환!
을 생각하면 조금 더 쉽게 풀어나갈 수 있다.

🧨 역시나 앞서 풀었던 2문제들과 비슷하다. 하지만, 생각을 조금 다르게 해야한다.
뒤에서부터 3번 앞으로 이동하면 red Node이며, 마지막 Node는 grey이고, 간격은 3이다.
앞에서부터 3번 뒤로 이동하면 orange Node이며, 첫 번째 Node는 green이고, 간격은 3이다.

만약, slow와 fast가 시작점(green)에서 시작할 때, fast를 먼저 3번 앞으로 이동해보자.
그럼 fast는 orange를 만난다. slow는 시작점인 green을 가리키고 있다.
이제 fast가 끝(grey)에 도달할 때까지, slow와 fast를 1칸씩 이동해보자.
slow는 최종적으로 red를 가리키게 된다.

즉, 앞에서 이동하나 뒤에서 이동하나 그 간격은 같다. Node를 각각 반대로 생각하면 된다.
결과적으로, fast는 마지막 node를, slow는 뒤에서부터 n번째 떨어진 node를 의미하게 된다.

이렇게 뒤에서 앞에 n번째 값을 구할 수 있다.

🔮 while loop을 이용해 fast를 n만큼 이동시켜주고, 또 다시 while loop을 이용해 slow와 fast를 이동시켜준다.
결과적으로 slow는 뒤에서 n번째 Node를 가리키게 된다.

Full Code

Q. Linked Lists가 circular인지 확인하라(마지막 Node가 없고, 계속 순환하는 Linked List).
(맞다면 true, 아니라면 false를 반환)

--- Examples
const l = new List();
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
l.head = a;
a.next = b;
b.next = c;
c.next = b;
circular(l) // true

🎈 토끼와 거북이가 운동장 돌기 경주를 하는데, 경주의 끝이 없다면, 언젠가는 둘이 만날(겹칠) 것이다.
라고 상상하면 조금 더 쉽게 풀어나갈 수 있다.

🧨 앞서 풀었던 Find the Midpoint 문제를 응용하면 된다.
slow와 fast의 시작점은 같고, slow는 1칸, fast는 2칸씩 이동한다.
계속 이동하다보면 slow === fast가 되는 경우가 발생할 것이고, 이걸 조건문으로 넣어 true를 return하면 된다.
만약, circular가 아니라면 while loop조건 fast.next.next를 만족하지 않으므로 while loop이 끝난 후 false를 return하면 된다.

🔮 while loop안에서 slow === fast 조건을 넣어주고, true가 반환된다면 이 Linked List는 Circular(순환)이며,
while loop의 조건인 fast.next.next를 만족시키지 못한다면 끝이 있는 Linked List이므로 Circular가 아니다.

Full Code

Q. Linked Lists의 중간 Node를 찾는 function을 구현하라.
(매개변수로 list를 받으며, Lists의 크기가 짝수라면, Lists 반의 앞 부분에서 마지막 Node를 반환하고,
counter변수나 size() method를 사용하지 않고 풀어야 한다)

🎈 토끼와 거북이의 경주를 생각해보자.
토끼가 거북이의 2배 속도로 달린다고 생각할 때, 토끼가 도착하면 거북이는 중간을 달리고 있을 것이다.

토끼 변수1, 거북이 변수1, 달리기 반복 loop을 이용해서 문제를 해결해보자.

🧨 slow와 fast변수는 같은 시작점에서 출발한다. 그리고 slow는 1칸씩, fast는 2칸씩 이동한다.
Lists 크기가 홀수일 경우를 먼저 생각해보자.
fast가 2칸씩 이동했을 경우, 항상 마지막 Node에 도착할 수 있고, 그때 slow의 위치는 중간이다.
하지만, Lists의 크기가 짝수일 경우에는 fast가 마지막 Node에 도착할 수 없다.
따라서, fast의 다음 칸은 있지만, 다음 다음 칸을 확인했을 때 Node가 없다면, 
그때 slow의 위치는 중간(즉, Lists 전체 크기에서 반을 잘랐을 때 앞부분 반의 마지막 Node)이다.

위의 내용을 아래 코드로 옮겨 보았다.

🔮 slow나 fast를 초기화할 때, list.head;를 사용해도 동일하며, while의 조건은 반드시 &&(and)로 넣어줘야 한다.

Full Code

Code

😢 단순 조건문 처리로는 풀기 싫어서, 어렵게 풀려다가 생각하는 시간이 조금 걸렸다.
그리고 문제를 보자마자 Regular Expression이 떠올라서, RegExp로 풀려고 공부를 조금 했다.

😊 조건문으로만 풀기에는 뭔가 문제가 아까웠다. 그래서 이런 방법 저런 방법을 시도해봤다. (물론 단순 조건으로도 풀어봤다)

regex변수에 크로아티아 알파벳 조건들을 입력해주고 replace() 에 주입하여, 만약 일치하는 것이 있다면 공백(' ')으로 만들어줬다.
RegExp 구성을 살펴보겠다. 아주 간단하다.
=, -와 같은 문자들은 특수문자이기 때문에 특별하다는 뜻으로 \(backslash, escape라고도 부른다)를 앞에 붙여줘야 하고,
그 외 조건들은 |(or)문자를 사용해서 구분해주었고, g를 붙여 Global search를 해줬다.

결과적으로 2개 이상 문자를 갖는 크로아티아 알파벳은 공백으로 변경되어 1개의 문자를 갖게 된다.
따라서 결과의 length를 출력해주면 크로아티아 알파벳의 개수를 알 수 있다.
(조건 외의 알파벳은 1개로 치니까 따로 처리하지 않는다)

Full Code에 단순 조건문 처리로 푼 예제도 있으니 참고하길 바란다.

✔ String.prototype.replce()

크로아티아 알파벳만의 조건을 넣어서, 공백(' ')으로 변경해주기 위해 사용했다.

✔ Regular Expressions

문자열을 다루기 위한 정규표현식이다. 크로아티아 알파벳 조건을 표현하기 위해 사용하였다.

위의 Skill들은 JavaScript - helper methods 카테고리에서 간단한 사용방법을 확인할 수 있다.

Full Code

Code

😢 알파벳을 직접 손으로 입력하고 싶지 않았고, Object로 value(각 지연 시간)까지 넣어서 진행하고 싶었다.
큰 어려움은 없었고, 중심을 Object로 만들고 푸는 과정에서 어떻게 진행할지 조금 고민했다.

😊 'A'부터 'Z'까지 진행하는 for loop을 열고, 'PQRS', 'WXYZ'는 예외로 들어가도록 조건문을 걸어주었다.
( i !== 'R'charCodeAt(0) && i !== 'Y'.charCodeAt(0) )으로 조건을 넣어준 이유는,
'PQRS', 'WXYZ' 이 2가지만 제외하면 모두 길이가 3이다. 그래서 길이 3으로 저장되기 전인 R or Y에서 저장을 차단하고,
앞의 두 문자가 각각 합쳐져 길이가 4가 되었을 때 key로 저장되도록 했다.

Object를 만들어준 후에, 입력 받고 split('')한 값에 reduce달았고, 안에 Object를 반복하는 for ... in loop을 열어주었다.
그렇게 입력받은 값 중에 각 key에 해당하는 문자가 있다면, acc에 해당 key의 value를 중복 저장해주고 return 해주었다.
결과적으로 result값에 전화를 걸기 위해 필요한 시간이 저장된다.

다른 풀이도 확인해보았지만, 대부분 직접 알파벳을 입력해서 사용하였고, 특별히 다른 점을 찾지 못 했다.

✔ Object {}

{ 'ABC' : 3, 'DEF': 4 ... } 이런 식으로 전체 알파벳을 저장하기 위해 작성하였다.

✔ charCodeAt()

해당 알파벳의 ASCII Code(숫자)를 알아내서 for loop을 이용하기 위해 사용하였다.

✔ String.fromCharCode()

()안에 ASCII코드를 넣어서 문자를 가져오기 위해 사용하였다.

✔ reduce

전화를 걸기 위해 필요한 시간을 중복 저장하기 위해 사용하였다.

✔ for ... in

Object의 key을 가져오는 for loop을 이용하기 위해 사용하였다.

위의 Skill들은 JavaScript - Helper methods or Grammar 카테고리에서 간단한 사용방법을 확인할 수 있다.

Full Code