hwooo

https://leetcode.com/problems/jump-game-iii/풀이현재 인덱스를 큐에 저장하며 탐색한다.다음 인덱스를 탐색할 때는 배열의 범위인지, 이미 방문한 지점인지 확인하고 처음 방문한 지점일 때 큐에 삽입하여 탐색한다.코드class Solution {public: bool visited[50000]; bool canReach(vector& arr, int start) { queue q; q.push(start); visited[start] = true; while (!q.empty()) { int now = q.front(); q.pop(); // 현재 인덱스의 ..

https://leetcode.com/problems/super-ugly-number/description/풀이 1우선순위 큐를 사용, 적은 수부터 계산했다. 현재 수에 prime 수들을 곱해 ugly number를 찾는다. 이 때 곱한 값이 signed int 범위 내에 있는지 확인하고, 이를 우선순위 큐에 넣는다. 큐에서 꺼낼 때에는 같은 값을 모두 큐에서 빼며 중복값을 제거했다. 위의 방법이 너무 느려 다른 사람들의 풀이를 봤고, 다른 방법으로 풀어보았다. 풀이 2n만큼 순회하며 n번째 ugly number를 찾는다.우선순위 큐에 {현재 숫자, prime 숫자, 인덱스}를 저장하고, 하나씩 꺼내면서 현재숫자와 직전 ugly number를 비교하며 중복값을 제거한다. (중복값은 삽입하지 않는다)우선순..

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이주어진 전선을 트리 형태로 저장 후, 전선을 하나씩 끊으며 나눠진 전력망에서 한 쪽의 송전탑 개수를 구함.해당 값과 나머지 값의 차를 비교하며 최솟값을 구함.코드#include #include #include #include using namespace std;#define MAX_VAL 101vector tree[MAX_VAL];// 잘린 상태 중 한 쪽의 송전탑 개수 구하기int getDividedCount(int v1, int v2, ..

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/풀이O(log n) 의 시간복잡도 + 정렬된 배열이라 이분탐색으로 풀어야겠다는 생각이 들었다.이분탐색 후 찾은 target의 인덱스부터 앞 뒤로 탐색하며 target의 범위를 찾는다.코드class Solution {public: vector searchRange(vector& nums, int target) { // 주어진 배열이 비었을 때 if (nums.empty()) return {-1, -1}; // 이분탐색 int start = 0, mid, en..

https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이입력된 문자열을 '{', '}' 기준으로 나누고, 그 문자열을 ',' 기준으로 나누며 숫자로 변환한다.이렇게 나눠진 숫자 배열들을 길이 순으로 정렬하여 앞에서부터 탐색한다. 이 때 나온 값인지 확인하여 나오지 않은 값이면 answer 배열에 저장하며 답을 만든다.코드#include #include #include using namespace std;// , 기준으로 파싱 및 숫자 변환vector strToNumList(string s) { ..

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/풀이토픽이 투포인터인 건 알았지만 풀이가 생각나지 않아 답지를 봤다.1번 순회하며 앞에서부터는 최댓값, 뒤에서부터 최솟값을 찾는다.maxVal을 업데이트하면서 nums[i] 마찬가지로 minVal은 뒤에서부터 탐색하며 begin을 갱신하며 최소 구간을 찾는다. 투포인터라 포인터 두 개로 탐색해야 한다고 생각했는데 특정 값을 저장하는 방식으로 사용하는 건 생각하지 못 했다.어렵다...ㅠ코드class Solution {public: int findUnsortedSubarray(vector& nums) { // 정렬된 값이 들어왔을 때 int begin = -..