🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 문제를 보자마자 양 쪽에 인덱스를 가리키는 변수 2개를 두고 구간을 줄여가며 구해야겠다고 생각했는데, 이게 투 포인터(Two pointer) 알고리즘이더군요. 몰랐지만 자연스럽게 사용하게 되었습니다..? 풀이 방식은 다음과 같습니다. gems 배열을 순회하며 보석의 종류 개수를 알아낸다. 시작 인덱스(start)와 끝 인덱스(end) 변수를 각각 0으로 두고, 보석의 종류 개수를 다 포함하는 구간이 될 때까지 end를 증가시킨다. 보석의 종류를 모두 포함하는 가장 작은 구간까지..

🔗문제 보러가기 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🧑‍💻풀이 과정 string을 스택(stack)처럼 사용하여 풀었습니다. 정답을 저장할 string 변수(answer)를 따로 준비한 후, 주어진 문자열을 차례대로 순회하였습니다. 그리고 다음과 같은 과정을 진행해 주었습니다. 현재 읽은 문자열을 answer 변수에 넣습니다. 현재 읽은 문자열이 폭발 문자열의 마지막 문자와 같다면, 다음 과정을 거칩니다. answer와 폭발 문자열을 뒤에서부터 차례대로 읽으며 비교합니다. 두 문자열..

🔗문제 보러가기 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🧑‍💻풀이 과정 등간격으로 설치할 수 있는 가장 큰 간격을 매개변수 탐색으로 구하면 됩니다. 입력 받은 집 위치들을 배열(arr)에 담고, 오름차순으로 정렬해준 뒤에 다음 과정을 진행해 주었습니다. left = 0 (첫 번째 ~ 첫 번째 공유기 사이의 범위), right = arr[N - 1] (첫 번째 ~ 마지막 공유기 사이의 범위) mid = (left + right) / 2로 중간 범위값을..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 (1)자동으로 오름차순으로 정렬되고, (2)중복 숫자 저장이 되며, (3)최솟값과 최댓값에 바로 접근할 수 있는 자료구조를 선정해야 합니다. 네, 바로 multiset이죠. multiset을 이용하면 쉽게 구현할 수 있습니다. 알고리즘은 다음과 같습니다. 공백을 기준으로 입력을 분리하여, "명령어"와 "데이터" 문자열로 분리합니다. "명령어"가 'I(대문자 i)'라면, multiset에 데이터를 삽입합니다. "명령어"가 'D'라면, 그 뒤에 오는 데이터가 1이냐, -1이냐에 따..

🔗문제 보러가기 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🧑‍💻풀이 과정 매개변수 탐색으로 풀 수 있습니다. 저는 다음과 같이 풀었습니다. 입력 받은 예산들을 오름차순으로 정렬합니다. 예산들의 합계가 M 이하라면, 예산들 중 최댓값(배열의 마지막 값)을 출력하고 종료합니다. 그게 아니라면, 최소 예산값(1)과 최대 예산값(배열의 마지막 값)을 가지고 이분 탐색을 시작합니다. "mid = (left + right) / 2" 값을 계산합니다. 예산의 총 합계를 계산하되, mid 값보다 큰 예산은 mi..

🔗문제 보러가기 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🧑‍💻풀이 과정 N이 최대 \( 10^5 \)라서, 당연히 \( \mathrm{O(n^2)}\) 알고리즘은 바로 컷 당합니다. 그렇다면, A[i][j] = \( i \times j \)으로 구성되는 2차원 배열은 만들 수가 없다는 얘기가 되는데 어떻게 풀어야 할 지 막막했습니다. 결국 다른 분들의 힌트를 찾아서 살펴 봤네요. 세상엔 정말 똑똑한 사람들이 많은 것 같습니다. 어떻게 이런 생각을 해낼까란 감탄이 나올 정..