티스토리 뷰
1️⃣ 덧칠하기
문제 설명
어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.
넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.
정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.
제한사항
- 1 ≤ m ≤ n ≤ 100,000
- 1 ≤ section의 길이 ≤ n
- 1 ≤ section의 원소 ≤ n
- section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
- section에서 같은 원소가 두 번 이상 나타나지 않습니다.
- section의 원소는 오름차순으로 정렬되어 있습니다.
입출력 예
| n | m | section | result |
| 8 | 4 | [2, 3, 6] | 2 |
| 5 | 4 | [1, 3] | 1 |
| 4 | 1 | [1, 2, 3, 4] | 4 |
입출력 예 #1
- 예제 1번은 2, 3, 6번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있습니다. 처음에 3, 4, 5, 6번 영역에 페인트칠을 하면 칠해야 할 곳으로 2번 구역만 남고 1, 2, 3, 4번 구역에 페인트칠을 하면 2번 만에 다시 칠해야 할 곳에 모두 페인트칠을 할 수 있습니다.2번보다 적은 횟수로 2, 3, 6번 영역에 페인트를 덧칠하는 방법은 없습니다. 따라서 최소 횟수인 2를 return 합니다.
입출력 예 #2
- 예제 2번은 1, 3번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있고 1, 2, 3, 4번 영역에 페인트칠을 하면 한 번에 1, 3번 영역을 모두 칠할 수 있습니다.따라서 최소 횟수인 1을 return 합니다.
입출력 예 #3
- 예제 3번은 모든 구역에 페인트칠을 해야 합니다. 롤러의 길이가 1미터이므로 한 번에 한 구역밖에 칠할 수 없습니다. 구역이 4개이므로 각 구역을 한 번씩만 칠하는 4번이 최소 횟수가 됩니다.따라서 4를 return 합니다.
💻 나의 풀이
class Solution {
public int solution(int n, int m, int[] section) {
int answer = 1;
int start = section[0];
int end = section[0] + (m-1);
for(int i : section) {
if(i>=start && i<=end) continue; // start~end 사이에 속하면 계속
else { // 속하지 않는 경우 -> 범위를 변경해주고, 횟수answer 1증가
start = i;
end = i+(m-1);
answer++;
}
}
return answer;
}
}
다시 페인트칠을 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section의 모든 원소가 주어진 시작~끝 범위 안에 속해있어야 한다고 생각했습니다. 속하지 않으면 한번 혹은 n번 더 칠해야하는 것이므로 횟수를 증가시켜주고, 범위를 재지정해주어야 합니다.
적어도 한 번 이상은 무조건 칠하니까 answer를 1로 초기화 시켜주고
시작점start와 끝점end를 초기화 시켜줬습니다.
(m-1)인 이유는? 인덱스는 0부터 시작하기 때문입니다.
예를 들어, 길이 m이 3이라면 연속된 3개의 요소를 선택해야 하므로 시작점에서 2번째(index 기준)까지의 거리를 더해주어야 합니다.
section을 순회하면서 현재 원소 i가 start와 end 사이에 속한다면 다음 요소로 이동합니다.
그렇지않다면 start를 현재 원소로 재지정하고 end도 그에 맞게 재지정 해줍니다. 더불어 횟수는 1 증가 시켜야겠죠!
🔍 다른 사람의 풀이
class Solution {
public int solution(int n, int m, int[] section) {
int roller = section[0];
int cnt = 1;
for(int i = 1; i < section.length; i++) {
if(roller + m - 1 < section[i]) {
cnt++;
roller = section[i];
}
}
return cnt;
}
}- roller 변수는 현재까지 선택한 구간의 끝 지점을 나타냅니다. 초기에는 배열의 첫 번째 요소로 초기화됩니다.
- cnt 변수는 최소 횟수를 나타냅니다. 초기에는 1로 시작합니다. (첫 번째 구간은 이미 선택된 상태)
- 배열 section을 순회하면서 각 요소를 확인합니다.
- 만약 roller + m - 1이 현재 요소보다 작다면, 현재 요소를 구간의 끝으로 설정하고, 횟수 cnt를 1 증가시킵니다.
- 이렇게 하면 현재 요소를 시작으로 하는 길이 m인 구간을 선택할 수 있습니다.
- 모든 요소를 확인한 후에는 최소 횟수로 모든 길이 m인 구간을 포함하기 위해 필요한 횟수가 cnt에 저장됩니다.
이렇게 하면 end 변수가 따로 필요 없습니다!
2️⃣ 실패율
문제 설명
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.
- 실패율은 다음과 같이 정의한다.
- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
제한사항
- 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
- stages의 길이는 1 이상 200,000 이하이다.
- stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
- 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
- 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
입출력 예
| N | stages | result |
| 5 | [2,1,2,6,2,4,3,3] | [3,4,2,1,5] |
| 4 | [4,4,4,4,4] | [4,1,2,3] |
입출력 예 #1
1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.
- 1 번 스테이지 실패율 : 1/8
2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.
- 2 번 스테이지 실패율 : 3/7
마찬가지로 나머지 스테이지의 실패율은 다음과 같다.
- 3 번 스테이지 실패율 : 2/4
- 4번 스테이지 실패율 : 1/2
- 5번 스테이지 실패율 : 0/1
각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.
- [3,4,2,1,5]
입출력 예 #2
모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.
- [4,1,2,3]
🔍 다른 사람의 풀이
import java.util.*;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
int noclear=0; // 해당 스테이지를 클리어하지 못한 사용자 수
int player=stages.length; // 초기 전체 사용자 수
Map<Integer, Double> stagefail = new HashMap<Integer, Double>(); // key:스테이지 번호, value:실패율
// 실패율 구하기
// 각 스테이지의 실패율을 계산. i : 현재 스테이지 번호
for(int i=1; i<=N; i++){
// stages 배열을 순회하며 각 사용자가 도전한 스테이지를 확인
for(int s : stages){
if(s==i) noclear++;
}
// 현재 스테이지에 도전한 사용자가 없는 경우 -> 실패율은 0.0
if(player==0) {
stagefail.put(i,0.0);
} else {
stagefail.put(i,(double)noclear/player); // 그렇지 않으면 실패율 계산 후 저장
player -= noclear; // 남은 전체 사용자 갱신해주기 = (전체 사용자 수 - 실패한 사용자 수)
noclear = 0; // 실패한 사용자 수 초기화
}
}
// 실패율을 기준으로 정렬하기
// Map.Entry 리스트 작성
// list_entries는 각 엔트리가 실패율을 저장한 Map.Entry<Integer, Double> 객체들을 저장
List<Map.Entry<Integer, Double>> list_entries = new ArrayList<Map.Entry<Integer, Double>>(stagefail.entrySet());
// key 오름차순, value로 내림차순정렬
// 비교함수 Comparator를 사용하여 오름차순으로 정렬
Collections.sort(list_entries, new Comparator<Map.Entry<Integer, Double>>() {
// compare로 값을 비교
public int compare(Map.Entry<Integer, Double> obj1, Map.Entry<Integer, Double> obj2) {
// 실패율을 기준으로 내림차순 정렬
return obj2.getValue().compareTo(obj1.getValue()); // obj1이 obj2보다 크면 1, 같으면 0, 작으면 -1 반환
}
});
int c=0;
for(Map.Entry<Integer, Double> entry : list_entries) {
answer[c]=entry.getKey(); c++; // 정렬한 list key값 answer에 넣기
}
return answer;
}
}
실패율을 구해줍니다.
그 다음엔 HashMap을 사용해 key값엔 스테이지 번호, value값엔 실패율을 넣은 후에
compare() 함수를 사용해 value값을 기준으로 내림차순 정렬을 해줍니다.
1. 실패율을 구해 hashmap에 저장
외부 for문으로 스테이지 개수인 N만큼 반복하며
내부 for문으로 현재 스테이지와 stages 배열을 비교해 같다면 실패한 사용자 수 noclear를 1 증가시켜줍니다.
현재 도전한 사용자가 없다면 실패율은 0.0 입니다.
도전한 사용자가 있다면 실패율 (noclear / player) 를 구해 stagefail에 넣어줍니다.
다음 반복문을 위해 player에서 noclear만큼 빼준 값으로 player를 업데이트 해주고,
noclear는 초기화 시켜줍니다.
2. 실패율을 내림차순 정렬
먼저 스테이지를 오름차순, 실패율을 내림차순으로 정렬하기 위한 Map.Entry 리스트를 정의해줍니다.
정렬해 줄 객체가 사용자가 정의해준 객체이기 때문에, Collection.sort() 메소드의 매개변수로 정렬하고자 하는 List변수명, Comparator 인터페이스를 구현한 클래스의 인스턴스를 넘겨줍니다.
Comparator 은 두 매개변수 객체를 비교하는 역할입니다.
인터페이스 내에 선언된 compare() 메소드를 반드시 오버라이딩 해줘야 합니다.
인터페이스 형식이 interface Comparator<T>{...} 인데, T 는 객체 타입이 지정될 자리며, compare() 메소드 안에 객체를 비교할 기준을 정의해주면 됩니다.
3. 정렬한 list key값을 answer에 인덱스 순서대로 넣어줍니다.
3️⃣ 옹알이(2)
문제 설명
머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ babbling의 길이 ≤ 100
- 1 ≤ babbling[i]의 길이 ≤ 30
- 문자열은 알파벳 소문자로만 이루어져 있습니다.
입출력 예
| babbling | result |
| ["aya", "yee", "u", "maa"] | 1 |
| ["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"] | 2 |
💻 나의 풀이
import java.util.*;
class Solution {
public int solution(String[] babbling) {
int answer = 0;
for(int i=0; i<babbling.length; i++){
// 만약 연속해서 같은 발음이 나온다면 continue
if(babbling[i].contains("ayaaya") || babbling[i].contains("yeye") || babbling[i].contains("woowoo") || babbling[i].contains("mama"))
continue;
// 연속해서 같은 발음이 나오지 않는다면, 각 발음을 공백으로 치환
babbling[i] = babbling[i].replace("aya"," ");
babbling[i] = babbling[i].replace("ye"," ");
babbling[i] = babbling[i].replace("woo"," ");
babbling[i] = babbling[i].replace("ma"," ");
babbling[i] = babbling[i].replace(" ", "");
// 해당 문자열의 길이가 0이라면 answer를 증가
if(babbling[i].length() == 0) answer++;
}
return answer;
}
}
0단계에서 풀었던 옹알이를 참고해서 풀었습니다.
중복되는 발음을 어떻게 배제시켜야 하나 했는데, 치환하지 않고 그대로 두고, 정상적인 발음이 나오는 부분만 공백으로 치환시켜 해당 문자열의 길이를 판단해 answer를 증가시키는 방법으로 풀었습니다.
🔍 다른 사람의 풀이
class Solution {
public int solution(String[] babbling) {
int answer = 0;
for(int i=0; i<babbling.length; i++){
babbling[i] = babbling[i].replaceAll("ayaaya|yeye|woowoo|mama","1");
babbling[i] = babbling[i].replaceAll("aya|ye|woo|ma"," ");
babbling[i] = babbling[i].replaceAll(" ","");
if(babbling[i].equals("")) answer++;
}
return answer;
}
}
같은 로직인데 | 를 적절하게 사용해서 코드 길이를 더 줄일 수도 있겠습니다.
class Solution {
public int solution(String[] babbling) {
int answer = 0;
String[] filter = {"aya", "ye", "woo", "ma"};
for(int i=0; i<babbling.length; i++) {
for(int j=0; j<filter.length; j++) {
if(!babbling[i].contains("ayaaya") && !babbling[i].contains("yeye") && !babbling[i].contains("woowoo") && !babbling[i].contains("mama"))
babbling[i] = babbling[i].replace(filter[j], " ");
}
babbling[i] = babbling[i].replace(" ", "");
if(babbling[i] == "") answer++;
}
return answer;
}
}
발음 배열을 만들어놓고 일치할 때 replace하는 방법도 있습니다.
4️⃣ [1차] 다트 게임
문제 설명
카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~
카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.
- 다트 게임은 총 3번의 기회로 구성된다.
- 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
- 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
- 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
- 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
- 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
- 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
- Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
- 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.
0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.
입력 형식
"점수|보너스|[옵션]"으로 이루어진 문자열 3세트.
예) 1S2D*3T
- 점수는 0에서 10 사이의 정수이다.
- 보너스는 S, D, T 중 하나이다.
- 옵선은 *이나 # 중 하나이며, 없을 수도 있다.
출력 형식
3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37
입출력 예
💻 나의 풀이
class Solution {
public int solution(String dartResult) {
String temp = ""; // 문자열 내 한 번의 점수 저장할 변수
int[] scores = new int[3]; // 다트를 세 번 던지는 게임이므로, 세 번의 점수를 저장할 배열
int idx = 0; // 인덱스
int answer = 0;
// 1. dartResult 문자열 순회
for(int i=0; i<dartResult.length(); i++) {
// 각각의 문자에 따라서 조건 처리하기 위한 switch문
switch(dartResult.charAt(i)) {
// S : 1제곱 / 다음 점수를 위해 인덱스idx 증가 / 점수 저장하는 temp 초기화
case 'S':
scores[idx] = (int)Math.pow(Integer.parseInt(temp), 1); // temp를 1제곱해서 정수로 변환해 저장
idx++; // 인덱스 증가
temp = ""; // 초기화
break;
// D : 2제곱 / 다음 점수를 위해 인덱스idx 증가 / 점수 저장하는 temp 초기화
case 'D':
scores[idx] = (int)Math.pow(Integer.parseInt(temp), 2);
idx++;
temp = "";
break;
// T : 3제곱 / 다음 정수를 위해 인덱스idx 증가 / 점수 저장하는 temp 초기화
case 'T':
scores[idx] = (int)Math.pow(Integer.parseInt(temp), 3);
idx++;
temp = "";
break;
// * : 해당점수와 이전의 점수 *2 / idx는 S,D,T 처리 후 증가하기 때문에 idx-1, idx-2 후 *2 해준다.
case '*':
scores[idx-1] *= 2;
if(idx > 1) scores[idx-2] *= 2; // 인덱스가 1보다 크다면 2를 빼서 이전의 점수도 *2 처리해준다.
break;
// # : 해당점수 *-1
case '#':
scores[idx-1] *= -1;
break;
// 그 외의 정수들은 temp 변수에 저장해 둔다.
default:
temp += String.valueOf(dartResult.charAt(i));
break;
}
}
// 2. 위 과정을 통해 구한 각 횟수의 점수를 모두 더한다.
for(int i=0; i<scores.length; i++) {
answer += scores[i];
}
return answer;
}
}
문제를 정말 여러 번 읽었던 것 같습니다..
일단 숫자랑 문자를 split으로 다 나누어서 보아야 하나?
아니면 앞에서 두 개씩 끊어내서 점수 계산을 해야하나?
스타상이 나왔을 때 바로 전 점수에도 2배를 해주려면 인덱스를 사용해야하나?
if문으로 하기엔 코드가 너무 더러울 거 같은데...케이스가 딱딱 나뉘어져 있으니 switch문을 써볼까?
여러 가지 아이디어를 떠올리고 풀어봤는데 안돼서 결국 다른 분들의 코드를 참고해서 해결했습니다.
어쨌든 혼자 풀지 못한 문제이니 자세하게 기록 해볼게요!
아주 자세한 설명은 주석으로 달아놨고
로직의 전체적인 흐름을 보자면 겁 먹었던 것에 비해 꽤 단순합니다.
1. 우선 세 번의 점수를 담을 scores배열, 문자열을 담을 수 있는 temp변수, 인덱스값을 위한 idx변수, 최종 정답을 담을 변수answer를 선언하고 초기화 해줍니다.
2. 주어진 dartResult문자열을 for문을 통해 순회합니다.
2-1. swtich~case문으로 들어온 문자열을 확인해주는데, 각각의 문자를 볼거기 때문에 charAt() 메소드를 사용해줬습니다.
2-2. 조건에 맞게 처리해줍니다.
2-3. 그 외의 점수들은 default를 사용해 temp변수에 저장해둡니다.
3. 위 과정을 통해서 구한 점수 scores[i]를 정답answer에 모두 더해줍니다.
double Math.pow(double base, double exponent) :
첫 번째 매개변수를 두 번째 매개변수로 거듭제곱한 값을 반환
base: 거듭제곱의 밑이 되는 숫자
exponent: 거듭제곱의 지수
switch (expression) {
case value1:
// expression이 value1과 일치할 때 수행할 코드
break;
case value2:
// expression이 value2와 일치할 때 수행할 코드
break;
// ...
default:
// 모든 case에 일치하지 않을 때 수행할 코드 (optional)
}
🔍 다른 사람의 풀이
class Solution {
public boolean solution(int x) {
int sum = 0;
int n = x;
while (n != 0) {
sum += n % 10; // 각 자릿수 구해서 sum 에 더하기
n /= 10; // 다음 자릿수로 넘어가기
}
return x % sum == 0? true : false;
}
}
5️⃣ 로또의 최고 순위와 최저 순위
문제 설명
로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1
로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.
알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 6개가 31, 10, 45, 1, 6, 19라면, 당첨 가능한 최고 순위와 최저 순위의 한 예는 아래와 같습니다.
- 순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다.
- 알아볼 수 없는 두 개의 번호를 각각 10, 6이라고 가정하면 3등에 당첨될 수 있습니다.
- 3등을 만드는 다른 방법들도 존재합니다. 하지만, 2등 이상으로 만드는 것은 불가능합니다.
- 알아볼 수 없는 두 개의 번호를 각각 11, 7이라고 가정하면 5등에 당첨될 수 있습니다.
- 5등을 만드는 다른 방법들도 존재합니다. 하지만, 6등(낙첨)으로 만드는 것은 불가능합니다.
민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다. 이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
- lottos는 길이 6인 정수 배열입니다.
- lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
- 0은 알아볼 수 없는 숫자를 의미합니다.
- 0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.
- lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.
- win_nums은 길이 6인 정수 배열입니다.
- win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.
- win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.
- win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.
입출력 예
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
알아볼 수 없는 번호들이 아래와 같았다면, 1등과 6등에 당첨될 수 있습니다.
입출력 예 #3
민우가 구매한 로또의 번호와 당첨 번호가 모두 일치하므로, 최고 순위와 최저 순위는 모두 1등입니다.
💻 나의 풀이
class Solution {
public int[] solution(int[] lottos, int[] win_nums) {
int[] answer = new int[2]; // [최고순위, 최저순위]
int cnt1 = 0; // 0의 갯수
int cnt2 = 0; // lottos와 win_nums에서 일치하는 숫자의 갯수
// lottos를 순회하면서 0의 갯수 구하기
for(int i : lottos) {
if(i == 0) {
cnt1++;
continue;
}
// win_nums 순회하면서 lottos와 win_nums에서 일치하는 숫자의 갯수 구하기
for(int j : win_nums) {
if(i == j) cnt2++;
}
}
answer[0] = getGrade(cnt1+cnt2); // 최고순위는 cnt1와 cnt2를 합해 결정
answer[1] = getGrade(cnt2); // 최저순위는 0을 제외하고 일치하는 숫자의 갯수로 결정
return answer;
}
// 순위 정하는 메소드
public int getGrade(int n) {
switch(n) {
case 6 :
return 1;
case 5 :
return 2;
case 4 :
return 3;
case 3 :
return 4;
case 2 :
return 5;
default :
return 6;
}
}
}
문제 접근 방식은 아래와 같습니다.
1. 최저 순위는 lottos와 win_nums의 일치하는 숫자의 갯수를 구해야 합니다. ( 0이 아닌 숫자들이 몇 개나 일치하느냐 )
2. 최고 순위는 최저 순위에 0의 갯수를 다 더한 값이 됩니다. 0이 나머지 숫자와 모두 다 일치한다고 가정해야 최고 순위이기 때문입니다.
3. 각 갯수에 맞게 등수를 결정해서 반환해줘야 하는데 switch문을 사용했습니다.
🔍 다른 사람의 풀이
import java.util.*;
class Solution {
public int[] solution(int[] lottos, int[] win_nums) {
int[] rank = {6, 6, 5, 4, 3, 2, 1};
int answer = 0;
int hidden = 0;
Arrays.sort(win_nums);
for (int i = 0; i < lottos.length; i++)
if (Arrays.binarySearch(win_nums, lottos[i]) > -1)
answer++;
else if (lottos[i] == 0)
hidden++;
return new int[] {rank[answer + hidden], rank[answer]};
}
}
rank 배열을 사용하여 일치하는 번호의 개수에 따라 순위를 즉시 계산하는 방법을 쓰셨네요. 이렇게하면 switch문을 쓰지 않아도 됩니다.
Arrays.sort(win_nums)를 사용하여 win_nums 배열을 오름차순으로 정렬합니다. 이렇게 하면 나중에 Arrays.binarySearch를 사용하여 특정 숫자를 빠르게 찾을 수 있습니다.
Arrays.binarySearch를 사용하면 배열을 정렬한 후에 이진 검색을 통해 원하는 값을 찾을 수 있어서 성능이 우수합니다.
💡 Arrays.binarySearch(int[] a, int key)
배열에서 이진 검색(Binary Search)을 수행하여 지정된 요소를 찾는 메서드입니다. 이 메서드는 특정 요소가 배열에 존재하는지 여부를 판단하고, 존재한다면 해당 요소의 인덱스를 반환하며, 존재하지 않는다면 음수 값을 반환합니다.
- a: 검색 대상 배열
- key: 찾을 요소
Arrays.binarySearch를 사용하기 위해서는 배열이 정렬되어 있어야 합니다.
'프로그래머스 > 1단계' 카테고리의 다른 글
| 문자열 나누기 / 숫자 짝꿍 / 체육복 / 대충 만든 자판 / 완주하지 못한 선수 (0) | 2024.03.02 |
|---|---|
| 과일 장수 / 모의고사 / 소수 만들기 / 기사단원의 무기 / 소수 찾기 (1) | 2024.02.09 |
| 추억 점수 / 명예의 전당(1) / 카드 뭉치 / 2016년 / 폰켓몬 (0) | 2024.02.03 |
| 문자열 내 마음대로 정렬하기 / K번째 수 / 두 개 뽑아서 더하기 / [1차]비밀지도 / 콜라 문제 (2) | 2024.01.28 |
| 최소직사각형 / 시저 암호 / 숫자 문자열과 영단어 / 가장 가까운 같은 글자 / 푸드 파이트 대회 (1) | 2024.01.26 |