プログラマーLv 1.スポーツウェア

15151 ワード
algorithm プログラマ テキストリンク

質問する


貪欲な問題
https://programmers.co.kr/learn/courses/30/lessons/42862

に近づく

  • 学生数(n)+2個配列.最初はすべての学生が運動服を持っていると仮定し、1の値段があった.
    • stu = [1] * (n+2)
  • lossに相当するインデックスの学生は、学生配列において−1である.
  • reserveに相当するindexの学生は+1をします.
    • for i in lost:
	stu[i] -= 1
for i in reserve:
        stu[i] += 1
  • 前の学生は後ろの学生に運動服を借り、後ろの学生は前の学生に運動服を借ります.
    for i in range(1,len(stu)):
        if stu[i] == 0 and stu[i-1] == 2 :
            stu[i-1] -= 1
            stu[i] += 1
        elif stu[i] == 0 and stu[i+1] == 2 :
            stu[i+1] -= 1
            stu[i] += 1
    したがって,先頭と先頭のindexを除いて,初期配列ではゼロ値以外の数が答えである.

    • コード#コード#


    python

    def solution(n, lost, reserve):
    stu = [1]*(n+2)
    for i in lost:
        stu[i] -= 1
    for i in reserve:
        stu[i] += 1
            
    for i in range(1,len(stu)):
        if stu[i] == 0 and stu[i-1] == 2 :
            stu[i-1] -= 1
            stu[i] += 1
        elif stu[i] == 0 and stu[i+1] == 2 :
            stu[i+1] -= 1
            stu[i] += 1
    
    result = [x for x in stu[1:-1] if x!=0]
    return len(result)

    js

    
function solution(n, lost, reserve) {
    let stu = [];
    for(let i=0; i<n+2; i++){
        stu.push(1);
    }
    for(let i=0; i<lost.length; i++){
        stu[lost[i]] -= 1;
    }
    for(let i=0; i<reserve.length; i++){
        stu[reserve[i]] += 1;
    }
    
    for(let i=1; i<stu.length-1; i++){
        if(stu[i]==0 && stu[i-1]==2){
            stu[i-1] -= 1;
            stu[i] += 1;
        }else if(stu[i]==0 && stu[i+1]==2){
            stu[i+1] -= 1;
            stu[i] += 1;
        }
    }
    
    let result = stu.slice(1, n+1);
    return result.filter(x => x!==0).length;
    
}
    0812 TIL
    重複文付きファイルI/O