[Programmers : Java] - 덧칠하기

문제 설명

 

---

문제 풀이 1차 (오답)

접근부터 틀린 풀이

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        HashMap<Integer, Integer> sCheck = new HashMap<Integer, Integer>();
        // HashMap 초기화
        for (int i = 1; i <= n; i++)
		{
        	sCheck.put(i, 1);
        	for (int j=0; j<section.length; j++)
				if(section[j] == i) sCheck.put(i, null);
		}
        
        // HashMap 에서 null 인 부분부터 m의 크기 만큼 null -> 1로 변경
        for (int i = 1; i <= (n-m)+1; i++)
		{
        	int tmp = 0;
        	for (int j = 0; j<m; j++)
			{
				if((sCheck.get(i+j) == null) && ((i+j)<=n))
				{
					sCheck.put(i+j, 1);
					tmp+=1;
				}
			}
			if(tmp>0) answer+=1;
			
			// HashMap 나머지 뒷 부분이 이미 색칠 되어 있는 상태(==완료된 상태)라면
			// 종료
			int emptyChk = 0;
			for (int j = i+1; j <= n; j++)
			{
				if(sCheck.get(j)==null) emptyChk += 1;
			}
			if(emptyChk==0) break;
		}
        
        return answer;
    }
}

 

생각 할 것이 많아지니 그 만큼 반복문의 사용도 많아지게 됨...

복잡도가 늘어날 걸 알아서 되도록이면 for문 사용을 줄이고 싶은데 생각처럼 안된다...ㅠ

계속 제출 통과가 되지 않아서 결국 블로그의 도움을 받기로...

 

---

문제풀이 2차

다른 블로그 글 찾아보곤 부끄러웠다....

사고력이 부족한걸까...

결국은 section[0]을 시작점으로 m만큼의 길이 안에 section에 있는 모든 숫자가 다 들어있는지 확인하면 되는 문제였다.

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 1;
        int start = section[0];

        for (int i = 0; i < section.length; i++)
        {
            if(start + (m-1) < section[i])
            {
                answer+= 1;
                start = section[i];
            }
        }
        return answer;
    }
}