목차
▸ 덧칠하기
▸ 기사단원의 무기
▸ 로또의 최고 순위와 최저 순위
💡덧칠하기 : 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;
}
}
안녕하세요