완주하지 못한 선수
문제
- 문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
-
제한 사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
-
입출력 예시
participant completion return ["leo", "kiki", "eden"] ["eden", "kiki"] "leo" ["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko" ["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"
문제 풀이
participant 배열에는 있고, completion 배열에는 없는 요소를 찾으면 되는 문제다.
간단하다고 생각했는데 엄청 오래 걸렸다.. 그냥 내가 모르는 문제였다고 봐도 무방
아래는 내가 문제를 풀기 위해 시도한 방법들이다.
1차 시도 : 배열 반복문 2개 : 실행 시간 최악 13
2차 시도 : 배열 반복문 2개 + boolean 배열 1개 : 실행 시간 최악 13
3차 시도 : ArrayList 2개 + boolean 배열 1개 : 실행 시간 최악 9
4차 시도 : ArrayList 2개 : 실행 시간 최악 9 ~ 12
5차 시도 : ArrayList 1개 : 실행 시간 최악 8
6차 시도 : ArrayList 1개 + break문 추가 : 실행 시간 최악 6
7차 시도 : HashMap 1개 + ArrayList 1개 : 실행 시간 최악 7
8차 시도 : HashMap 1개 : 실행 시간 최악 1초, 효율성 + 정확도 100점
==> 8차 시도에는 방법을 아예 바꿔서 Key : String, Value : Count로 표현했다.
==> 그 다음 completion 배열과 비교하며 값이 있는 경우 1개씩 지워나갔다.
==> 최종적으로 남는 단 하나의 HashMap을 출력하면 됐다.중간에 있는 boolean 배열을 사용한 이유는 participant 배열의 인덱스와 같은 boolean 배열의 true, false만 체크해서 정답으로 내보내기 위함이었다.
HashMap 이라는 자료구조를 사용했다. Map 이란, Key와 Value의 쌍으로 이루어진 자료구조이다. Key는 Map에서 유일하게 있어야 한다. 즉, 중복되어서는 안된다.
HashMap과 사용법이 거의 동일한 자료구조는 HashTable이 있다고 한다. 두 클래스의 차이점은 Thread 관점에서 안전하느냐, 혹은 안전하지 않은 대신 속도가 빠르냐 이다.
안전한 자료구조는 HashTable, 빠른 자료구조는 HashMap이라고 생각하면 된다.
HashMap은 java.util.Map과 java.util.HashMap을 import하여 사용한다.
아래는 문제 풀이 코드이다.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
Map<String, Integer> par = new HashMap();
for(int i = 0; i < participant.length; i++) {
if(par.containsKey(participant[i])) {
int count = (int) par.get(participant[i]);
par.put(participant[i], count + 1);
}
else
par.put(participant[i], 1);
}
for(String i : completion)
if(par.containsKey(i)) {
if(par.get(i) == 1)
par.remove(i);
else // 동명이인이 2명 이상 있는 경우
par.put(i, par.get(i) - 1);
}
String answer = "";
for(String key : par.keySet())
answer = key;
return answer;
}
}HashMap에 key는 선수의 이름, value는 그 이름을 가진 선수가 몇 명인지를 count 하여 put 했다. 그 다음, completion 배열에서 선수들의 이름이 자료구조에 있는지 검사한 후 count를 하나씩 줄이는 방법을 사용했다. 최종적으로는 1명만 남게 될 것이다.
k번째 수
문제
-
문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. -
제한 사항
- array의 길이는 1 이상 100 이하입니다.
- array의 각 원소는 1 이상 100 이하입니다.
- commands의 길이는 1 이상 50 이하입니다.
- commands의 각 원소는 길이가 3입니다.
-
입출력 예시
arrays commands return [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]
문제 풀이
이 문제는 배열을 잘라 낸 다음, 잘라 낸 배열을 정렬하는 문제이다. 문제 풀이 코드를 보자.
import java.util.*;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
int i = 0;
for(int[] arr : commands) {
int[] temp = Arrays.copyOfRange(array, arr[0] - 1, arr[1]);
Arrays.sort(temp);
answer[i] = temp[arr[2] - 1];
i++;
}
return answer;
}
}위에서 보면 Arrays 클래스를 사용했다. solution 메소드의 매개 변수로 주어지는 배열을 자른 배열을 temp로 저장한다. 이 때, 배열을 잘라낼 때 Arrays 클래스의 copyOfRange 메소드를 사용했다.
copyOfRange(array, start, end) 처럼 사용하면 array 배열을 start부터 end - 1까지 잘라 주는 메소드이다. 그 다음 자른 배열을 Arrays.sort를 통해 정렬하면 된다.
나는 최초에 이 문제를 풀 때 Arrays.sort를 사용하지 않고 선택 정렬을 구현해서 풀었었다. (퀵 정렬이 제대로 기억나지 않음)
