2022 카카오 신입 공채 1차 온라인 코딩테스트 (누적합)

https://school.programmers.co.kr/learn/courses/30/lessons/92334

프로그래머스

신고 결과 받기

 

풀이 (90)

한 명이 여러번 신고해도 1번으로 간주 => Set 객체 사용

신고자에게 반환할 때는 순서를 유지함 => Map 객체 사용

function solution(id_list, report, k) {
    // map으로 (신고한 사람, 신고당한 사람 set) 만들기
    const reportUsers = new Map();
    for (let i=0; i<id_list.length; i++) {
        reportUsers.set(id_list[i],new Set())
    }
    report.forEach(item => {
        const [go,taken] = item.split(" ")
        reportUsers.get(go).add(taken)
    })
    
    // 신고당한 횟수 구하기
    const reportCount = {};
    for (let report of reportUsers.entries()) {
        for (let taken of report[1]) {
            reportCount[taken] = (reportCount[taken] || 0) +1
        }
    }
    const overKUsers = (Object.entries (reportCount).map(item=>{
        if (item[1]>=k) {
           return item[0]
       }
    }).filter(Boolean))
  
    // 결과 count하여 반환하기
    const result = Array(id_list.length).fill(0)
    let index = 0
    reportUsers.forEach((reportUser,value) => {
        reportUser.forEach(item => {
            if (overKUsers.includes(item)) {
                result[index]++
            }
        })
        index++
    })

    return result    
}

---

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

k진수에서 소수 개수 구하기

 

풀이 (5)

//     0P0처럼 소수 양쪽에 0이 있는 경우 (중간)
//     처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 (처음) 
//     0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 (마지막)
//     P처럼 소수 양쪽에 아무것도 없는 경우 (한자리)

 

0을 기준으로 나눈 숫자 배열에 대하여 prime인지 판별하면 됩니다.

function solution(n, k) {
    const targets = n.toString(k).split("0").filter(Boolean)
    
    const checkPrime = (number) => {
        if (number == 2) return 1
        if (number == 1) return 0
        
        for (let i=3; i*i<=number;i+=2) {
            if (number%i==0) return 0
        }
        return 1
    }
    
    let result = 0
    for (let target of targets) {
       if (checkPrime(target))  result++
    }
    return result
}

---

https://school.programmers.co.kr/learn/courses/30/lessons/92341

프로그래머스

주차 요금 계산 

 

풀이 (15)

입차한 분(minute) 만큼 마이너스(-)를 해주고,

출차한 분(minute)만큼 플러스(+)를 해준다.

출차한 내역이 없다면 23:59을 분으로 환산한 값을 플러스(+) 해주면 주차 시간이 결정된다.

 

그리고 차량 번호 순으로 정렬을 해준 뒤에

차량별 주차시간을 공식에 맞게 대입하여 결과를 반환한다.

 

function solution(fees, records) {
    const [base, fee, unit, plus] = fees
    const MAXIMUM = 60*24 - 1
    
    const cars = {}
    
    for (const record of records) {
        const [time,number,move] = record.split(" ")
        let [hour, minute] = time.split(":").map(Number)
        minute += hour*60
        if (move === "IN") {
            cars[number] = (cars[number]||0) -minute        
        }
        if (move === 'OUT') {
            cars[number] += minute
        }
    }
    
    const endOfDay = Object.entries(cars).sort((a,b) => a[0]-b[0])
    const result = []
    for (const car of endOfDay) {
        if (car[1]<=0) {
            car[1] += MAXIMUM
        }
        const baseTime = (car[1] - base)
        const total = fee + Math.ceil(baseTime / unit) * plus
        baseTime <= 0 ? result.push(fee) : result.push(total)  
    }
    return result
}

---

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

양궁 대회

 

조건
  // 라이언에게 불리한 규칙
  // 1. 유리한 사람(어피치)이 n발 다 쏘고 불리한 사람(라이언)이 n발을 쏜다
  // 2. 더 많은 화살을 k점에 맞힌 선수가 k점을 가져가는데, a=b이면 유리한 사람이 k점을 가져간다.
  // 3. 모든 과녁 점수에 대하여 최종 점수 계산하는데, 최종 점수가 동일할 경우 유리한 사람이 우승자
  // 4. 라이언이 어피치를 가장 큰 점수 차로 이기기 위해 어느 과녁 점수에 맞혀야 하는지 구하려 한다.

  // 화살 개수: n, 유리한 사람 점수: info
  // 무조건 지거나 비기는 경우 -1 반환

 

풀이 (***)

가장 큰 점수 차를 구해야 하니 완전탐색일 것이다. =>

n발 이하로 발사하는 경우에 대해 모든 점수 케이스를 구한다. =>

점수의 차이가 가장 큰 배열을 구한다. =>

동일한 점수 차이의 배열이 여러개일 경우 가장 낮은 점수를 많이 맞힌 횟수를 반환한다.

 

function solution(n, info) {
  // 모든 score 배열을 구하기
  const scores = [];

  const backtrack = (i, array, n, shotCount) => {
    // 발사 횟수의 합이 n보다 클 경우엔 더 이상 검사할 필요 없으므로 선리턴
    if (shotCount > n) {
      return;
    }
    // n회의 발사가 끝났다면 배열에 추가
    if (i === array.length) {
      if (shotCount === n) {
        scores.push([...array]);
      }
      return;
    }

    // 모든 점수에 대해 발사
    for (let j = 0; j <= n; j++) {
      array[i] = j;
      backtrack(i + 1, array, n, shotCount + j);
      array[i] = 0;
    }
  };

  backtrack(0, new Array(11).fill(0), n, 0);

  // 가장 차이가 큰 배열 모으기
  let bigScores = [];
  let maxDifference = -1;

  scores.forEach((array) => {
    let good = 0;
    let bad = 0;

    // 차이 구하기
    array.forEach((score, index) => {
      if (score > info[index]) {
        bad += 10 - index;
      } else {
        if (info[index]) {
          good += 10 - index;
        }
      }
    });

    const biggerDifference = Math.max(maxDifference, bad - good);
    if (maxDifference !== biggerDifference) {
      bigScores = [];
      maxDifference = biggerDifference;
    }

    if (bad - good === maxDifference) {
      bigScores.push(array);
    }
  });

  // 가장 차이가 큰 배열이 여러개일 경우 가장 낮은 점수를 많이 맞힌 score 반환하기
  if (bigScores.length > 1) {
    let result;
    let maximum = -1;

	// 요소의 뒤에서부터 검사
    for (let i = info.length - 1; i > 0; i--) {
      for (let j = 0; j < bigScores.length; j++) {
        const score = bigScores[j][i];
        const bigScore = Math.max(score, maximum);
        // 0점을 맞춘 배열이 1,2,3... 과 같이 여러개가 있는 경우, 이 중 가장 큰 수의 배열을 반환
        if (score !== 0) {
          if (maximum < bigScore) {
            result = bigScores[j];
            maximum = bigScore;
          }
        }
      }
      if (result) break;
    }

    return result;
  }

  return maxDifference <= 0 ? [-1] : bigScores[0];
}

solution(9, [0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1]);

---

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

파괴되지 않은 물건

 

풀이 (***)

(x1, y1) 좌표부터 (x2, y2) 좌표 범위 내에 존재하는 모든 배열에 n의 값을 더하는 누적합을 이용한다.

https://eunchanee.tistory.com/635

(프로그래머스 KAKAO JS)파괴되지 않은 건물

---

누적합 동작 원리 

 

(1,0), (3,1), degree:2

  [ 0, 0, 0, 0, 0, 0 ],
  [ 2, 0, -2, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ -2, 0, 2, 0, 0, 0 ]

 

(1, 0), (3+1, 1+1) 왼쪽 위, 오른쪽 아래 +2

(1, 3+1), (3+1, 1+1) 오른쪽 위, 왼쪽 아래 -2

 

가로로 누적합 진행

  [ 0, 0, 0, 0, 0, 0 ],
  [ 2, 2, 0, 0, 0, 0 ], -2 좌표에서 (2) + (-2) = 0이 되면서 이후의 배열부터는 0 이 유지된다.
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ -2, 0, 2, 0, 0, 0 ]

 

세로로 누적합 진행

  [ 0, 0, 0, 0, 0, 0 ],
  [ 2, 2, 0, 0, 0, 0 ],
  [ 2, 2, 0, 0, 0, 0 ],
  [ 2, 2, 0, 0, 0, 0 ],
  [ -2, 0, 2, 0, 0, 0 ]

---

(0,0), (3,4), degree:-4

  [ -4, 0, 0, 0, 0, 4 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 4, 0, 0, 0, 0, -4 ]

 

(0, 0), (3+1, 4+1) 왼쪽 위, 오른쪽 아래 +(-4)

(0, 3+1), (3+1, 4+1) 오른쪽 위, 왼쪽 아래 -(-4)

 

가로로 누적합 진행

  [ -4, -4, -4, -4, -4, 4 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0 ],
  [ 4, 0, 0, 0, 0, -4 ]

세로로 누적합 진행

  [ -4, -4, -4, -4, -4, 4 ],
  [ -4, -4, -4, -4, -4, 0 ],
  [ -4, -4, -4, -4, -4, 0 ],
  [ -4, -4, -4, -4, -4, 0 ],
  [ 4, 0, 0, 0, 0, -4 ]

---

function solution(board, skill) {
  const row = board.length;
  const column = board[0].length;
  const cumulated = Array.from({ length: row + 1 }, () => Array(column + 1).fill(0));

  skill.slice(2, 3).forEach((item) => {
    const [type, r1, c1, r2, c2, degree] = item;
    console.log(`(${r1},${c1}), (${r2},${c2}), degree:${degree}`);
    const role = type === 1 ? -1 : 1;

    cumulated[r1][c1] += role * degree; // 왼쪽 위 +
    cumulated[r1][c2 + 1] -= role * degree; // 오른쪽 위 -
    cumulated[r2 + 1][c1] -= role * degree; // 왼쪽 아래 -
    cumulated[r2 + 1][c2 + 1] += role * degree; // 오른쪽 아래 +
  });

  // row에 대하여 누적합
  for (let i = 0; i < row; i++) {
    let sum = 0;

    for (let j = 0; j < column; j++) {
      sum += cumulated[i][j];
      cumulated[i][j] = sum;
    }
  }

  // column에 대하여 누적합
  for (let i = 0; i < column; i++) {
    let sum = 0;

    for (let j = 0; j < row; j++) {
      sum += cumulated[j][i];
      cumulated[j][i] = sum;
    }
  }

  // board 배열과 누적합 배열을 합하기
  let answer = 0;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      board[i][j] += cumulated[i][j];

      if (board[i][j] > 0) {
        answer++;
      }
    }
  }
  return answer
}