분류 전체보기
[프로그래머스] 탐욕법 1. 체육복
문제 풀이 삽질을 많이 했다... 처음에 c++로 했는데, while문 안에서 인덱스를 두 개 사용하여 lost, reserve 배열의 값을 비교하려고 했다. c++의 find()나 python의 in을 사용하는것보다 시간복잡도가 줄어들 것이라고 예상했기 때문이다. 그런데 과정이 너무 복잡해지고, c++을 사용하는 의미가 없이 c로도 가능한 풀이가 되어가고 있었다. 또 인덱스를 쓰다보니 헷갈려서 시간이 오래 걸리기에 그냥 접고 파이썬으로 새로 풀었다. 그렇게 푼 게 다음과 같다. lost를 작은 쪽부터 시작했으니 reserve도 -1부터 차례로 비교했다. 이렇게 푸니 두 개의 케이스에서 실패했다. 고민해본 끝에 다음 조건에서 틀렸다는 것을 알 수 있었다. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 ..
[프로그래머스] 완전탐색 1. 모의고사
문제 풀이 이건 전체 탐색을 진행할 수 밖에 없는 문제였다. 애초에 카테고리가 완전탐색임 c++으로는 예전에 풀어놨길래 이번엔 python으로 풀어봤다. 전체적인 알고리즘은 동일하다. answers을 반복문으로 1회 돌며 주어진 패턴과 비교한다. 정답수를 저장하고 오름차순으로 배열에 넣어 반환한다. c++ #include #include #include using namespace std; vector solution(vector answers) { vector winners; vector correct{0, 0, 0}; int arrayFor2[4] = {1, 3, 4, 5}; int arrayFor3[5] = {3, 1, 2, 4, 5}; for (int i = 0; i < answers.size()..
[프로그래머스] 해시 1. 완주하지 못한 선수
풀이과정 처음엔 이중포문으로 participant 배열에서 completion배열의 이름을 찾고 만약 있다면 하나하나 지워가는 방식을 생각해봤는데 그러면 시간복잡도가 n^2이라 코테 등에서 통과되지 못할 것이라 판단해서 시도하지 않았다. 그 다음은 두 배열을 sort해서 비교하는 방법을 생각해봤다. 이건 좀 더 나은 시간복잡도를 가질 것이라고 예상한다. 그렇지만 둘다 해시를 사용하는 것 같지 않아 검색의 도움을 받았다. 해시는 파이썬 dictionary형태로 구현되어있다는 정보에 힌트를 얻어 배열을 {이름: 참가자 수} 형태로 변환하고 두 딕셔너리를 비교하여 참가자 수가 다른 이름을 반환토록 하였다. def solution(participant, completion): hashTable = {} for ..
[프로그래머스] 정렬 1. k번째 수
c++ #include #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; vector temp; for(int i = 0; i < commands.size(); i++) { temp.clear(); for(int j = commands[i][0] - 1; j < commands[i][1]; j++) { temp.push_back(array[j]); } cout