https://programmers.co.kr/learn/courses/30/lessons/42862
코딩테스트 연습 - 체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번
programmers.co.kr
소스코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
// 체육복 갯수를 저장하는 n크기의 벡터 저장
vector<int> students(n,1);
int answer = 0;
//체육복 갯수 맞추기
for(int i : reserve) students[i-1]++;
for(int i : lost) students[i-1]--;
//탐욕적으로 왼쪽, 오른쪽을 살펴 체육복 가져오기
for(int i = 0 ; i < n ; i++) {
if(students[i] == 0) {
//왼쪽 친구에게 체육복 얻기
if(i>0 && students[i-1]==2) {
students[i-1]--;
students[i]++;
}
//오른쪽 친구에게 체육복 얻기
else if(i<n-1 && students[i+1] == 2) {
students[i+1]++;
students[i]++;
}
}
}
for(int n : students) if(n>0) answer++;
return answer;
}
실패코드
사실 아직도 왜 틀린지 이해를 못하겠다... 왜 탐욕법으로 하는건 되고 나름 논리적(?)이라 생각하는 코드는 안 되는걸까...
우선 프로그래머스에 질문 올려놨으니 누군가 알려줬으면 좋겠다.
https://programmers.co.kr/questions/31824
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
// 체육복 갯수를 저장하는 n크기의 벡터 저장
vector<int> students(n,1);
int answer = 0;
//체육복 갯수 맞추기
for(int i : reserve) students[i-1]++;
for(int i : lost) students[i-1]--;
//오른쪽 친구한테 체육복 빌리기
for(int i = 0; i < n-1; i++) {
if(students[i] == 0 && students[i+1] == 2) {
students[i]++;
students[i+1]--;
}
}
//왼쪽 친구한테 체육복 빌리기
for(int i = 1; i < n; i++) {
if(students[i] ==0 && students[i-1] == 2) {
students[i]++;
students[i-1]--;
}
}
for(int n : students) if(n>0) answer++;
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : 단어변환(C++, Lv.3, BFS) (0) | 2022.05.27 |
---|---|
프로그래머스 : 카펫 (C++, Lv.2, 완전탐색) (0) | 2022.05.25 |
프로그래머스 : 가장 큰 수 (C++, Lv.2,정렬) (0) | 2022.05.21 |
프로그래머스 : 전화번호 목록 (C++, Lv.2, 해시) (0) | 2022.05.20 |
프로그래머스 : 완주하지 못한 선수 (C++, Lv.1, 해시) (0) | 2022.05.20 |