문제 목록
function solution(s) {
let word = [];
// 스택으로 넣어서 마지막과 마지막+1가 같으면 빼주기
// 결과적으로 담아뒀던 word에 아무것도 없으면, 짝지어 제거하기가 성공된 것이므로 1리턴
for (let i = 0; i < s.length; i++) {
word.push(s[i]);
if (word.length >= 2 && word.at(-1) === word.at(-2)) {
word.pop();
word.pop();
}
}
return !word.length ? 1 : 0;
}
solution('baabaa');
스택을 이용해서 풀었다! 스택하면 예전에 했었던 햄버거 만들기밖에 생각이 안나..
function solution(s){
var stack = [];
for(let i = 0; i<s.length; i++){
if(stack[stack.length-1] != s[i]){
stack.push(s[i]);
}
else{
stack.pop();
}
}
if(stack.length>0) return 0;
else return 1;
}
동원님 코드! 다른 부분들은 거의 유사하지만 나는 애초에 넣어주고 했었는데 동원님은 지금 넣을 값하고 마지막 같이 같은지 확인해 주었다 이렇게 해 준게 훨씬 간결하고 좋아 보여서 가져왔다!
function solution(n, words) {
//? 앞에 말한 단어의 마지막 문자로 시작하는 단어 말하기
//! 가장 먼저 탈락하는 사람 번호, 몇 번째 차례인지
// 지금까지 말한 단어는 connectGame push 시켜 줘서 현재 단어가 connectGame에 있다면 탈락
//
let connectGame = [words[0]];
let turn = 0;
for (let i = 0; i < words.length; i++) {
//? 첫번째는 바로 통과
if (i === 0) continue;
const before = words[i - 1];
const now = words[i];
//? 전에 말한 단어 사용하면 탈락
if (connectGame.includes(now)) {
break;
}
//! 현재 단어의 첫글자가 전 글자의 마지막 글자와 같은지 비교
if (now.at(0) === before.at(-1)) {
turn++;
connectGame.push(words[i - 1]);
connectGame.push(words[i]);
}
}
//? [탈락 번호, 몇 번째 차례]
//? 게임 turn이 words의 길이만큼 돌아갔다면 탈락자가 없는 것이므로 [0, 0]
if (turn + 1 === words.length) return [0, 0];
return (turn + 2) % n === 0
? [n, Math.ceil(turn / n)]
: [(turn + 2) % n, Math.ceil(turn / n)];
}
실패했던 코드 시간초과도 아니고 그냥 실패이다... 사유는 모르겠다 일단 성공코드 먼저 보자!
function solution(n, words) {
//? 앞에 말한 단어의 마지막 문자로 시작하는 단어 말하기
//! 가장 먼저 탈락하는 사람 번호, 몇 번째 차례인지
// 지금까지 말한 단어는 connectGame push 시켜 줘서 현재 단어가 connectGame에 있다면 탈락
//
let connectGame = [words[0]];
console.log(connectGame);
//? 첫번째는 바로 통과
for (let i = 1; i < words.length; i++) {
const before = words[i - 1];
const current = words[i];
//! 현재 단어의 첫글자가 전 글자의 마지막 글자와 같은지 비교
if (
current.at(0) === before.at(-1) &&
connectGame.indexOf(current) === -1
) {
connectGame.push(current);
} else {
//? [탈락 번호, 몇 번째 차례]
return [(i % n) + 1, parseInt(i / n) + 1];
}
}
//? 탈락자가 없으면 [0, 0]
return [0, 0];
}
실패코드랑 다른 점이 있다면 가장 큰 건 이미 말했던 단어라면 탈락시키는 부분이 다르다. 성공 코드에서는 indexOf를 통해서 해당 요소가 있는지 확인하였고, 실패 코드에서는 includes로 했다는 점이다... 아니면 내가 리턴 시키는 곳에서 잘못해 주었을까?,,, 나중에 처음부터 뜯어보고 다시 풀어야겠다.
/**
1. 이전에 나온 단어가 다시 나오는지
2. 직전에 나온 단어의 마지막 문자(character)가 이번에 보고 있는 단어의 첫번째 문자와 동일한지
*/
function solution(n, words) {
let answer = [0,0];
let last = words[0][words[0].length-1];
let hs = new Set();
hs.add(words[0]);
console.log(hs)
for (let i = 1; i < words.length; i++) {
if (words[i][0] != last || hs.has(words[i])) { // hs배열에 word[i]를 갖고 있는지
answer[0] = i%n+1;
answer[1] = parseInt(i/n)+1;
console.log(answer[0])
console.log(answer[1])
break;
}
last = words[i][words[i].length-1];//마지막 글자 가져오기
hs.add(words[i]); //hs배열에 단어 추가하기
}
return answer;
}
solution(3,["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]);
동원님 코드! set에서 추가하고 has로 해당 인덱스가 있는지 확인하는 메서드를 알게 되었다! Set은 항상 중복 없애는 용도로만 사용했었는데 새로운 코드,, 굿굿
function solution(people, limit) {
// 가벼운 사람, 무거운 사람 정렬 후
// 제일 무거운 사람 + 제일 가벼운 사람 넣어지면 shift! 해주기
let light = [...people].sort((a, b) => a - b);
let heavy = [...people].sort((a, b) => b - a);
let boat = 0;
for (let i = 0; i < heavy.length; i++) {
// 무거운 사람, 가벼운 사람 되면 boat++ 해 주고 사람들이 보트를 탔으니 빼준다
// 빼줬으니 다시 처음부터 비교해야 되므로 i--
if (heavy[i] + light[i] <= limit) {
heavy.shift();
heavy.pop();
light.shift();
light.pop();
boat++;
i--;
} else {
heavy.shift();
light.pop();
boat++;
i--;
}
}
return boat;
}
solution([70, 80, 50], 100);
for문 안에서 shift(), pop()을 써줘서 시간초과로 실패한 코드이다. 동원님께서 스터디가 끝나고 공유해 주신 블로그를 통해서 배열 내에서의 메서드들의 시간 복잡도에 대해서 알 수 있었다. shift의 경우에는 앞의 값을 제거하고 나머지 인덱스들이 1만큼 앞으로 와야 되기 때문에 새로운 인덱스가 돼 전체 인덱스가 바뀌므로 시간복잡도가 O(N)이다!
push, pop : O(1)
shift, unshift : O(N)
참고: [시간복잡도](참고: https://parkparkpark.tistory.com/m/101)
function solution(people, limit) {
// 내림차순 정렬 후
// 제일 무거운 사람 + 제일 가벼운 사람 넣어지면 boat++ 해주기
let heavy = [...people].sort((a, b) => b - a);
let boat = 0;
console.log(heavy);
// 투포인터로 풀기
// [80, 70, 50, 50]
//! i j
//? i j i + j가 limit보다 작거나 같을 경우, j-- 해서 포인터 이동
for (let i = 0, j = heavy.length - 1; i <= j; i++) {
if (heavy[i] + heavy[j] <= limit) {
j--;
}
boat++;
}
console.log(boat);
return boat;
}
solution([70, 50, 80, 50], 100);
for문 내에서 선언하는 것을 두 번 하여 투포인터 개념으로 풀었다! 위에 실패코드에서는 직관적이게 풀었지만,,, 시간초과로 아쉽지만 투포인터를 해서 풀어본 건 이번이 처음이라 좋았따 ㅎㅎㅎ!!