2023-10-27(프로그래머스)

덧칠하기

문제 설명을 요약하자면 n = 벽의 길이, m = 칠하는 롤러의 길이, section = 칠해야 하는 범위, 반환값 = 최소한으로 모두 칠하는 횟수

---

내가 떠올린 것

section으로 주어지는 값의 첫번째 값을 시작으로 롤러의 길이(m)만큼 띄워서 그다음 값을 찾아보자

 

Python

def solution(n, m, section):
    answer = 0
    i = 1

    while i <= n:
        if i in section:
            i += m-1 # -1을 해주지 않으면 그 다음값까지 포함
            answer += 1
        i += 1

    return answer

처음에 이렇게 작성을 하였었는데 테스트케이스중 3개에서 시간초과가 발생해서 예전에 사용했던 딕셔너리를 사용하였다

 

↓

def solution(n, m, section):
    answer = 0
    i = 1
    section_map = {x: i for i, x in enumerate(section)}
    
    while i <= n:
        if i in section_map:
            i += m-1
            answer += 1
        i += 1

    return answer

딕셔너리를 사용해서 작성을 하였더니 바로 해결되었다

 

 

def solution(n, m, section):
    answer = 1
    prev = section[0]
    for sec in section:
        if sec - prev >= m: # m만큼의 롤러 길이 이상이 차이가 나면 한번의 페인트칠에 포함 되지 않는 경우
            prev = sec
            answer += 1

    return answer

다른 분이 푼 방법인데 이 방법도 간단해서 좋은 것 같다

 

 

JAVA

public static int solution(int n, int m, int[] section) {
        int answer = 0, a = 0;
        HashMap<Integer,Integer> section_HashMap = new HashMap<>();

        for(int i = 0 ; i < section.length ; i ++ ){
            section_HashMap.put(section[i],i);
        }

        while(a <= n){
            if (section_HashMap.get(a) != null){
                a += m - 1;
                answer ++;
            }
            a ++;
        }
        return answer;
    }

파이썬에서 딕셔너리를 사용했다면 java에서는 HashMap을 사용!

 

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

파이썬에서 다른분이 푸신 것을 이용해서 java로 풀어본 경우

 

---

※ 딕셔너리를 사용하는 주된 이유

→ 검색 연산을 빠르게 만들기 위해서!

→ 딕셔너리의 검색 연산은 평균적으로 O(1)의 시간 복잡도를 가지기 때문에 리스트나 다른 자료 구조보다 빠른 검색이 가능