Algorithm/자료구조
-
[프로그래머스] 오픈채팅방Algorithm/자료구조 2021. 10. 1. 12:55
문제 : https://programmers.co.kr/learn/courses/30/lessons/42888?language=javascript 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr - record의 길이는 100,000이기 때문에, O(NlogN)이하의 알고리즘을 구현해야 한다. - hash를 이용하면 쉽게 풀 수 있는 문제이다. (설명이 길어서 살짝 쫄았다..) - 자바스크립트는 Map 생성자를 통해 hash를 구현할 수 있다. function solution(record) { var answ..
-
[프로그래머스] 짝지어 제거하기Algorithm/자료구조 2021. 9. 30. 12:40
문제 : https://programmers.co.kr/learn/courses/30/lessons/12973?language=javascript 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr - s의 길이는 최대 1,000,000이다. 즉 O(NlogN) 이하로 처리해야 한다. - 문자열 문제에서 이정도의 길이제한이 주어진다면, 이중 for문 이상의 알고리즘을 구현하지 못하므로 스택/큐를 고민해야한다. function solution(s) { let stack = [] for(let char ..
-
[Codility - Counting Elements] BracketsAlgorithm/자료구조 2021. 9. 20. 13:34
문제 링크 NumberOfDiscIntersections coding task - Learn to Code - Codility Compute the number of intersections in a sequence of discs. app.codility.com - 스택 문제중에서도 가장 쉬운 문제인 것 같다. 백준 브론즈 냄새가.. - 자바스크립트는 C++처럼 stack STL을 제공하지 않지만, array를 잘 활용하면 stack과 queue를 사용할 수 있다. - N은 200,000 이하의 양의 정수이다. 따라서, O(NlogN) 이하의 알고리즘을 구현해야 하고, 0일때 예외 처리를 해 주어야 한다. function solution(S) { if(S.length === 0) return 1; le..
-
[Codility - Counting Elements] frog_river_oneAlgorithm/자료구조 2021. 9. 17. 15:19
https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/ FrogRiverOne coding task - Learn to Code - Codility Find the earliest time when a frog can jump to the other side of a river. app.codility.com - array의 최대 사이즈는 100,000이므로, O(NlogN) 이하로 알고리즘을 구현해야 한다. - Map을 사용해서 Hash로 구현을 한다. leaf의 위치를 key로 한다. function solution(X, A) { let hashMap = new Map() let numOfLeaves = 0 fo..
-
[Codility - Arrays] OddOccurrencesInArrayAlgorithm/자료구조 2021. 9. 16. 10:05
https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ OddOccurrencesInArray coding task - Learn to Code - Codility Find value that occurs in odd number of elements. app.codility.com - Array의 element수가 최대 100만이므로, n^2 이상의 시간복잡도 알고리즘은 바로 시간초과가 난다. O(NlogN) 이하의 알고리즘으로 해결해야 한다. - Hash를 활용하기 위해 Map 객체를 활용했다. 전체 데이터를 한 번씩 순회하면서 O(N), 각 순회당 key의 존재 여부를 탐색하는(Map.has()) 데에 O(log..