[프로그래머스] Lv.1 체육복 (Java)

문제

나의 풀이

예를 들어 lost = {2,4} , reserve = {1,3}일 경우, 2번이 3번에게 빌리면 4번은 빌릴 곳이 없다. 따라서 밑의 로직을 따라야 한다.

• lost±1이 전부 reserve에 존재할 경우, lost-1의 번호에게 먼저 빌린다.

첫 시도 : 제한사항 바로 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있고, 이 학생은 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없다 을 간과하여 실패하였다.

• lost[i]의 번호가 reserve에 존재할 경우, lost의 번호(자기자신)에게 빌린다.
  이 경우 다른 번호들과 함께 for문을 돌릴 경우, 위의 다른 법칙에 의해 다른 번호에게 체육복을 빌려줘버리는 경우가 생길 수 있으므로 무조건 먼저 처리해주어야 한다.

다른 자료구조를 사용하지 않기 위해서 lost 배열을 순회하며 해당 번호가 reserve에 존재할 경우, 관련 연산을 처리하고 '-1'을 넣어주어서 해결하려고 했으나, 학생들의 번호에 대한 제한사항이 따로 적혀있지 않아 음수 번호가 들어올 수도 있다고 판단하여 lostSet을 추가하는 방식으로 구현했다.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> reserveSet = new HashSet<>();
        Set<Integer> lostSet = new HashSet<>();
        int borrowed=0;

        for(int student : reserve) {
            reserveSet.add(student);
        }
        for(int student : lost) {
            if(reserveSet.contains(student)) {
                borrowed++; reserveSet.remove(student);
            }
            else {
                lostSet.add(student);
            }
        }

        for(int lostOne : lostSet) {
            if(reserveSet.contains(lostOne-1)) {
                borrowed++; reserveSet.remove(lostOne-1);
            }
            else if(reserveSet.contains(lostOne+1)) {
                borrowed++; reserveSet.remove(lostOne+1);
            }
        }

        return n-lost.length+borrowed;
    }
}

다른 풀이

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost) 
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++;

        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}

굳이 Set을 쓰지 않고 배열으로 구현한 풀이이다.
위의 for문 두 개를 돌면서 lost[i]의 번호가 reserve에 존재할 경우, lost의 번호(자기자신)에게 빌린다. 에 대한 처리가 같이 되는 것을 알 수 있다.
시간복잡도는 내 풀이와 비슷한데, 배열 하나로 풀 수 있어 좋은 것 같다.

후기

문제를 제대로 읽어보지 않고 계속 이상한 것들만 고치다가 40분을 썼던 문제.
모든 제한사항들을 꼼꼼히 읽어보자는 아주 당연한 교훈을 얻었다 .. ^^