체크사항
문제에 이모티콘 표시한 것은 풀 때 조금 어렵거나 새롭게 알게 된 알고리즘이라 다시 풀어보거나 체크해봐야 할 문제이다!
- 두 개 뽑아서 더하기
import java.util.*; class Solution { public int[] solution(int[] numbers) { Set<Integer> s = new TreeSet<>(); for(int i = 0; i < numbers.length; i++){ for(int j = i + 1; j < numbers.length; j++){ int sum = numbers[i] + numbers[j]; s.add(sum); } } int[] answer = new int[s.size()]; int idx = 0; for(int num : s){ answer[idx++] = num; } return answer; } }
오름차순으로 중복 없게 들어가야 하기 때문에 HashSet이 아닌 TreeSet을 사용했다. 이번 문제를 계기로 Set을 정리해보았다.
| 자료구조 | 내부 구현 | 데이터 순서 (Order) | 평균 시간 복잡도(추가/삭제/검색) | 핵심 요약 |
|---|---|---|---|---|
HashSet | Hash Table | 순서 없음 (뒤죽박죽) | O(1) (가장 빠름) | 단순 중복 제거 끝판왕 |
TreeSet | Red-Black Tree | 오름차순 정렬 (기본값) | O(\log N)(조금 느림) | 중복 제거 + 자동 정렬 마법 |
LinkedHashSet | Hash Table + Linked List | 입력된 순서 유지 | O(1) | 중복 제거 + 들어온 순서 기억 |
| 분류 | 코드 / 메서드 | 설명 |
|---|---|---|
| 기본 사용 방법 | Set<Integer> s = new HashSet<>(); | (가장 기본형인 HashSet 기준) |
| 데이터 추가 | add(item) | 셋에 아이템을 삽입 (중복된 값이면 무시) |
| 데이터 삭제 | remove(item) | 셋에서 특정 아이템을 찾아서 제거 |
| 데이터 확인 | contains(item) | 셋에 해당 아이템이 있는지 반환 (Set의 핵심! 매우 빠름) |
| 비었는지 확인 | isEmpty() | 셋이 비었는지 반환 (true / false) |
| 크기 확인 | size() | 셋에 들어있는 고유한 원소의 개수 반환 |
| 초기화 | clear() | 셋의 모든 원소를 한 번에 싹 제거 |
- 숫자 문자열과 영단어
import java.util.*; class Solution { public int solution(String s) { int answer = 0; StringBuilder sb = new StringBuilder(); StringBuilder tmp = new StringBuilder(); Map<String, Integer> m = new HashMap<>(); m.put("zero", 0); m.put("one", 1); m.put("two", 2); m.put("three", 3); m.put("four", 4); m.put("five", 5); m.put("six", 6); m.put("seven", 7); m.put("eight", 8); m.put("nine", 9); for(char ch : s.toCharArray()){ if(Character.isDigit(ch)){ if(tmp.length() > 0){ sb.append(m.get(tmp.toString())); tmp.setLength(0); } sb.append(ch); } else{ tmp.append(ch); if(m.containsKey(tmp.toString())){ sb.append(m.get(tmp.toString())); tmp.setLength(0); } } } return Integer.parseInt(sb.toString()); } } // 개선 class Solution { public int solution(String s) { String[] words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; for(int i = 0; i < 10; i++){ s = s.replace(words[i], Integer.toString(i)); } return Integer.parseInt(s); } }
맵을 사용하여 풀었는데 훨씬 간단한 방법이 있었다.그래도 맵을 사용한 김에 정리를 해봐야겠다.
| 자료구조 | 데이터 순서 (Key 기준) | 언제 쓸까? (실무 선택 가이드) |
|---|---|---|
HashMap | 순서 없음 (뒤죽박죽) | "순서 상관없이 Key로 Value만 엄청 빨리 찾고 싶어!" (99% 확률로 이거 씀) |
TreeMap | 오름차순 정렬 (Key 기준) | "Key 값을 기준으로 가나다순, 123순 예쁘게 정렬해서 저장해야 해!" |
LinkedHashMap | 입력된 순서 유지 | "내가 put으로 데이터를 집어넣은 순서표를 그대로 기억해 줬으면 좋겠어!" |
| 분류 | 코드 / 메서드 | 설명 |
|---|---|---|
| 기본 사용 방법 | Map<String, Integer> m = new HashMap<>(); | (가장 기본형인 HashMap 기준) |
| 데이터 추가/수정 | put(key, value) | 맵에 Key-Value 쌍을 삽입 (이미 있는 Key면 Value가 덮어씌워짐!) |
| 데이터 꺼내기 | get(key) | Key를 주고, 그에 맞는 Value를 반환 (없으면 null 반환) |
| 데이터 꺼내기 | getOrDefault(key, 기본값) | Key를 주고, 그에 맞는 Value를 반환(없으면 기본값 반환) |
| 데이터 삭제 | remove(key) | 맵에서 해당 Key와 그에 딸린 Value를 통째로 제거 |
| Key 존재 확인 | containsKey(key) | 맵에 해당 Key가 있는지 반환 (true / false) |
| Value 존재 확인 | containsValue(value) | 맵에 해당 Value가 있는지 반환 (Key 탐색보단 느림) |
| 비었는지 확인 | isEmpty() | 맵이 비었는지 반환 (true / false) |
| 크기 확인 | size() | 맵에 들어있는 Key-Value 쌍의 개수 반환 |
| Key만 다 뽑기 | keySet() | 맵에 있는 모든 Key만 모아서 Set 형태로 반환 (for문 돌릴 때 필수!) |
- K번째 수
import java.util.*; class Solution { public int[] solution(int[] array, int[][] commands) { int[] answer = new int[commands.length]; for(int i = 0; i < commands.length; i++){ int from = commands[i][0], to = commands[i][1], target = commands[i][2]; int[] tmp = Arrays.copyOfRange(array, from - 1, to); Arrays.sort(tmp); answer[i] = tmp[target - 1]; } return answer; } }
시작, 끝, 타겟 인덱스를 체크하여서 기존 배열에서 시작과 끝을 잘라서 정렬한 후 타겟 인덱스의 값을 넣으면 해결
- 콜라 문제
class Solution { public int solution(int a, int b, int n) { int answer = 0; while(n >= a){ answer += n / a * b; n = (n / a) * b + (n % a); } return answer; } }
n이 a보다 크거나 같을 때까지 얻는 병을 더하고 남은 병과 얻은 병의 양으로 갱신하여 해결
- 명예의 전당 (1)
import java.util.*; class Solution { public int[] solution(int k, int[] score) { int[] answer = new int[score.length]; for(int i = 0; i < score.length; i++){ int[] tmp = Arrays.copyOfRange(score, 0, i + 1); Arrays.sort(tmp); if(tmp.length < k) answer[i] = tmp[0]; else answer[i] = tmp[tmp.length - k]; } return answer; } } // 개선(우선순위 큐) import java.util.*; class Solution { public int[] solution(int k, int[] score) { int[] answer = new int[score.length]; PriorityQueue<Integer> pq = new PriorityQueue<>(); for(int i = 0; i < score.length; i++) { pq.add(score[i]); if (pq.size() > k) { pq.poll(); } answer[i] = pq.peek(); } return answer; } }
처음에 반복문에서 정렬하고 answer에 추가하는 방식을 했는데 이러면 O(n^2log(n))이 되어 효율이 떨어진다. 그래서 찾은 방법이 우선순위 큐를 활용하여 해결하는 것이다. 우선순위큐를 사용한 김에 큐를 정리해야겠다.
| 자료구조 | 데이터 입출력 방식 |
|---|---|
Queue(LinkedList) | FIFO (First In First Out) 먼저 들어간 놈이 먼저 나옵니다. |
PriorityQueue | 우선순위 (최솟값/최댓값) 순서 상관없이 지정된 기준(VIP)이 먼저 나옵니다. |
Deque(ArrayDeque) | 양방향 입출력 (만능) 앞으로도 넣고 빼고, 뒤로도 넣고 뺄 수 있습니다. |
| 분류 | 코드 / 메서드 | 설명 (큐 & 데크 공통 및 전용) |
|---|---|---|
| 기본 선언 | Queue<Integer> q = new LinkedList<>();PriorityQueue<Integer> pq = new PriorityQueue<>();Deque<Integer> dq = new ArrayDeque<>(); | 데크는 주로 빠르고 가벼운 ArrayDeque로 만듦 |
| 데이터 넣기 | offer(item) | (공통) 큐의 맨 뒤에 데이터를 집어넣습니다. |
| (데크 전용) | offerFirst(item) / offerLast(item) | [Deque] 맨 앞에 넣기 / 맨 뒤에 넣기 (선택 가능!) |
| 데이터 빼기 | poll() | (공통) 우선순위가 가장 높은(또는 맨 앞) 데이터를 꺼내고 삭제 |
| (데크 전용) | pollFirst() / pollLast() | [Deque] 맨 앞의 데이터 빼기 / 맨 뒤의 데이터 빼기 |
| 데이터 확인 | peek() | (공통) 다음에 나올 데이터가 뭔지 확인만 합니다. (삭제 X) |
| (데크 전용) | peekFirst() / peekLast() | [Deque] 맨 앞 데이터 확인 / 맨 뒤 데이터 확인 |
| 비었는지/크기 | isEmpty() / size() / clear() | (공통) 비었는지 확인 / 데이터 개수 확인 / 싹 다 지우기 |
- 문자열 내 마음대로 정렬하기
import java.util.*; class Solution { public String[] solution(String[] strings, int n) { Arrays.sort(strings, (a, b)->{ if(a.charAt(n) == b.charAt(n)) return a.compareTo(b); return a.charAt(n) - b.charAt(n); }); return strings; } }
람다식으로 푸는 방식 아직 어색하며 문자열이면 a - b 가 아니라 a.compareTo(b) 이런 식으로 비교를 해야한다.
- 카드 뭉치
import java.util.*; class Solution { public String solution(String[] cards1, String[] cards2, String[] goal) { Queue<String> q1 = new LinkedList<>(); Queue<String> q2 = new LinkedList<>(); for(String card : cards1) q1.offer(card); for(String card : cards2) q2.offer(card); for(String s : goal){ if(!q1.isEmpty() && q1.peek().equals(s)){ q1.poll(); } else if(!q2.isEmpty() && q2.peek().equals(s)){ q2.poll(); } else{ return "No"; } } return "Yes"; } } // 메모리 절약(투 포인터) class Solution { public String solution(String[] cards1, String[] cards2, String[] goal) { int idx1 = 0, idx2 = 0; for(String s : goal){ if(idx1 < cards1.length && cards1[idx1].equals(s)){ idx1++; } else if(idx2 < cards2.length && cards2[idx2].equals(s)){ idx2++; } else{ return "No"; } } return "Yes"; } }
큐 2개로 값과 같으면 제거하는 방식으로 풀었는데 투 포인터로 메모리를 절약하는 방식이 있어 개선해보았다.
- 추억 점수
import java.util.*; class Solution { public int[] solution(String[] name, int[] yearning, String[][] photo) { int[] answer = new int[photo.length]; Map<String, Integer> m = new HashMap<>(); for(int i = 0; i < name.length; i++){ m.put(name[i], yearning[i]); } int idx = 0; for(String[] p : photo){ int y = 0; for(String n : p){ y += m.getOrDefault(n, 0); } answer[idx++] = y; } return answer; } }
맵으로 이름과 점수를 먼저 생성하고 사진을 돌면서 점수를 합산한다. 없는 이름을 대비하여 get이 아닌 getOrDefault 를 활용하여 해결
- [1차] 비밀지도
import java.util.*; class Solution { public String[] solution(int n, int[] arr1, int[] arr2) { String[] answer = new String[n]; for(int i = 0; i < n; i++){ char[] c1 = change(arr1[i], n); char[] c2 = change(arr2[i], n); char[] ch = new char[n]; for(int j = 0; j < n; j++){ ch[j] = (c1[j] == '1' || c2[j] == '1')? '#' : ' '; } answer[i] = String.valueOf(ch); } return answer; } private char[] change(int num, int n){ StringBuilder sb = new StringBuilder(); while(num != 0){ sb.append((char)(num % 2 + '0')); num /= 2; } while(sb.length() != n){ sb.append('0'); } return sb.reverse().toString().toCharArray(); } } // 비트 연산자 풀이 class Solution { public String[] solution(int n, int[] arr1, int[] arr2) { String[] answer = new String[n]; for (int i = 0; i < n; i++) { int combined = arr1[i] | arr2[i]; String mapRow = Integer.toBinaryString(combined).replace('1', '#').replace('0', ' '); while (mapRow.length() < n) { mapRow = " " + mapRow; } answer[i] = mapRow; } return answer; } }
각 수를 2진수로 바꾸어 문자열로 치환하여 해결했는데 비트 연산과 정수를 2진수로 바꾸는 함수를 활용하면 거의 절반의 코드 길이로도 해결이 가능하다.
비트 연산
| 연산자 | 이름 | 동작 규칙 (비유) |
|---|---|---|
| `A | B` | OR (논리 합) |
A & B | AND (논리 곱) | 둘 모두 1이면 1 |
A ^ B | XOR (배타적 논리 합) | 서로 다르면 1 같으면 0 |
~A | NOT (논리 부정) | 0은 1로 1은 0으로 |
- 폰켓몬
import java.util.*; class Solution { public int solution(int[] nums) { Set<Integer> s = new HashSet<>(); for(int num : nums) s.add(num); if(s.size() >= nums.length / 2) return nums.length / 2; return s.size(); } }
중복되는 값을 제거한 집합이 전체의 2분의 1보다 크거나 같은지 체크하여 값을 반환하면 해결
- 기사단원의 무기
class Solution { public int solution(int number, int limit, int power) { int answer = 0; for(int i = 1; i <= number; i++){ int c = cnt(i, limit, power); answer += c; } return answer; } private int cnt(int num, int limit, int power){ int cnt = 0; for(int i = 1; i * i <= num; i++){ if(i * i == num) cnt++; else if(num % i == 0) cnt += 2; if(cnt > limit){ cnt = power; break; } } return cnt; } }
반복문으로 단순히 약수 개수를 구하면 시간 초과가 날 수 있어서 제곱근이 약수면 1개 추가 아니라면 2개 추가하는 방식으로 약수 개수를 구하면 O( Nsqrt(N))으로 해결할 수 있다.
- 모의고사
import java.util.*; class Solution { public int[] solution(int[] answers) { int[] person1 = {1, 2, 3, 4, 5}; int[] person2 = {2, 1, 2, 3, 2, 4, 2, 5}; int[] person3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; int p1 = 0, p2 = 0, p3 = 0; for(int i = 0; i < answers.length; i++){ if(answers[i] == person1[i % 5]) p1++; if(answers[i] == person2[i % 8]) p2++; if(answers[i] == person3[i % 10]) p3++; } int max = Math.max(p1, Math.max(p2, p3)); ArrayList<Integer> list = new ArrayList<>(); if(max == p1) list.add(1); if(max == p2) list.add(2); if(max == p3) list.add(3); return list.stream().mapToInt(i ->i).toArray(); } }
반복되는 찍기를 미리 배열로 만들어 answers를 순회하면서 % 해당 배열 크기로 인덱스를 갱신하면 각 사람의 맞는 개수를 셀 수 있고 최대값을 구해 해당 값과 같으면 리스트에 넣어 배열로 반환하면 해결
- 2016년
class Solution { public String solution(int a, int b) { int[] month = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30}; int day = 0; for(int i = 0; i < a - 1; i++) day += month[i]; day += b - 1; String[] days = {"FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"}; return days[day % 7]; } }
누적된 일수를 세어 해당 값을 7로 나눈 나머지의 요일을 구하면 되며 요일은 1월 1일이 금요일이니 금요일부터 세팅하였다.
- 덧칠하기 🤔
class Solution { public int solution(int n, int m, int[] section) { int answer = 0; int e = 0; for(int i = 0; i < section.length; i++){ e = section[i] + m - 1; for(int j = i + 1; j < section.length; j++){ if(section[j] > e) break; i++; } answer++; } return answer; } } // 개선 class Solution { public int solution(int n, int m, int[] section) { int answer = 0; int painted = 0; for (int s : section) { if (s > painted) { answer++; painted = s + m - 1; } } return answer; } }
처음에 길이로 갱신하려다가 엄청 헤맸다….길이보다 끝나는 인덱스를 저장하여 다음 구역이 그것보다 작다면 넘어가는 방식으로 해결할 수 있다. 안쪽 반복문을 없애는 방법이 있어 개선해보았다.
- 과일 장수
import java.util.*; class Solution { public int solution(int k, int m, int[] score) { int answer = 0; Arrays.sort(score); int min = 10, select = 0; for(int i = score.length - 1; i >= 0; i--){ if(select == m){ answer += min * m; select = 0; } min = Math.min(min, score[i]); select++; } if(select == m){ answer += min * m; } return answer; } } // 개선 import java.util.*; class Solution { public int solution(int k, int m, int[] score) { int answer = 0; Arrays.sort(score); for(int i = score.length - m; i >= 0; i -= m) { answer += score[i] * m; } return answer; } }
정렬해서 큰 거부터 상자에 담는 그리디 방법을 사용하였으며 m만큼 고르면 최소 * m을 답에 더하고 마지막에 한 번 모두 골랐으면 더하는 방식으로 해결했다. 정렬하여서 min을 안하고 해결하는 방식이 있어 개선했다.
- 지폐 접기
class Solution { public int solution(int[] wallet, int[] bill) { int answer = 0; int max_w = Math.max(wallet[0], wallet[1]); int min_w = Math.min(wallet[0], wallet[1]); int max_b = Math.max(bill[0], bill[1]); int min_b = Math.min(bill[0], bill[1]); while(true){ if(min_w < min_b || max_w < max_b){ max_b /= 2; answer++; } if(max_b < min_b){ int tmp = min_b; min_b = max_b; max_b = tmp; } if(max_w >= max_b && min_w >= min_b) break; } return answer; } }
문제에 조건을 모두 보여줘서 해당 조건을 따라가서 구현만 하면 해결이 된다. 큰 부분과 작은 부분만 잘 유지하면 해결
- 소수 만들기
class Solution { public int solution(int[] nums) { int answer = 0; for(int i = 0; i < nums.length - 2; i++){ for(int j = i + 1; j < nums.length - 1; j++){ for(int k = j + 1; k < nums.length; k++){ if(isPrime(nums[i] + nums[j] + nums[k])) answer++; } } } return answer; } boolean isPrime(int num){ for(int i = 2; i <= (int)Math.sqrt(num); i++){ if(num % i == 0){ return false; } } return true; } }
배열이 크지 않아 3중 반복문으로 3개를 더한 값이 소수인지 판별하였다. 소수 판별은 루트를 씌운 값까지 나누어 떨어지는 수가 있으면 아니고 아니라면 맞는 것으로 구현했다.
- 소수 찾기 🤔
class Solution { public int solution(int n) { int answer = 0; for(int i = 1; i <= n; i++){ if(isPrime(i)) answer++; } return answer; } private boolean isPrime(int num){ if(num < 2) return false; for(int i = 2; i <= (int)Math.sqrt(num); i++){ if(num % i == 0) return false; } return true; } } // 개선 import java.util.*; class Solution { public int solution(int n) { int answer = 0; boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= (int)Math.sqrt(n); i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } for (int i = 2; i <= n; i++) { if (isPrime[i]) answer++; } return answer; } }
소수 만들기 문제의 소수 판별 함수를 그대로 사용하여 1부터 n까지 소수 개수를 세어 해결했다. 훨씬 빠른 방법을 찾아서 개선했다. 에라토스테네스의 체라는 알고리즘으로 해당 값이 소수이면 모든 배수를 소수가 아니라고 제외하는 방법을 활용하여 개선했다.
- 옹알이 (2)
class Solution { public int solution(String[] babbling) { String[] str = {"aya", "ye", "woo", "ma"}; int answer = 0; for(String st : babbling){ for(String s : str){ st = st.replaceFirst(s, " "); } st = st.replace(" ", ""); if(st.equals("")) answer++; } return answer; } } // 해결 class Solution { public int solution(String[] babbling) { String[] str = {"aya", "ye", "woo", "ma"}; int answer = 0; for(String st : babbling){ if(st.contains("ayaaya") || st.contains("yeye") || st.contains("woowoo") || st.contains("mama")) { continue; } for(String s : str){ st = st.replace(s, " "); } st = st.replace(" ", ""); if(st.equals("")) answer++; } return answer; } }
처음처럼 풀었는데 문제를 자세히 보니 2개의 연속 발음이 있으면 안되는 것이라서 replaceFirst를 해버리면 문제가 된다. 따라서 2개의 연속 발음이 있는지 체크하고 replace로 하면 해결된다.
- 실패율 🤔
import java.util.*; class Solution { public int[] solution(int N, int[] stages) { Arrays.sort(stages); int[] num = new int[N + 1]; int[] fail = new int[N + 1]; for(int i = 0; i < stages.length; i++){ int s = stages[i]; if(s > N) continue; if(num[s] == 0) num[s] = stages.length - i; fail[s]++; } Map<Integer, Double> m = new HashMap<>(); for(int i = 1; i <= N; i++){ double percent = 0.0; if(num[i] == 0) percent = 0.0; else percent = (double)fail[i] / num[i]; m.put(i, percent); } List<Integer> list = new ArrayList<>(m.keySet()); list.sort((a, b)->Double.compare(m.get(b), m.get(a))); return list.stream().mapToInt(i->i).toArray(); } }
도전 인원과 실패 인원을 세어 실패율을 구하는 것까지는 구현했는데 실패율이 높은 순서로 배열을 만드는 것을 실패해서 다른 사람 풀이를 참고하였다.
개발자가 되기 위해 열심히 춤추는 중이에요 🕺