그리디알고리즘 체육복(프로그래머스)
1차 시도
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int cnt = 0;
if(lost.length <= reserve.length){
for(int i = 0; i < lost.length; i++){
if(reserve[i] != lost[i] - 1 && reserve[i] != lost[i] + 1 && reserve[i] != lost[i]){
cnt++;
}
}
answer = n-cnt;
}else if(reserve.length < lost.length){
for(int i = 0; i < reserve.length; i++){
if(reserve[i] != lost[i] - 1 && reserve[i] != lost[i] + 1 && reserve[i] != lost[i]){
cnt++;
}
}
answer = n-cnt-(lost.length-reserve.length);
}
return answer;
}
}
예제는 맞았지만 채점해보니 16점...ㅎ
2차 시도
3개씩 비교를 하는 것은 아무래도 다른 케이스들을 생각하지 못하게 만들어서 새로운 방식을 사용하기로 함
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
//최소 lost에 없는 애들은 수업 들을 수 있음
int answer = n-lost.length;
for(int i = 0; i < reserve.length; i++){
for(int j = 0; j < lost.length; j++){
if(reserve[i] == lost[j]){
answer++;
}else if(reserve[i] == lost[j]-1){
answer++;
i++;
j++;
}else if(reserve[i] == lost[j]+1){
answer++;
i++;
j++;
}
}
}
return answer;
}
}
이번에는 50점...
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
//최소 lost에 없는 애들은 수업 들을 수 있음
int answer = n-lost.length;
for(int i = 0; i < reserve.length; i++){
for(int j = 0; j < lost.length; j++){
if(reserve[i] == lost[j]){
answer++;
}else if(reserve[i] == lost[j] + 1 && lost[j] != n){
answer++;
}else if(reserve[i] > lost[j] + 1 && lost[j] != n){
i--;
}else if(reserve[i] == lost[j] - 1 && lost[j] != 1){
answer++;
}else if(reserve[i] < lost[j] - 1 && lost[j] != 1){
j--;
}
break;
}
}
return answer;
}
}
n차 시도...ㅎ
import java.util.ArrayList;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n - lost.length;
//하나씩 지워주는 것이 정신 건강에 이로우므로 ArrayList를 사용하기로 함
ArrayList<Integer> res = new ArrayList<>();
ArrayList<Integer> los = new ArrayList<>();
//하나씩 담아준다
for(int r : reserve){
res.add(r);
}
for(int l : lost){
los.add(l);
}
//여분의 체육복을 가져왔으나, 도둑 맞았을 때
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < los.size(); j++){
if(res.get(i) == los.get(j)){
res.remove(i); //더이상 빌려줄 수 없으므로 reserve에서 하나씩 지워준다.
los.remove(j); //수업에 참여할 수 있게 되었으므로 지워준다
j--;//lost, reserve에서 모두 지워지니까 처음부터 들을 수 있는 사람처럼 되버림, 그 자리부터 다시 시작
answer++;
break;//멈춰서 다시 시작하니까
}
}
}//여기서 reserve부터 지워줘야, 여분이 도둑맞지 않은 상황에서의 여분량을 재조정 가능
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < los.size(); j++){
if(res.get(i) == los.get(j) + 1 || res.get(i) == los.get(j) - 1){
res.remove(i); //더이상 빌려줄 수 없으니까
//los.remove(j); 수업에 참여할 수 있게 됐지만 answer에서 하나씩 제하니까 바뀌면 안됨
answer++;
break; //다시 반복하도록
}
}
}
return answer;
}
}
58점... 이쯤 되니 진짜 모르겠다.
n+1차 시도
import java.util.ArrayList;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n - lost.length;
//하나씩 지워주는 것이 정신 건강에 이로우므로 ArrayList를 사용하기로 함
ArrayList<Integer> res = new ArrayList<>();
ArrayList<Integer> los = new ArrayList<>();
//하나씩 담아준다
for(int r : reserve){
res.add(r);
}
for(int l : lost){
los.add(l);
}
//여분의 체육복을 가져왔으나, 도둑 맞았을 때
for(int i = 0; i < los.size(); i++){
for(int j = 0; j < res.size(); j++){
if(res.get(j) == los.get(i)){
res.remove(j);
los.remove(i);
i--;
answer++;
break;
}
}
}
for(int i = 0; i < los.size(); i++){
for(int j = 0; j < res.size(); j++){
if(res.get(j) == los.get(i) + 1 || res.get(j) == los.get(i) - 1){
res.remove(j);
answer++;
break;
}
}
}
return answer;
}
}
for문에서 los와 res의 순서를 바꾸니 또 맞는다...
왜 이러는 걸까...
일단 los(0) 일때 res(1)~res(reserve)
los(1) 일때 res(1)~res(reserve)
...
이므로 여분의 옷이 도둑 맞을 경우에는 res, los 다 사라져야 하니까 i--해서 새 루프(?)를 다시 돌려줬던 것임
옷을 빌려주는 경우에는 lost가 1번 학생이거나 n번 학생일때, 바로 옆 번호 (2번이나 n-1번) 만이 빌려줄 수 있으므로 los를 기준으로 이중 for문을 돌려야했다.
res를 기준으로 돌리게 되면 los의 경우도 사라지게되어 answer 값에 변동이 생겨버린다.
하... 다른 분 글 참고해서 한건데로 어려우니.... level2는 또 얼마나 걸릴지...ㅠㅠㅠㅠ
Author And Source
이 문제에 관하여(그리디알고리즘 체육복(프로그래머스)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inhye-world/그리디알고리즘-체육복프로그래머스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)