완주하지 못한 선수 LEVEL 1 https://programmers.co.kr/learn/courses/30/lessons/42576?language=cpp 문제 풀이 (효율성 X) 단순하게 생각하면 됩니다. 완주선수 목록에서 string을 하나씩 꺼낸다. 참가자 목록에서 찾아서 지운다. 마지막으로 남은 한 명의 이름을 참가자 목록에서 출력한다. 하지만 이는 효율성 테스트를 통과하지 못합니다. 우선 최대 100,000번 for문을 반복합니다 그리고 cpp의 find를 이용해 찾게되면 제일 끝에 있다면 100,000 찾아봐야 될 수도 있습니다 즉 O(n^2 + n) = O(n^2) 이 걸릴 것으로 예상됩니다 (n은 vector::erase의 time complexity) 문제 풀이 (효용성 O) 우선 s..

프로그래머스 월간 코드 챌린지 시즌 1 삼각 달팽이 Level 2 삼각 달팽이 문제 정리 정수 n이 주어진다. 밑변의 길이와 높이가 n인 삼각형이 있다. 이 삼각형에서 맨 위 꼭짓점부터 반시계 방햐야으로 달팽이 채우기를 진행 한다. 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 한다. 문제 풀이 n이 최대 1000이므로 시뮬레이션 처럼 돌린다. 백준의 마법사 상어와 토네이드와 비슷한 방식으로 풀었다. 달팽이 모양으로 움직이기 위한 방향은 세가지가 있다.(아래, 오른쪽, 왼쪽 위 대각선) 이를 각각 구현한다. 단계 마다 이동해야 하는 step수를 steps 배열에 담는다. 예를들어 n이 4 이면 3(아래 이동), 3(오른쪽 이동), 2(대각선 이동), 1(아래 이동) 이동하게 된다..

프로그래머스 월간 코드 챌린지 시즌 1 두 개 뽑아서 더하기 Level 1 두 개 뽑아서 더하기 문제 정리 주어진 배열에서 서로 다른 인덱스의 두 수를 뽑는다. 더해서 만들 수 있는 모든 수를 오름차순으로 정렬하여 return 하라 문제 풀이 이중 for문을 돌면서 i와 j가 같지 않은 경우 set에 넣는다. (중복 제거를 위해 set에 넣음) set크기의 배열을 생성 iterator를 통해 set의 원소들을 모두 뽑아 배열에 넣는다. Arrays.sort()를 통해 오름차순으로 정렬한다. 프로그래머스 두 개 뽑아서 더하기 java 두 개 뽑아서 더하기 cpp 가능한 조합을 모두 vector에 넣고 sotring을 우선 진행한 다음에 unique 함수를 통해 연속된 수 중 중복된 수를 지웠습니다 이 외에..

프로그래머스 올바른 괄호 자바(java) 풀이 Level 2 Stack [올바른 괄호]](https://programmers.co.kr/learn/courses/30/lessons/12909#) 문제 정리 괄호가 올바로 짝지어져 있다: '('문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫힌다 문자열 s가 주어졌을때 올바른 괄호 문자열인지 아닌지 판별하여라 문자열의 길이는 최대 100,000 문자열 s는 '(' ')' 만으로 이루어져 있다. 힙, 우선순위 큐 이 문제는 stack을 이용하면 쉽게 구현할 수 있습니다. 이와 비슷한 문제가 이번 카카오 코테에도 나왔습니다. 그렇기테때문애 확실히 이해하는게 중요합니다. 주어진 문자열을 캐릭터(문자) 배열..

프로그래머스 행렬의 곱셈 c++ 풀이 Level 2 연습문제 행렬의 곱셈 문제 정리 2차원 행렬 arr1, arr2가 주어질때 두 행렬을 곱한 결과를 반환하는 함수를 작성하여라 행과 열의 길이는 2 이상 100 이하이다. (최대 100x100) 행렬의 원소는 -10 이상 20 이하의 자연수이다. 곱할 수 있는 배열만 주어진다. 문제 풀이 20^2 x 100 = 400 x 100 = 40000으로 int형으로 가능 이 문제는 단순히 행렬 곱셈의 개념만 알고 있다면 풀 수 있습니다. 2차원 벡터를 다루는 문제로 좋은 예제라고 생각합니다. (실제로 제가 그랬음) 왼쪽 행렬의 i행, 오른쪽 행려의 j열을 sumproduct 하면 새로운 행렬의 (i,j) 위치의 값이 됩니다. 예를들어 arr1의 1행, arr2의..

프로그래머스 피보나치 수 c++ 풀이 Level 2 연습문제 피보나치 수 문제 정리 n이 주어질 때 n번째 피보나치 수를 1234567로 나눈 나머지를 구하여라 n은 2이상 100000 이하이다. 문제 접근 피보나치 수를 알기 위해서는 이전의 2개의 수만 알면 된다. 그렇기 때문에 2개의 수만 관리한다. n이 최대 100,000이기 때문에 배열을 모두 만들면 낭비이다. 또한 계속 값을 더해나간 후 마지막에 모듈러 연산을 하면 값이 범위를 넘어 이상한 값이 나올 수 있다. 그렇기 때문에 모듈러 연산의 성질을 이용하면 간단히 풀 수 있다. 모듈러 연산의 성질 이 성질만 안다면 간단히 풀 수 있습니다. (a + b) % c = ((a % c) + (b % c)) % c 예를들어 (10 + 1) % 3 = (1..