코딩 테스트/Level 1
33. 체육복
컴닥
2019. 10. 31. 23:28
반응형
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;
}
}반응형