코딩테스트 연습 - 체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번
programmers.co.kr
처음 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> temp(n, 1);
int i = 0, count = 0;
i = reserve.size() - 1;
while(i > 0){
temp[reserve[i] - 1] += 1;
i--;
}
if(reserve.size() * 2 >= n) return n;
else{
i = lost.size() - 1;
while(i > 0){
temp[lost[i] - 1] -= 1;
i--;
}
for(int i = 0; i < n; i++){
if(temp[i] >= 2){
if(temp[i - 1] != 0 || temp[i + 1] != 0){
count++;
}
}else{
answer += temp[i];
}
answer -= count;
}
}
return answer;
} |
12개 중 3개 맞음 |
두 번째 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> temp(n, 1);
int i = 0, count = 0;
i = reserve.size() - 1;
while(i > 0){
temp[reserve[i] - 1] += 1;
i--;
}
//if(reserve.size() * 2 >= n) {
// return n;
//}else{
i = lost.size() - 1;
while(i > 0){
temp[lost[i] - 1] -= 1;
i--;
}
for(int i = 0; i < n; i++){
answer += temp[i];
if(temp[i] >= 2){
count++;
if(temp[i - 1] != 0 || temp[i + 1] != 0){
answer -= count;
}
}
}
return answer;
} |
12개 중 5개 맞음 |
세 번째 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> pe(n, 1);
int i = 0, count = 0;
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1] += 1;
i--;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1] -= 1;
i--;
}
for(int i = 0; i < n; i++){
answer += pe[i];
if(pe[i] == 2){
count++;
if(i > 0 && pe[i - 1] != 0){
answer -= 1;
}
if(i < n && pe[i + 1] != 0){
answer -= 1;
}
}
}
if(n > 4 && count * 2 >= n) answer = n;
return answer;
} |
 |
네 번째 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> temp(n, 1);
int i = 0, count = 0;
i = reserve.size() - 1;
while(i >= 0){
temp[reserve[i] - 1] += 1;
i--;
}
i = lost.size() - 1;
while(i >= 0){
temp[lost[i] - 1] -= 1;
i--;
}
for(int i = 0; i < n; i++){
answer += temp[i];
if(temp[i] >= 2){
count++;
if(temp[i - 1] != 0 || temp[i + 1] != 0){
answer -= count;
}
}
}
if(count * 2 >= n) answer = n;
return answer;
} |
12개 중 6개 맞음 |
다섯 번째 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> pe(n, 1);
int i = 0, count = 0;
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1] += 1;
--i;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1] -= 1;
--i;
}
for(int i = 0; i < n; i++){
answer += pe[i];
if(pe[i] > 1){
count++;
if(pe[i - 1] > 0 || pe[i + 1] > 0){
answer -= 1;
}
}
}
if(n > 3 && count * 2 >= n) answer = n;
return answer;
} |
 |
제한 사항 추가해서 다시 돌렸는데 맞았다.
 |
 |
... 그런데 실제 실행하면 틀린다. 하.. 열받아서 프로그래머스 질문에 다른 분들이 알려준 테스트 케이스 다 추가해보고 틀린 부분있으면 고치기로 했다. 넘 답답해서.... 지금...... 땀이 나네...ㅎ...
 |
 |
 |
 |
  |
 |
8번 |
 |
 |
 |
 |
 ..ㅎ |
 |
 |
 |
 |
 |
..아악..... |
 |
 |
| ...? 이런 케이스도 있단 말야..?  |
이건 뭐 추가하나 마나... 틀린 건 똑같이 틀림. 그래도 혹시 모르니 추가함. |
 |
드디어 틀린 테케 찾았다..ㅠㅠㅠ : 뒷 사람에게 여벌 빌려줄 때, 발생하는 케이스가 적용이 안 된 듯 보인다.  |
| 코드 다듬고 고쳤는데 여전히 7번 8번은 실패가 뜸 ... 내가 진짜.. 다른 사람 코드 참고 안 하고 해결한다 진짜.. ......하,,, 일단 저녁을 먹고 와야겠다. > 코드는 아래에 여섯 번째 코드 |
 |
여섯 번째 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> pe(n, 1);
int i = 0, count = 0;
sort(reserve.begin(), reserve.end());
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1] += 1;
--i;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1] -= 1;
--i;
}
for(int i = 0; i < n; i++){
if(pe[i] == 2){
count++;
if(pe[i - 1] > 0 || pe[i + 1] > 0){
pe[i] -= 1;
if(pe[i - 1] == 0 || pe[i + 1] == 0){
pe[i] += 1;
}
}
}
answer += pe[i];
}
if(n > 3 && count * 2 >= n) answer = n;
return answer;
}7번 8번이 틀리니까.. index가 0일때랑 마지막일 때는 각각 뒤와 앞만 체크할 수 있므로 이에 해당하는 제한 사항을 추가했다.
일곱 번째 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> pe(n, 1);
int i = 0, count = 0;
sort(reserve.begin(), reserve.end());
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1] += 1;
--i;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1] -= 1;
--i;
}
for(int i = 0; i < n; i++){
if(pe[i] == 2){
count++;
if(i == 0){
if(pe[i + 1] > 0){
pe[i] -= 1;
if(pe[i + 1] == 0){
pe[i] += 1;
}
}
}else{
if(pe[i - 1] > 0 || pe[i + 1] > 0){
pe[i] -= 1;
if(pe[i - 1] == 0 || pe[i + 1] == 0){
pe[i] += 1;
}
}
}
}
answer += pe[i];
}
if(n > 3 && count * 2 >= n) answer = n;
return answer;
}
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
 |
... |
테스트 케이스는 모두 정답인데, 7번만 틀린 이유는 뭘까......... 저녁 먹고,,, 다시 생각해봐야겠다.
여덟번째 코드
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
vector<int> pe(n, 1);
vector<int> temp(n, 0);
int i = 0, count = 0;
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1]--;
i--;
}
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1]++;
i--;
}
for(i = 0; i < n; i++){
if(pe[i] == 2){
count++;
pe[i]--;
if(i == 0 || pe[i + 1] == 0) pe[i + 1]++;
else if(i == n - 1 || pe[i - 1] == 0) pe[i - 1]++;
else{
if(pe[i - 1] <= 0) pe[i - 1]++;
if(pe[i + 1] <= 0) pe[i + 1]++;
}
}
}
for(i = 0; i < n; i++){
answer += pe[i];
}
if(count * 2 >= n) answer = n;
return answer;
}
그나저나 복기 안 하고, 이것저것 수정하다보니 vector로 answer 값을 +하려고 했는데, 단순 배열로 값을 체크하는 게 안전한 것 같아서 array로 다시 변경했다.
최종
// *************** 로 표시해둔 부분 다시 고치기
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
int pe[30];
int i = 0, count = 0;
for(i = 0; i < n; i++) pe[i] = 1;
i = 0;
while(i < reserve.size()){
pe[reserve[i] - 1]++;
i++;
}
i = 0;
while(i < lost.size()){
pe[lost[i] - 1]--;
i++;
}
// ***************
for(i = 0; i < n; i++){
if(pe[i] == 2){
pe[i]--;
if(i == 0 && pe[i + 1] == 0) pe[i + 1]++;
else if(i == n - 1 && pe[i - 1] == 0) {
pe[i - 1]++;
break;
}
else{
if(pe[i - 1] == 0) pe[i - 1]++;
if(pe[i + 1] == 0) pe[i + 1]++;
}
}
//if(pe[i] > 1) pe[i] = 1;
answer += pe[i];
}
return answer;
} |
 |
진짜진짜 최종
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
int pe[30] = {0, };
int i = 0;
for(i = 0; i < n; i++) pe[i] = 1;
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1]++;
i--;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1]--;
i--;
}
for(i = 0; i < n; i++){
if(pe[i] == 2){
if(i > 0 && pe[i - 1] == 0) {
pe[i]--;
pe[i - 1]++;
}
if(i < n && pe[i + 1] == 0) {
pe[i]--;
pe[i + 1]++;
}
}
}
for(i = 0; i < n; i++){
if (pe[i] > 0) answer++;
//answer += pe[i];
}
return answer;
} |
ㅎㅎ for과 while의 문제도 아니었고, if 문 내에서 발생한 문제였다. if 2일 때 { 모든 경우의 수 체크 }가 아니라 if{ 2일 때 / index - 1이 0일 때 / index가 0보다 클 때} if{ 2일 때 / index + 1이 0일 때 / index가 n보다 작을 때} 로 변경해줘야 11번이 맞는다. |
진짜진짜진짜 최종
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
int pe[30] = {0, };
int i = 0;
for(i = 0; i < n; i++) pe[i] = 1;
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1]++;
i--;
}
i = lost.size() - 1;
while(i >= 0){
pe[lost[i] - 1]--;
i--;
}
for(i = 0; i < n; i++){
//if(pe[i] == 2){
if(pe[i] == 2 && i > 0 && pe[i - 1] == 0) {
pe[i]--;
pe[i - 1]++;
}
if(pe[i] == 2 && i < n && pe[i + 1] == 0) {
pe[i]--;
pe[i + 1]++;
}
//}
}
for(i = 0; i < n; i++){
if (pe[i] > 0) answer++;
//answer += pe[i];
}
return answer;
}
* check하면서 풀었던 메모들
🧩 문제 풀이
✔ 문제 설명 숙지
* 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.
* 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
✔ 제한 사항 숙지
문제 풀기 전, 제한 사항에 명시된 내용을 숙지해야 합니다.
* 전체 학생의 수는 2명 이상 30명 이하입니다.
* 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
* 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
* 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
* 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
위 제한 사항 중, 4번과 5번... 특히 5번을 주의하여 코드를 작성합니다.
✔ 입출력 예 참고하면서 코드 작성
그리고 입출력 예를 보면서 초기 코드를 작성해줍니다.
저는 처음에 문제를 이해할 때, reserve에 담겨있는 학생만 체육복을 가진 줄 알았는데,
두 번째 입출력을 참고하니 return이 4가 될 수 없었습니다. 문제에는 명시되어 있지 않지만, 초기에 모든 학생은 체육복을 하나 가진 것으로 초기화해줘야 합니다.
첫 번째 입출력 예시
두 번째 입출력 예시
세 번째 입출력 예시
입출력 예시에는 없지만, **여벌 옷이 있는 학생이 도난 당할 경우도 생각해줘야 합니다. (제한 사항 5번 참고)
위 입출력 예시에서 2번 학생(노란색 동그라미)은 초기에 체육복을 하나(+ 1) 가졌고, 그 체육복을 도난당했습니다.(- 1)
그런데 2번 학생은 여벌 옷이 있으므로(+ 1)
최종적으로 '하나의 체육복'을 가지게 됩니다.
이때 이 학생은 1번 학생에서 체육복을 빌려주지 않고, 자기 자신이 여벌 체육복을 입어야 합니다.
✔ 체육복 개수 체크하기
저는 배열로 체육복 개수를 체크해줬습니다.
1. 배열을 n만큼 1로 초기화
2. 도난 당한 학생의 체육복 -1
3. 여벌이 있는 학생 체육복 +1
위와 같이 check한 후에 체육복이 2개 있는 학생일 때를 체크해줬습니다.
그리고 배열 index가 0일 경우와 n - 1 경우도 체크해줘야 합니다.
index가 0일 경우 index - 1의 원소를 체크할 수 없고, n - 1일 경우 index + 1의 원소를 체크할 수 없기 때문입니다.
✔ lost와 reserve 정렬하기
테스트 케이스를 체크하면서 다양한 질문과 답변을 본 결과 lost와 reserve가 [2, 5, 3]이나 [2, 1] 등으로 정렬되지 않은 상태가 있을 수 있다고 합니다. 저는 코드 짤 때, 의도한 건 아니지만 애초에 check 배열에 lost 학생과 reserve 학생을 체크해줬습니다.
i = reserve.size() - 1;
while(i >= 0){
pe[reserve[i] - 1]++;
i--;
}위의 예시처럼요. 저처럼 작성하지 않았는데, 코드 채점 시 실패하시는 경우, lost와 reserve를 체크하기 전에 각 배열을 오름차순으로 sort해주세요.
🌱 정답코드
'OLD_알고리즘 > Programmers - 알고리즘' 카테고리의 다른 글
| Programmers ] Level 1 - 예산 (0) | 2021.01.25 |
|---|---|
| Programmers ] Level 1 - 완주하지 못한 선수 (0) | 2021.01.22 |
| Programmers ] Level 1 - 모의고사 (0) | 2021.01.13 |
| Programmers ] Level 1 - 가운데 글자 가져오기 (0) | 2021.01.10 |
| Programmers ] Level 1 - 나누어 떨어지는 숫자 배열 (0) | 2021.01.10 |
댓글