문제
https://school.programmers.co.kr/learn/courses/30/lessons/92344
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
정확성만 본다면 단순히 브루트포스로 풀 수 있는 문제이나, 시간을 따졌을때 그렇게 풀 수 없는 문제이다.
이 문제의 핵심은 '누적합' 인데, 나도 전혀 감을 못잡아서 풀이를 보고 알게 되었다. 개인적으로는 이런 문제를 접해보지 않고, 관련 테크닉을 모른다면 못푸는 문제가 아닐까 생각했다. (구현보다는 스킬, 테크닉 의존적인 문제 아닐까..)
이 누적합 테크닉은 1차원 배열을 먼저 예시로 들고 이해하는게 빠르다.
[1, 2, 3, 4, 5] 에서 인덱스 0에서 3까지 -2를 빼준다고 생각해보자.
일반적으로는 각 인덱스에 접근해서 -2씩 연산을 해줄 것이다.
그러나 누적합을 사용하면 이 과정을 더 간단하게 수행할 수 있다.
우선 배열을 원본 배열과 같은 길이로 선언한 후에 0으로 모두 채워준다 -> [0, 0, 0, 0, 0]
다음 시작 위치인 0에 -2 를 설정하고, 끝 위치 + 1 인 4에 +2를 설정한다. -> [-2, 0, 0, 0, 2]
(이 때 -2는 우리가 변화를 줄 값이고, +2는 부호만 바꾼 값이다.)
이후 만들어진 배열을 앞에서부터 누적합을 구한다. [-2, -2, -2, -2, 0]
최종적으로 원본 배열과 더해주면 된다.
[1, 2, 3, 4, 5] + [-2, -2, -2, -2, 0] => [-1, 0, 1, 2, 5]
위와 같이 조건이 하나인 경우에는 시간 복잡도가 똑같이 느껴질 수 있지만 조건이 여러개면 조건 하나를 설정하는데 O(1)에 수행이 가능하기 때문에 압도적인 속도 차이를 보인다. 나도 이 부분이 헷갈려서 직접 작성해봤다.
위에서보면
- 1. (1) 첫번째 누적합 배열을 만들기 위해서 0의 위치에 -3, 그리고 끝 위치 +1 인 4에 +3을 해주었다.
- 2. (1)번에서 만들어진 배열에 2번 조건을 똑같이 적용한다.
3의 위치에 -1, 5의 위치에 +1 (단 여기서 배열 길이가 4가 끝이므로 뒷부분 처리는 따로 필요없다.) - 3. (2)번에서 만들어진 결과 배열에서 다시 3번 조건을 적용한다.
1의 위치에 +2, 3의 위치에 -2
이렇게 보면 조건 마다 인덱스에 접근해서 값만 설정해주면 끝인것을 확인할 수 있다. 그리고 마지막에 원본 배열과 더해주기만 하면 원하는 결과를 얻을 수 있다. (만약 브루트포스식으로 했다면 15번이나 접근해서 값을 변경했어야 할 것이다.)
이 원리를 이해하면 2차원도 똑같이 적용할 수 있다.
(0, 0) ~ (2, 2) 까지 2를 더해준다고 생각해보자.
각각을 1차원 배열로 생각하면
2 0 0 -2
2 0 0 -2
2 0 0 -2
와 같이 표현할 수 있다.
위의 배열을 열로 따져보면 ,
첫 번째 열에서 0번째 요소부터 2번째 요소까지의 n만큼의 변화로 같고,
마지막 열에서 0번째 요소부터 2번째 요소까지 -n만큼의 변화로 같다.
변화가 같다는 것은 우리가 이전에 세워놓은 누적합 원리를 사용할 수 있다는 것이고, 아래와 같이 표현할 수 있다.
2 0 0 -2
0 0 0 0
0 0 0 0
-2 0 0 2
이 원리를 적용해서 문제를 풀이하면 시간내에 풀이가 가능하다. 아래는 카카오 공식해설인데 참조해보자.
https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/
2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설
지난 2021년 9월 11일 토요일 오후 2시부터 7시까지 5시간 동안 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, JavaScript, K
tech.kakao.com
코드
import java.util.*;
class Solution {
public int solution(int[][] board, int[][] skills) {
// board와 같은 크기의 2차원 배열 선언
int answer = 0;
int r = board.length;
int c = board[0].length;
int[][] preSum = new int[r+1][c+1];
for(int[] skill : skills){
int type = skill[0];
int r1 = skill[1];
int c1 = skill[2];
int r2 = skill[3]+1;
int c2 = skill[4]+1;
int degree = skill[5] * (type == 1 ? -1 : 1);
preSum[r1][c1] += degree;
preSum[r1][c2] -= degree;
preSum[r2][c1] -= degree;
preSum[r2][c2] += degree;
}
for(int i=0; i<r; i++){
for(int j=1; j<c; j++){
preSum[i][j] += preSum[i][j-1];
}
}
for(int i=0; i<c; i++){
for(int j=1; j<r; j++){
preSum[j][i] += preSum[j-1][i];
}
}
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
if(board[i][j] + preSum[i][j] > 0) answer +=1;
}
}
return answer;
}
}
후기
누적합 개념은 생각도 못했다. 생각했더라도 전혀 관계가 있을거라고 생각이 닿지 않았을 거 같다. 부딪히면서 좋은 테크닉하나 얻었다고 생각하자. (코테에서 만났으면 진짜 죽도 못쓰고 털렸을거다)
'프로그래머스' 카테고리의 다른 글
LV2 괄호 회전하기 (1) | 2023.09.19 |
---|---|
LV3 기지국 설치 (0) | 2023.09.10 |
LV3 [KAKAO] [1차] 셔틀버스 (0) | 2023.09.01 |
LV2 [KAKAO] 단체 사진 찍기 (0) | 2023.08.28 |
LV3 [KAKAO] 합승 택시 요금 (0) | 2023.08.24 |