33. 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862

 

파이썬

주어진 조건에 맞춰 평범하게 코딩해 보았습니다. 최대 O(4n).

def solution(n, lost, reserve):
    clothes = [1] * n
    for each in lost:
        clothes[each - 1] -= 1
    for each in reserve:
        clothes[each - 1] += 1
    for i in range(n):
        if clothes[i] == 0:
            if i - 1 >= 0 and clothes[i - 1] == 2:
                clothes[i - 1] -= 1
                clothes[i] += 1
            elif i + 1 < n and clothes[i + 1] == 2:
                clothes[i + 1] -= 1
                clothes[i] += 1
    count = 0
    for i in range(n):
        if clothes[i] > 0:
            count += 1
    return count

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.5MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.6MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.04ms, 10.5MB)
테스트 8 〉	통과 (0.04ms, 10.8MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.04ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.04ms, 10.8MB)

count를 위해 for를 한 번 더 돌릴 필요가 없죠?. 최대 O(3n)으로 줄일 수 있습니다.

def solution(n, lost, reserve):
    clothes = [1] * n
    for each in lost:
        clothes[each - 1] -= 1
    for each in reserve:
        clothes[each - 1] += 1
    for i in range(n):
        if clothes[i] == 0:
            if i - 1 >= 0 and clothes[i - 1] == 2:
                # clothes[i - 1] -= 1  # 가독성에는 도움을 주나 생략해도 결과는 같다. 
                clothes[i] += 1
            elif i + 1 < n and clothes[i + 1] == 2:
                clothes[i + 1] -= 1
                clothes[i] += 1
            else:
                n -= 1
    return n

테스트 1 〉	통과 (0.04ms, 10.5MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	통과 (0.07ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.8MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.8MB)
테스트 7 〉	통과 (0.04ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.8MB)
테스트 9 〉	통과 (0.04ms, 10.6MB)
테스트 10 〉	통과 (0.04ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.9MB)
테스트 12 〉	통과 (0.04ms, 10.5MB)

집합 자료형을 이용하면 더 간단해질까요?
파이썬 3.7 이후로는 (정확하게는 3.6부터는 언오피셜로) 딕셔너리의 순서가 보장되었는데요.
셋도 보장되었었나? 그럴 것 같긴 한데 명확하게 읽은 적은 없는 것 같네요.

def solution(n, lost, reserve):
    reserve_set = set(reserve) - set(lost)
    lost_set = set(lost) - set(reserve)
    for rev in reserve_set:
        front = rev - 1
        back = rev + 1
        if front in lost_set:
            lost_set.remove(front)
        elif back in lost_set:
            lost_set.remove(back)
    return n - len(lost_set)

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.03ms, 10.6MB)
테스트 7 〉	통과 (0.04ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.07ms, 10.6MB)
테스트 11 〉	통과 (0.04ms, 10.6MB)
테스트 12 〉	통과 (0.04ms, 10.8MB)

혹 순서의 문제가 발생한다면 순서가 명시된 자료형(ex. list)과 정렬을 사용해야 합니다. 

다만 이 때 리스트의 remove는 최대(?) O(n)이고 이것이 for 문 안에서 rereserve_list의 길이만큼 반복되기 때문에 효율의 문제가 발생할 수 있습니다.

코테 코뽐(코드 뽐내기)용으론 그럴싸한데 실제 쓰기는 좀 애매합니다. 

def solution(n, lost, reserve):
    reserve_list = sorted(list(set(reserve) - set(lost)))
    lost_list = sorted(list(set(lost) - set(reserve)))
    for rev in reserve_list:
        front = rev - 1
        back = rev + 1
        if front in lost_list:
            lost_list.remove(front)
        elif back in lost_list:
            lost_list.remove(back)
    return n - len(lost_list)

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.05ms, 10.7MB)
테스트 8 〉	통과 (0.05ms, 10.7MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.05ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.8MB)
테스트 12 〉	통과 (0.04ms, 10.7MB)

(테스트는 모두 번호 순서대로 리스트가 주어졌으나, 명시된 조건은 아닙니다. 
테스트가 순서대로 주어지지 않는다면 모든 알고리듬에 소트가 필요해진다는 점도 생각할 필요가 있습니다.)

자바스크립트

function solution(n, lost, reserve) {
    let clothes = []
    for (let i = 0; i < n; i++) clothes.push(1)
    for (let each of lost) clothes[each - 1]--
    for (let each of reserve) clothes[each - 1]++
    for (let i = 0; i < clothes.length; i++) {
        if (clothes[i] == 0) {
            if (i > 0 & clothes[i - 1] > 1) {
                //clothes[i - 1]--
                clothes[i]++
            } else if (i < n -1 & clothes[i + 1] > 1) {
                clothes[i + 1]--
                clothes[i]++
            } else {
                n--
            }
        }
    }
    return n
}

자바

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        var clothes = new int[n];
        for (int i = 0; i < n; i++) clothes[i] = 1;
        for (int each : reserve) clothes[each - 1]++;
        for (int each : lost) clothes[each - 1]--;
        for (int i = 0; i < clothes.length; i++) {
            if (clothes[i] == 0) {
                if ((i - 1 >= 0) && (clothes[i - 1] == 2)) {
                    // clothes[i - 1]--;
                    clothes[i]++;
                } else if ((i + 1 < n) && (clothes[i + 1] == 2)) {
                    clothes[i + 1]--;
                    clothes[i]++;
                } else {
                    n--;
                }
            }
        }
        return n;
    }
}

코틀린

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        val clothes = IntArray(n){1}
        for (each in reserve) clothes[each - 1]++
        for (each in lost) clothes[each - 1]--
        var count = 0
        for (i in 0 until n) {
            if (clothes[i] == 0) {
                if (i - 1 >= 0 && clothes[i - 1] == 2) {
                    //clothes[i - 1]--;
                    clothes[i]++
                } else if (i + 1 < n && clothes[i + 1] == 2) {
                    clothes[i + 1]--
                    clothes[i]++
                } else {
                    count++
                }
            }
        }
        return n - count
    }
}

고

func solution(n int, lost []int, reserve []int) int {
    clothes := make([]int, n)
    for i := 0; i < n; i++ {
        clothes[i] = 1
    }
    for _, each := range lost {
        clothes[each-1]--
    }
    for _, each := range reserve {
        clothes[each-1]++
    }
    for i := 0; i < len(clothes); i++ {
        if clothes[i] == 0 {
            if i > 0 && clothes[i-1] > 1 {
                //clothes[i-1]--
                clothes[i]++
            } else if i < n-1 && clothes[i+1] > 1 {
                clothes[i+1]--
                clothes[i]++
            } else {
                n--
            }
        }
    }
    return n
}

C#

public class Solution
{
    public int solution(int n, int[] lost, int[] reserve)
    {
        int[] clothes = new int[n];
        for (int i = 0; i < n; i++)
            clothes[i] = 1;
        foreach (int i in lost)
            clothes[i - 1] -= 1;
        foreach (int i in reserve)
            clothes[i - 1] += 1;
        for (int i = 0; i < clothes.Length; i++)
        {
            if (clothes[i] == 0)
            {
                if ((i - 1 >= 0) && (clothes[i - 1] == 2))
                {
                    clothes[i - 1]--;
                    clothes[i]++;
                }
                else if ((i + 1 < n) && (clothes[i + 1] == 2))
                {
                    clothes[i + 1]--;
                    clothes[i]++;
                }
                else
                {
                    n--;
                }
            }
        }
        return n;
    }
}