1. 첨에 나오는 겹치는 문자 골라내기~
https://leetcode.com/problems/longest-common-prefix/description/
Longest Common Prefix - LeetCode
Can you solve this real interview question? Longest Common Prefix - Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: strs = ["flower","flow"
leetcode.com
문제 내용은 이해하겠는데 뭔가 포문으로 여러번 돌려서 풀어야 할것같음
계속 코드 짜는데 의미 없는 시간이 계속 흘러 결국 다른사람의 솔루션을 봤다
indexOf() 와 lastIndexOf() 함수를 알아야 풀수 있는 문제 인것 같다
indexOf()는 비교문자와 같은 문자중에 젤 첨에 나오는것을 찾아오는것이고 last는 맨마지막에 오는것 찾는 함수
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
let firstStr = strs[0]
for (let i = 0; i < strs.length; i++){
while(strs[i].indexOf(firstStr)){
firstStr = firstStr.substring(0, firstStr.length-1);
if(firstStr === ''){
return '';
}
}
}
return firstStr;
};내 나름대로의 컨닝과 다른사람 해설을보고 풀어봄
스트링 배열의 첫번째를 firstStr으로 놓고
포문을 돌려서 배열 전체를 돌린다
포문안에 와일을 써서 firstStr과 배열중에 속해있는것이 있을때까지 돌림
1.첫번째는 동일한 단어이니 전체 동일할것이고
2.첫번째와 두번째 단어가 동일하지 않으면 substring함수를 이용하여 첫번째 단어의 맨끝자리 한글자를 썰어낸다
3.다시 와일문으로 돌려서 확인 ⇒ 완전히 동일할때까지 썰어냄 와일문에서 트루나와서 두단어가 동일해지면 포문으로 다시들어가서 그다음것과 비교
- 같은글자만 정리되면 리턴한다.
처음에 문제가 영어로 되어있어 내가 착각하여 오바한것같다 prefix 라고 접두사같이 앞자리 중복만 찾아내라는 문제였는데 중간이나 맨마지막에 겹치면 어떡하지 라며 진도를 못빼고 있었다.
모자란게 한두개가 아닌듯 ㅎ
정리하면서 보니 1번 로직을 하나 더줄일수 있게 포문을 1부터 돌리면 의미없는 포문 한번을 안돌아도 될것같다
2. 괄호 구분해서 잘닫았는지 보는문제 (스택써야 하는 문제였음)
뭔가 문제 보자마자 기분이 좋다 뭔가 내 힘으로 아는것만이용하여 풀수 있을것 만 같은 기분~
https://leetcode.com/problems/valid-parentheses/description/
Valid Parentheses - LeetCode
Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the sam
leetcode.com
은 개똥이 였다 이렇게 쉽게 풀릴순 없지 테스트 케이스에선 통과했지만 섭밋에는 롱엔서 ㅋㅋㅋㅋ
코드짜면서 어? 이러면 저거 안되는데 했지만 걍 짯다 ㅋㅋ
나는 부끄러움을 모르는인간이라 첨에짠 코드 방출
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var so = 0
var sc = 0
var mo = 0
var mc = 0
var lo = 0
var lc = 0
for(var i = 0; i < s.length; i++){
if(s[i] == '('){
so += 1
}
if(s[i] == ')'){
sc += 1
}
if(s[i] == '{'){
mo += 1
}
if(s[i] == '}'){
mc += 1
}
if(s[i] == '['){
lo += 1
}
if(s[i] == ']'){
lc += 1
}
}
if(so == sc && mo == mc && lo == lc){
return true;
}else{
return false;
}
};너희들은 커서 나같은 코드 짜지 마라 .... 후...
그럼 그렇지 개 허접해 보인다ㅋㅋㅋ
여기에서 문제는 "({)}"이런 케이스 못 골라 낸다는것
lc += 1
}
}
if(so == sc && mo == mc && lo == lc && s.indexOf(`()`) && s == `()`){
return true;
}else{
return false;
}
};발악하는 나의 모습
해결되지 않는 문제
}
if(so == sc && mo == mc && lo == lc && s.indexOf(`()`) !== -1 && s.indexOf(`{}`) !== -1 && s.indexOf(`[]`) !== -1){
return true;
}else{
return false;
}
};개 지랄 하는 코드 까지 가서도 안되니 다시 풀어야 할것같은 느낌이 왔다.
구글링하니 스텍이라는 자료구조를 통해 풀어야 하는 문제였다.
스텍은 후입선출 구조를 가진 자료구조란다 가장 최근에 추가된 항목이 가장 먼저 제거 되는 특징이라고함
화장실에 수건마냥 정리해서 하나씩 쌓아놓으면 마지막에 쌓는것 부터 쓰는것 처럼 ..
특히 괄호 검사같은문제에서 유용하게 사용되고 많은 알고리즘에서 쓴다고 이해하는것이 유용하다는 갓지피티의 말씀
여기에서의 스텍을 이용해 푸는 방법은
포문으로 하나씩 검사하다가 열린 괄호가있으면 스텍에 추가하고 닫친 괄호가 나타나면 열린괄호가 쌓여있는 스텍에서 같은 괄호인지 확인한후 제거 하는 방식
이렇게 생각하니 쉽네 ㅎㅎ.... 풀어보자
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var stack = [];
for(var i = 0; i < s.length; i++){
var currentChar = s[i];
if(currentChar == '(' || currentChar == '{' || currentChar == '['){
stack.push(currentChar);
} else {
if(stack.length == 0){
return false;
}
var topElement = stack.pop();
if(
(currentChar === ')' && topElement !== '(') ||
(currentChar === '}' && topElement !== '{') ||
(currentChar === ']' && topElement !== '[')
){
return false
}
}
}
if(stack.length == 0){
return true;
}else{
return false;
}
};
맨 마지막 if문 처리 는
return stack.length === 0;
이코드를 쓰면 더짧게 쓸수 있겠다.
더욱 더 멋지게 풀려면 괄호열림과 닫힘을 맵핑하여 풀면 더 깐지
var isValid = function(s) {
// 스택을 초기화합니다.
var stack = [];
// 괄호의 대응 관계를 정의한 매핑입니다.
var mapping = { ')': '(', '}': '{', ']': '[' };
// 문자열을 순회하면서 각 문자를 확인합니다.
for (var i = 0; i < s.length; i++) {
var currentChar = s[i];
// 닫힌 괄호인 경우
if (mapping[currentChar]) {
// 스택에서 가장 최근에 열린 괄호를 꺼냅니다.
var topElement = stack.length === 0 ? '#' : stack.pop();
// 현재 닫힌 괄호와 가장 최근에 열린 괄호의 대응 관계를 확인합니다.
if (topElement !== mapping[currentChar]) {
return false; // 괄호의 짝이 맞지 않으면 false를 반환합니다.
}
} else {
// 열린 괄호인 경우 스택에 추가합니다.
stack.push(currentChar);
}
}
// 모든 문자를 확인한 후에도 스택에 남아있는 괄호가 없어야 올바른 괄호 쌍입니다.
return stack.length === 0;
};지린다 배움엔 끝이없다.
3. 두개 숫자배열 머지하기~
이것도 내가 풀수있을것같다~ ㅎㅎ
https://leetcode.com/problems/merge-two-sorted-lists/
Merge Two Sorted Lists - LeetCode
Can you solve this real interview question? Merge Two Sorted Lists - You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists
leetcode.com
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
var outPutList = new ListNode(0);// 빈 연결 리스트 만들고
var endPointer = outPutList; //비교해서 끝에 넣어줘야하니까 끝을 보고있는 포인터생성
while(list1 !== null && list2 !== null){
if(list1.val <= list2.val){
endPointer.next = list1.val; //엔드포인트가 가리키는 마지막에다가 list1을 넣어줌
list1 = list1.next; //리스트 1의 노드가 빈연결리스트에 들어갔으므로 list1의 넥스트를 list1으로 바꿔줌 == 방금 넣은 노드 뺀거임
} else {
endPointer.next = list2.val;
list2 = list2.next;
}
endPointer = endPointer.next;
}
if(list1 !== null){
endPointer.next = list1;
} else if (list2 !== null){
endPointer.next = list2;
}
return outPutList;
};이렇게 풀었는데 여기서 더이상은 진행 안됨 계속 에러뜸
챗지피티 지적!
문제는 endPointer.next = list1.val; 및 endPointer.next = list2.val; 부분입니다. 이 부분에서 .val을 사용하면 노드의 값만 할당되고, 다음 노드에 대한 참조가 손실됩니다. 그래서 이 부분을 endPointer.next = list1; 및 endPointer.next = list2;로 바꾸어야 합니다.
+
outPutList 는 병합된 연결 리스트를 가리키는 더미 노드입니다. 처음에 이 더미 노드를 생성할 때, 노드의 값으로 0을 할당하였습니다. 따라서 outPutList를 그대로 반환하면, 병합된 연결 리스트의 시작이 더미 노드가 되어, 실제 값이 아닌 0이 리스트의 첫 번째 원소가 되고, 이는 우리가 원하는 결과가 아닙니다.
따라서 outPutList.next를 반환하여, 우리가 원하는 실제 리스트를 반환하게 됩니다. 이렇게 하면 병합된 연결 리스트의 첫 번째 원소가 실제 값이 되어, 우리가 원하는 결과를 얻을 수 있습니다.
???:
아 첨에 아웃풋리스트에 첫머리가 0을 가르치고 있으면 안되니까 넥스트로 한단계 넘겨주고 리턴하는거구나?
갓지피티:
네, 맞습니다! 처음에 생성한 `outPutList` 노드는 더미 노드(또는 센티넬 노드라고도 부릅니다)로, 실제 연결 리스트의 값들과는 상관없이 연결 리스트를 관리하기 위해 사용됩니다. 이 더미 노드는 연결 리스트의 헤드를 가리키는 역할을 하며, 이를 통해 연결 리스트의 첫 번째 요소에 쉽게 접근할 수 있습니다. 그러나 이 더미 노드는 실제 연결 리스트의 일부가 아니므로, 병합된 연결 리스트를 반환할 때는 더미 노드를 제외하고 반환해야 합니다. 그래서 `outPutList.next`를 반환하여, 더미 노드를 제외한 실제 병합된 연결 리스트를 반환하는 것입니다. 이해가 되셨나요? 추가적인 질문이 있으시다면 언제든지 말씀해 주세요!
사랑합니다.. 갓지피티...
열심히 배우겠습니다 센세....
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
var outPutList = new ListNode(0);// 빈 연결 리스트 만들고
var endPointer = outPutList; //비교해서 끝에 넣어줘야하니까 끝을 보고있는 포인터생성
while(list1 !== null && list2 !== null){
if(list1.val <= list2.val){
endPointer.next = list1; //엔드포인트가 가리키는 마지막에다가 list1을 넣어줌
list1 = list1.next; //리스트 1의 노드가 빈연결리스트에 들어갔으므로 list1의 넥스트를 list1으로 바꿔줌 == 방금 넣은 노드 뺀거임
} else {
endPointer.next = list2;
list2 = list2.next;
}
endPointer = endPointer.next;
}
if(list1 !== null){
endPointer.next = list1;
} else if (list2 !== null){
endPointer.next = list2;
}
return outPutList.next;
};
어렵다 ㅎㅎ....
하지만 계속하는 사람은 이길수없는것이 인생의 진리 이고 길이의 법칙이지
가즈아...!! let's gooooo~
