[프로그래머스] 15 : 덧칠하기 | 기사단원의 무기 | 로또의 최고 순위와 최저 순위

서예진·2024년 1월 29일
0
post-custom-banner

목차

▸ 덧칠하기
▸ 기사단원의 무기
▸ 로또의 최고 순위와 최저 순위


💡덧칠하기 : Lv.1

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습문제 > 덧칠하기


▼ 내 풀이

  • 우선, replace 메서드를 통해 접근했다. n 만큼의 리스트에서 칠해야할 곳을 1로 표시하고 칠했으면 0으로 바꾸는 방법을 생각했다.
  • 여기서 m은 replace 메서드의 반복 횟수가 된다.
  • 이때, 초기에 paintList를 선언했으므로 replace 메서드가 아니라 set 메서드를 사용했다.
[오답 코드]
import java.util.List;
import java.util.ArrayList;


class Solution {
    public List<Integer> solution(int n, int m, int[] section) {
        int answer = 0;
        List<Integer> paintList = new ArrayList<>();
        
        //초기 paintList 세팅
        for(int i = 0; i < n; i++){
            paintList.add(0);
        }
        
        //칠해야 할 부분 1로 처리하기
        for(int i : section){
            paintList.set(i-1, 1); 
        }
        
        //칠한 부분 0으로 처리하기
        for(int i = 0; i < paintList.size(); i++){
            if(paintList.get(i) == 1){
                for(int j = i; j < i + m; j++){
                    paintList.set(j, 0);
                    answer++;
                }
            }
        }
        
        
        return paintList;
    }
}
  • ❗️주의: 페인트칠은 무조건 m만큼의 페인트칠을 해야한다. 위에서의 방법대로 코드를 작성하니 당연히 index 관련 오류가 떴다.
  • 입출력 예에서 2번부터가 아니라 3번부터 페인트칠한 것도 주의와 관련된 이유였다.
  • 우선, 페인트칠의 시작점을 정해야 했다.
[수정 코드]
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int startpoint = 0; 
        List<Integer> paintList = new ArrayList<>();
        
        //초기 paintList 세팅
        for(int i = 0; i < n; i++){
            paintList.add(0);
        }
        
        //칠해야 할 부분 1로 처리하기 및 페인트칠 시작점 구하기
        for(int i : section){
            paintList.set(i-1, 1); 
            if(i+m-1 <= n){
                startpoint = i-1;
            }
        }
        
        //페인트칠 0으로 처리하기
        for(int i = startpoint; i < startpoint + m; i++){
            paintList.set(i, 0); 
        }
        answer++;
        
        //페인트칠 이전에 1이 남아있는지 확인하고 남아있으면 페인트칠
        for(int i = 0 ; i < startpoint; i++){
            if(paintList.get(i)==1){
                for(int j = i; j < i+m; j++){
                    paintList.set(j, 0);
                }
                answer++;
            }
        }
        
        return answer;
    }
}
  • 위와 같이 수정해서 제출했지만 7개의 테스트에서 실패 결과를 얻었다. 내가 생각했을 때 위 코드의 문제점은 모든 경우에 일반화하기에 부족한 것 같았다. 문제가 페인트칠하는 것이 문제라고 해서 set 메서드를 활용하여 진짜 페인트칠하는 것처럼 로직을 세울 필요가 없었다.
  • 우선, 페인트 시작점과 끝점을 구한 후, 끝점 보다 큰 수가 아직 section에 있으면 페인트할 구역이 남아있다는 것과 같으므로 아래와 같이 작성했다.
[통과 코드]
class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int painted = 0;
        
        for(int point : section){
            if(point > painted){
                answer++;
                painted = point + m -1;
            }
        }
        return answer;
    }
}

❗️문제의 처리방법과 유사한 메서드를 실행하지 않아도 된다. 쉽게 생각하기!


💡기사단원의 무기 : Lv.1

▼ 문제

출처: 코딩테스트 연습 > 연습문제> 기사단원의 무기

▼ 내 풀이

  • 우선, 1번 부터 number까지 각 숫자의 약수의 수를 구하고 이 수가 만약 limit보다 클 경우, power로 바꾸는 과정을 코드로 작성했다.
  • for문을 활용했고 각 숫자의 공격력을 나타내는 수를 저장하기 위해 리스트를 활용했다.
import java.util.List;
import java.util.ArrayList;


class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= number; i++){
            //약수의 수 구하기
            int count = 0; 
            for(int j = 1; j <= i; j++){
                if(i%j==0){
                    count++;
                }
            }
            list.add(count);
        }
        
        //limit 넘은 숫자 처리하기 와 합 구하기
        for(int i = 0; i < list.size(); i++){
            if(list.get(i) > limit){
                list.set(i, power);
            }
            answer += list.get(i);
        }
        
        return answer;
    }
}
  • 위와 같이 코드를 작성해서 제출했지만 9개의 테스트에서 시간초과로 실패가 떴다. 리스트가 시간이 오래걸리는 것 같아서 배열로 바꿨지만 시간초과 결과는 똑같았다.
  • 원인을 찾아보니 약수를 구하는 부분에서 모든 수를 하나하나 탐색하기 때문에 시간이 많이 걸리는 것을 알 수 있다. 따라서 약수의 수를 구하는 최적의 방법을 찾아서 참고했다.

    ❗️약수를 구하는 최적의 방법 (시간 단축)
    ✓ number의 약수가 1일 때, 그 짝으로 다른 약수는 number/1이다.
    ✓ number의 약수가 i일 때, 다른 약수는 number/i가 된다.
    ✓ 약수의 수가 홀수인 경우는 제곱근이 포함되어있는 경우다.

    	int number = 199999999;
    	int count = 0;
    	for(int i = 1; i*i <= number; i++){
    		if(i * i == number){
        		count ++;
        	} else if(number % i == 0){
        		count += 2;
        	}
[수정 코드]
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int[] array = new int[number];
        
        for(int i = 1; i <= number; i++){
            //약수의 수 구하기
            int count = 0; 
            for(int j = 1; j * j <= i; j++){
                if(j * j == i){
                    count++;
                } else if(i % j == 0){
                    count += 2;
                }
            }
            array[i-1] = count;
        }
        
        //limit 넘은 숫자 처리하기 와 합 구하기
        for(int i = 0; i < array.length; i++){
            if(array[i] > limit){
                array[i] = power;
            }
            answer += array[i];
        }
        
        return answer;
    }
}
  • 위와 같이 수정한 결과 시간이 확연하게 줄어든 것을 확인할 수 있었다.

💡로또의 최고 순위와 최저 순위 : Lv.1

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 로또의 최고 순위와 최저 순위

▼ 내 풀이

  • 우선, 0을 제외하고 당첨 번호와 일치한 숫자의 수, 0의 수를 센다.
  • 최고 순위는 0이 모두 원래의 당첨 번호인 경우이며 최저 순위는 0이 모두 당첨번호가 아닌 경우이다.
  • 따라서, 최고 순위일 때의 일치 숫자의 수에는 0의 수를 더하고 최저 순위는 더하지 않는다.
  • 마지막으로 해당 숫자의 수에 따라 순위를 매기고 배열에 넣어준다.
class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        int cnt = 0;
        int zerocnt = 0;
        
        //0을 제외하고 당첨 번호와 일치하는 숫자 세기
        for(int number1 : lottos){
            for(int number2 : win_nums){
                if(number1 == number2){
                    cnt++;
                }
            }
            if(number1 == 0){
                zerocnt++;
            }
        }
        
        //최고순위는 0이 원래의 당첨 번호인 경우, 최저순위는 0이 다 당첨 번호가 아닌 경우
        int highcnt = cnt + zerocnt;
        int lowcnt = cnt;
        
        
        int highrank = 0;
        int lowrank = 0;
        //순위매기기
        if(highcnt == 6){
            highrank = 1;
        } else if(highcnt ==5){
            highrank = 2;
        } else if(highcnt ==4){
            highrank = 3;
        } else if(highcnt ==3){
            highrank = 4;
        } else if (highcnt ==2){
            highrank = 5;
        } else {
            highrank = 6;
        }
        
        if(lowcnt == 6){
            lowrank = 1;
        } else if(lowcnt ==5){
            lowrank = 2;
        } else if(lowcnt ==4){
            lowrank = 3;
        } else if(lowcnt ==3){
            lowrank = 4;
        } else if (lowcnt ==2){
            lowrank = 5;
        } else {
            lowrank = 6;
        }
        
        answer[0] = highrank;
        answer[1] = lowrank;
        return answer;
    }
}
profile
안녕하세요
post-custom-banner

0개의 댓글