본문 바로가기

🧠 알고리즘31

[프로그래머스] 뒤에 있는 큰 수 찾기 JS 첫 번째 풀이는 뒷큰수가 있는 경우만 판별하여 이중 포문으로 처리했습니다 2개 정도 시간초과가 발생했습니다 시간 초과가 발생해서 어떻게 해야 반복을 줄일 수 있을까 고민했습니다 생각을 하다보니 스택을 통해 뒷큰수만 유지하면 되겠다는 판단이 들었습니다. 뒤에서부터 순회를 하면서 바로 뒤에 있는 수와 그 수의 뒷큰수들만 스택으로 관리하는 방식으로 풀었습니다 function solution(numbers) { //뒤에서부터 순회하면서 //스택에는 바로 뒤에 있는 수와 그 수의 뒷큰수들만 관리 const stack = []; const result = []; //뒤에서부터 순회 for (let i = numbers.length - 1; i >= 0; i--) { //스택이 빌 때까지 반복 while (stack.. 2024. 1. 7.

[프로그래머스] 무인도 여행 JS 문제링크 전형적인 BFS문제 모든 원소를 순회하면서 존재하는 모든 무인도를 방문하고 하나의 무인도를 발견할 때마다 bfs를 통해 해당 무인도가 가지고 있는 식량의 수를 더해나가는 방식으로 풀었습니다 방문한 무인도의 원소는 X로 변경하여 방문처리를 해줬습니다 function solution(maps) { //bfs 완전 탐색 const q = []; const result = []; const r_length = maps.length; const c_length = maps[0].length; const dr = [0, 0, -1, 1]; const dc = [1, -1, 0, 0]; //문자열을 배열로 변환 for (let r = 0; r < r_length; r++) { maps[r] = maps[r].. 2024. 1. 6.

[프로그래머스] 호텔 대실 JS 문제링크 개인적으로 프로그래머스에 있는 과제 진행하기 문제랑 비슷하다고 느꼈습니다 스터디원 분의 풀이 방법이 인상깊었는데 그 풀이를 이 문제에 적용해보려고 했어요 1. 예약 시간들은 모두 분단위로 변환, 시작 시간 기준으로 오름차순 정렬을 했습니다. 2. 배열들을 순회하면서 2-1. room_stack(사용 중인 방들의 종료시간이 저장되어 있는 배열)을 내림차순 정렬합니다 2-2. 현재 예약 시작 시간 기준으로 종료된 방이 있으면, 종료된 방을 pop합니다 2-3. 현재 예약의 종료시간을 room_stack에 push합니다 2-4. room_cnt와 room_stack의 length를 비교해서 큰 값을 저장합니다 사실 room_stack을 내림차순 정렬하는 것보다 우선순위큐를 사용하는게 시간복잡도 측면에.. 2024. 1. 5.

[프로그래머스]미로 탈출 JS 문제링크 전형적인 최단거리 찾는 bfs 문제였습니다 최단 거리를 2번 찾아야 해서 함수를 만들어서 활용했습니다 특정 지점까지의 최단거리를 찾는 함수를 만들어서 1. 입구에서 레버까지 방문 가능 여부를 확인하고 2. 레버에서 출구까지 방문 가능 여부를 확인했습니다 function solution(maps) { const r_length = maps.length; const c_length = maps[0].length; const dr=[0,0,-1,1]; const dc = [1,-1, 0,0]; let visited = Array.from(new Array(r_length), ()=> new Array(c_length).fill(false)); let q=[]; let start; let lever; .. 2024. 1. 4.

[프로그래머스] 혼자서 하는 틱택토 JS 문제링크 풀이 방법 나올 수 없는 경우를 구해 0을 리턴해줬습니다 1. X가 O보다 많을 때 2. O가 X보다 2개이상 많을 때 3. 선공이 이미 이겼는데 후공이 이어서 진행한 경우 4. 후공이 이미 이겼는데 선공이 이어서 진행한 경우 이기는 경우를 빙고라고 지칭했습니다 가로, 세로 빙고 여부를 판별하는 함수 대각선 빙고 여부를 판별하는 함수를 만들어서 활용했습니다 function solution(board) { // 나올 수 없는 경우 구하기 //1. X가 O보다 많을 때 //2. O가 X보다 2개이상 많을 때 //3. 선공이 이미 이겼는데 후공이 이어서 진행한 경우 //4. 후공이 이미 이겼는데 선공이 이어서 진행한 경우 let o_cnt = 0; let x_cnt = 0; for (row of bo.. 2024. 1. 3.

[프로그래머스] 당구 연습 JS 문제 링크 풀이 이 문제도 생각보다 오래 걸렸습니다 처음에는 (시작공과 벽면의 거리 + 벽면과 도착공의 거리)의 제곱을 구했는데 각 거리를 구하는 과정에서 실수가 나와서 오차가 생기더라구요 다른 분들의 풀이를 찾아보니 점을 대칭시켜서 구하는거였습니다 도착공의 좌표를 상[0], 하[1], 좌[2], 우[3] 대칭시킴 대칭시킨 도착공의 좌표와 시작공 사이의 거리를 구함 대신 시작공이 벽보다 도착공을 먼저 만나는 상황이면 건너뛴다 예를 들어 도착공을 위쪽으로 대칭시킬건데(시작공을 상단벽에 부딪히게 만들고) && 두 공이 같은 세로선상에 있고 && 시작공이 도착공 아래쪽에 있다면 => 벽에 부딪히기 전에 도착공에 부딪히므로 continue; 이해가 안가시는 분들은 아래 링크 참고해주세요!! https://sil.. 2024. 1. 3.

이전 1 2 3 4 5 6 다음

티스토리툴바