https://school.programmers.co.kr/learn/courses/30/lessons/161989
class Solution {
public int solution(int n, int m, int[] section) {
int answer = 0;
int paint = 0; // 완료된 영역 담을 수
for(int i : section) {
if(i > paint) {
paint = i + m - 1;
answer++;
} else continue;
}
return answer;
}
}
너무 어렵게 생각하면서 긴시간 헤매고헤매다가,, 쉽게 풀 수 있는 문제임을 깨닫고 고쳐서 맞았다ㅠㅠㅠ
처음 생각했던건 전체 칸과 길이가 같은 boolean 배열에 칠해야하는 칸은 true로 바꿔놓고 시작 -> 앞에서부터 검사하다가 true 만나면 칠할 수 있는 길이만큼 false로 바꿈 -> 여전히 true인 배열이 남아있다면 뒤에서부터 검사하다가 true 만나면 칠할 수 있는 길이만큼 false로 바꿈 -> 여전히 true인 배열 남아있다면 앞에서부터 -> 다시 뒤에서 반복반복
지금 dfs를 공부하느라 boolean 배열에 넣어서 체크하면 좋겠단 생각이 들기도 했고 벽이 엄청엄청 길다면 양쪽에서 처리하고 중간으로 다가오며 답을 찾는게 제일 나은 답일거라고 생각하기도 했다 그리고 앞에서부터 칠해가면 벽 길이를 넘어가는 경우도 생기지않나? 생각하기도했고,,
너무 어렵게 생각하지말고 최대한 쉽게 풀 수 있는 방법을 찾는 연습도 해야될거같다 시간만 엄청 날렸다ㅠㅠ
아무튼 최종적으로 푼 방법은 그냥 앞에서부터 처리하면 되는거였다 처음 만난 부분부터 칠해줄 수 있는 길이만큼 칠해주고 넘어가서 아직 안칠해진 부분 칠하면 되고 그거를 반복하면된다!
예를 들어 2에서 4만큼 칠했다면 2,3,4,5 해서 5까지 칠해지는거고
칸 숫자 기준으로 "시작칸 + 칠하는 길이 - 1" 까지 완료 -> 완료된 다음(시작칸+칠하는길이)부터 다시 칠하기!
'코딩테스트-알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Lv.1] 완주하지 못한 선수 (1) | 2024.01.12 |
---|---|
[프로그래머스/Lv.0] 정수를 나선형으로 배치하기 (1) | 2024.01.11 |
[프로그래머스/Lv.1] 카드 뭉치 (0) | 2023.12.26 |
[프로그래머스/Lv.1] 과일 장수 (0) | 2023.12.25 |
[프로그래머스/Lv.1] 명예의 전당 (1) (2) | 2023.12.22 |