본문 바로가기

알고리즘 부셔버렷/ProblemSolving45

[프로그래머스] 소수 찾기 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 소수 찾기 문제입니다. numbers return example.. "17" 3 7, 17, 71 "011" 2 11, 101 해결 과정 주어진 문자열의 숫자들로 구할 수 있는 모든 부분집합들 구합니다. ex) "17" => 1, 17, 71 부분집합을 구하는 과정에서 부분집합의 앞자리가 0이거나 부분집합이 0이나 1인(1은 소수에 포함x) 경우를 제외하고 구할 수 있었던 모든 부분집합을 배열에 저장합니다. 이때 제가 구현한 방법에서는 문자열 내에 중복되는 숫자가 있을 시 중복된 부분집합을 가질 수있어서, 부분집합을저장한 배열의 중복된 부분을 제거합니다.(erase unique 기법을 사용하였습니다.) 이후 소수인지를 판별 함수를 통해 .. 2022. 6. 10.
[프로그래머스] 가장 큰 수 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 가장 큰 수 문제이다. 해결 과정 본 문제를 그냥 정수로 해결할 시 상당히 큰 범위의 수가 나올 수 있어 문자열로써 다루었습니다. 본 문제를 정렬하기 앞서 그냥 주어지는 정렬함수의 조건으로는 해당 문제를 풀 수 없어 사용자정의 조건을 만들었습니다. 그 조건은 비교하는 숫자문자들끼리 서로 덧붙혀 더 큰 숫자가 나오는 경우를 앞쪽에 정렬하는 것 입니다. 이렇게 정렬된 문자배열을 앞에서부터 덧붙혀 반환하면 정답입니다. 코드 전문 #include #include #include using namespace std; string solution(vector numbers) { string answer = ""; vector str_nums; in.. 2022. 6. 9.
[프로그래머스] 프린터 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 프린터 문제입니다. 해결 과정 문제 특성 상 앞에 있는 원소를 뒤로 보낸다거나 앞에 있는 원소를 제거하는 작업이 많아. deque를 채택하였습니다. 문제에선 가장 중요도가 높은 작업물의 출력을 우선 시 하기에 priority queue를 사용할까 하였지만 그렇게 되면 우리가 찾는 원소가 중복의 경우에는 구분할 수가 없어 포기하였습니다. 전체적인 흐름은 deque가 빌 때 까지 반복하며 반복중에 우리가 찾는 원소가 나가면 반환과 종료합니다. deque의 가장 큰 원소를 찾기 전까지 가장 큰 앞의 원소들을 전부 deque의 뒤로 보냈습니다. 그리고 가장 큰 원소를 출력하게 되면서 출력물의 갯수를 더하고 값을 deque에서 제거를 합니다. 이.. 2022. 6. 9.
[프로그래머스] 튜플 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 튜플 문제입니다. 해결 과정 튜플의 원소들에게는 정해진 순서가 있기에 원소들을 보면 자신보다 작은 집합에서 한 가지의 요소만 더 더해진 형태로 있습니다. 이 점을 이용해 작은 집합부터 체크를 해서 중복된 요소를 배제하겠습니다. 우선 주워진 문자열에서 각 집합별로 뽑아내 배열에 저장합니다. 각 집합별로 뽑아내며 이때 나오는 모든 원소들을 중복을 가리기 위한 배열에 다음과 같은 {원소, 0} pair의 형태로 저장합니다. 이후 각 집합의 길이 별로 정렬을 합니다. 이후 집합의 요소들을 불러들여 중복을 체크하고 중복 되지 않았다면 반환배열에 저장하고 중복확인배열의 본인 인덱스 값 0을 1로 바꿉니다. 이 과정을 마친 뒤 반환배열을 반환합니다... 2022. 6. 7.
[프로그래머스] 수식 최대화 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 수식 최대화 문제입니다. 해결 과정 이번 문제는 주워진 식에서 *, +, - 세 연산자의 우선순위를 바꿔가며 얻을 수 있는 가장 큰 수를 구하는 문제입니다. *, +, - 로 얻을 수 있는 모든 경우는 6개이며 저는 순열을 이용하여 모든 경우에 접근하였습니다. 우선 주워진 식이 문자열의 형태라 숫자와 연산자를 따로 분리해야합니다. 이후 각 순열마다 우선순위에 맞춰 연산을 진행합니다. 우선순위가 가장 빠른 연산자부터 식에서 찾아 그 앞 숫자와 뒷 숫자를 연산해 스택에 집어 넣습니다. 이러한 과정을 가장 효율적으로 수행하는 자료구조는 stack이기에 채용하였습니다. 이후 해당 순열에서 얻을 수 있었던 가장 큰 수를 배열에 담으며 모든 경우에.. 2022. 6. 7.
[프로그래머스] [1차] 뉴스 클러스터링 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 [1차] 뉴스 클러스터링 문제입니다. 해결 과정 입력형식에서 볼 수 있듯 대소문자에 대한 구분을 하지 않습니다. 모든 알파벳을 소문자로 바꾸고 각 문자열에서 앞 뒤 모두 알파벳인 경우를 추출해 배열에 담습니다. 이후 합집합과 교집합의 수를 구해야하는데 합집합은 두 배열의 사이즈의 합에서 교집합의 수 만큼 뺸 것이니 교집합만을 구하면 됩니다. 교집합을 구하기 위해 두 배열 중 하나가 다 탐색될 때까지 순회합니다. 이 과정에서 중복을 허용해야하기 때문에 한 번 접근했던 부분은 visited 배열을 두어 똑같은 위치에 대한 중복을 방지합니다. 그리고 이 과정이 끝나고 나면 출력 형식에 맞춰 연산하고 반환합니다. 코드 전문 #include #i.. 2022. 6. 6.
[프로그래머스] 메뉴 리뉴얼 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 메뉴 리뉴얼 문제이다. course별로 가장 많이 불린 조합들을 반환하는 문제입니다. 가장 많이 불린 횟수가 중복될 경우 중복 모두 반환합니다. 해결 과정 총 메뉴는 10개까지 시킬 수 있음으로 크기 11개의 해쉬테이블을 생성하고 각 손님들의 주문 속 메뉴들의 모든 조합을 구하여 조합의 갯수 별로 저장을 합니다. 각 조합들의 길이 당 가장 많이 주문된 횟수를 저장할 배열을 11개의 크기로 생성해 저장합니다. 이제 각 주문별로 조합을 구하며 중복된 조합이 나올 경우 해당 조합의 수를 올려줍니다. 그리고 중복된 조합의 주문된 횟수가 현재 조합의 길이의 가장 많이 주문된 횟수보다 크다면 대체합니다. 이렇게 조합과 불려진 횟수와 최대 불려진 횟.. 2022. 6. 5.
[프로그래머스] 짝지어 제거하기 (문제 설명, 해결 과정, 코드 전문, c++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 프로그래머스의 짝지어 제거하기 문제입니다. 해결 과정 주어진 문자열의 문자를 하나 하나 스택에 담아 기존 스택의 최상위 값과 추가될 값이 동일하다면 최상위 값을 제거하고 동일하지 않다면 추가될 값을 그대로 저장합니다. 문자열의 모든 문자를 전부 담은 이후 스택에 남은 값이 존재하지 않는다면 1을 반환 그렇지 않은 경우엔 0을 반환합니다. 코드 전문 #include #include using namespace std; int solution(string s) { int answer = -1; stack stk; for (auto ch : s) { if (!stk.empty() && stk.top() == ch) stk.pop(); else stk.pus.. 2022. 6. 3.

티스토리툴바