🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 처음에는 백트래킹을 통해 조합으로 풀었는데, 테스트 케이스 1번에서 시간 초과가 났습니다. 아무래도 최대 입력 범위인 30개의 옷이 들어있었던 것 같네요. 어떻게 풀 지 고민하다가, 어느 한 분의 수학적 아이디어를 보고 깨달았습니다. 코니는 하루에 최소 한 개의 의상은 입는다. 의상 종류 A의 옷 개수가 n개라면, 해당 종류의 옷들 중 하나를 골라 입거나, 안 입는 경우의 수는 다음과 같다. \( {n \choose 1} + {n \choose 0} = n + 1 \) 따라서,..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 행렬 A와 행렬 B가 있다고 할 때, 다음과 같이 곱셈을 진행합니다. // 행렬 A // 행렬 B 2 3 2 5 4 3 4 2 4 X 2 4 1 3 1 4 3 1 1 ------------------------------------------------------------------------------ /* A의 i번 행과 B의 j번 열 원소들을 각각 곱하여 합하기 */ (2 x 5) + (3 x 2) + (2 x 3) = 22 // A의 0행 x B의 0열 (2 x 4) ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 \(n\)의 최대 개수가 천만 개라, 2차원 배열을 만들어 수를 저장하고, 나눗셈과 몫 연산을 통해 left ~ right 사이의 숫자만 추출하면 되지 않을까 생각하여 코드를 짰는데, 시간 초과가 났습니다. 시간을 더 줄일 방도가 필요했습니다. 방법을 모색하던 중, (i, j)에 저장되는 숫자는 max(i + 1, j + 1)이라는 특성을 발견하였습니다. 0 1 2 3 --------- 0 | 1 2 3 4 1 | 2 2 3 4 2 | 3 3 3 4 3 | 4 4 4 4 // ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 중복없이 저장을 해야 하니, set에 저장하였습니다. 연속 수열 합계를 구하는 부분에선 deque를 활용하여 풀었습니다. 인덱싱이 가능하고, 맨 앞 맨 뒤 삽입 삭제가 효율적인 deque라면 좋은 효율을 낼 것 같다고 생각하였습니다. 알고리즘은 다음과 같습니다. 1. vector에 저장되어 있던 elements의 원소들을 모조리 deque로 옮겨 저장합니다. 2. 0번 인덱스부터 추출할 개수 (1 ~ element.size()) 인덱스만큼의 합계를 구합니다. - 합계를 set에..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 문제를 잘 읽어야 합니다. 보트에 탈 수 있는 사람은 단 두 명입니다. 1. 사람들의 무게를 오름차순으로 정렬 2. 가장 작은 무게를 지닌 사람의 인덱스(li = 0)와 가장 무거운 무게를 지닌 사람의 인덱스(hi = people.size() - 1)를 지정 3. people[li] + people[hi] > limit 이라면, 제일 무거운 사람 혼자 밖에 탈 수 없으므로 answer++, hi-- 4. people[li] + people[hi] hi가 될 때까지 3, 4번을 ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 처음에는 정규식을 활용해서 replace()를 할까 생각했었는데 문제의 의도(짝을 발견하면 제거하고 앞 뒤 붙이는)와는 맞지 않았고, 짝을 기준으로 앞과 뒤 문자열을 합치는 과정에서 오버헤드가 많이 발생하니 어떻게 하면 좋을까 고민이었습니다. 그런데, 복잡할 것 없이 스택(Stack)을 활용하면 정말 쉽게 풀리는 문제였습니다. 좀 더 사고를 확장하여 유연하게 할 필요가 있을 것 같네요. ✏️소스 코드 및 결과 #include #include using namespace std;..