FrontEnd
[JS] 뒤에 있는 큰 수 찾기
처음에는 무식하게 반복문을 두번 사용해서 찾는 방식으로 구현했었는데, 배열의 크기가 100만개이다보니 예상대로 시간초과가 발생하였다. 메모제이션이나 스택을 활용하면 좋을 것 같아서 생각을 하다가 스택을 활용해서 구현하였다. 1. 스택에 맨 끝값을 집어넣고 해당 값을 -1로 만들어 준다. 2. 배열을 뒤에서부터 구해준다. 스택에서 비교할 값을 pop으로 빼주고, 만약 스택에서 뺀 값이 비교할 값보다 작으면 큰 수가 나오거나 스택이 비어질때까지 계속 값을 빼준다. 3. n-1 번째와 n번째를 비교할때, n이 n-1번째보다 크다면 무조건 뒷 큰수는 n이된다. 따라서 해당 경우 n을 n-1의 뒷 큰수로 만들어주고, 스택에 다시 두개의 값을 집어 넣는다. 4. 스택이 비어있는경우 -1으로 생각하고 원래 있던 값을..
[JS] 무인도 여행
BFS를 활용해서 문제를 풀어보았다. 배열을 순회하면서 숫자가 적힌 지점부터 BFS를 적용하여 수들을 더해 나갔다. 이때, 방문했던 곳이라면 다시 방문할 필요가 없기 때문에 방문했는지 여부를 저장할 배열을 하나 두었다. 2차원 배열을 한번 순회한 이후, 정렬을 해주었고 섬이 없다면 [-1]을 반환하게 설정해주며 마무리하였다. function solution(maps) { const dx = [1,0,-1,0] const dy = [0,1,0,-1] const dp = [...new Array(maps.length)].map((_,i) => [...new Array(maps[0].length)].fill(0)) ret = [] for (let i = 0 ; i< maps.length ; i++) { for..
[JS] 호텔 대실
현재 쓰고있는 방의 개수를 넣을 배열을 하나 넣은 후, 손님이 들어올때마다 종료시간이 된 손님들을 내보내는 방식으로 코드를 구현하였다. 손님이 나간 이후 10분동안 청소를 해야하므로, 종료시간을 그냥 10분 더 연장하여 생각하였다. 시간,분으로 나누어져 있는 값들을 모두 분으로 바꾸어서 계산하기 쉽게 바꾸어주었다. const hTom = (str) => { const [h,m] = str.split(":") return +h * 60 + +m } function solution(book_time) { const time = book_time.map(el => [hTom(el[0]) , hTom(el[1])+10]) time.sort((a,b) => a[0]-b[0]) let ret = 0; let roo..
[JS] 미로탈출
BFS 와 que를 활용해서 풀었다. (지금 봤는데 중간에 변수 이름을 stk으로 썼는데 생각해보니 DFS가 아닌 BFS로 풀어야 하는 문제여서.. stk가 큐라고 생각하고 보면 좋을 것 같다.) 1. 시작 좌표 정하기 2. 방문했는지 정할 dp배열 정하기 => 이때 레버있을때는 방문했던 곳을 또 지나갈 수 있으므로 레버가 없이 방문했으면 1, 없이 방문했으면 2를 넣어준다. 3. 큐에 첫 값으로 [시작 x좌표, 시작 y좌표, laver 유무 , 카운트] 를 넣어준다. 4. 큐를 순회하면서 갈 수 있는곳이라면 큐에 위에 정해준 서식대로 값을 넣어준다. => 레버를 당겼으면서 골인지점인 경우에는 cnt+1 을 출력 => 레버가 당겼으면서 2번이상 방문한 곳은 큐에 더이상 넣지 않음 => 레버가 당겨지지않은..
[JS] 혼자서 하는 틱택토
틱택토는 사실 3*3의 작은 배열이기 때문에 직접 개수를 한번 세 보는식으로 판별했다. 사실 아래 조건을 충족하지 않으면 모두 일치하지 않는 틱택토이다. 1. O,X 개수의 차이가0,1 이상인 경우 2. x,o 둘다 점수가 난 경우 3. x가 점수났을때 o의 개수와 x의 개수가 다른 경우 4. o가 점수났을때 o의 개수와 x+1의 개수가 다른경우 해당 케이스를 제외하면 점수가 날 수 없다. function solution(board) { //O,X 개수세기 let oCnt=0; let xCnt=0; for (let i=0 ; i
[JS] 리코쳇 로봇
que와 bfs를 활용해서 풀어보았다. que를 활용하긴 했는데 JS에서는 큐 자료구조를 라이브러리로 제공하지는 않아 직접구현해야 하는데 배열 범위가 크지 않아 그냥 배열을 활용해서 풀었다. 풀이 방법을 순서에 따라 설명해보겠다. 1. 동서남북 방향으로 움직이는것을 구현할 수 있게 도와주는 dx,dy값 생성 2. 배열을 2차원 배열로 만들어줌 (지금 생각하면 원본배열을 수정하는것이 아니라, 굳이 상관 없었을 듯 하다) 3. 로봇의 시작 좌표 찾기 4. 찾을 수 없는경우 그만 찾아야 하므로, 방문한 좌표를 저장할 dp배열을 하나 생성 5. 큐에 로봇의 좌표와 몇번 움직였는지 저장할 cnt값을 넣어서 이를 빼면서 확인 [x,y,cnt] 0