어제 코테와 42dot 지원서 작성한다고 늦게 자는 바람에 좀 늦게 일어났다. 아침형 인간 만들기가 힘든 것 같다. 뭔가 밤에 공부가 더 잘되는 느낌... 그리고 프로젝트 이후로 조용한 밤에 익숙해졌다.
12:00 ~ 14:00
[프로그래머스] 입국 심사 (이진탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/43238
두 심사관으로 부터 심사 받는 시간의 최소값을 구하면되는 문제입니다.
먼저, 제일 짧을때를 low, 제일 길때를 high로 둡니다. 이 둘을 합하여 2로 나눈 값을 중앙값으로 두고 몇명의 인원을 처리가능한지 확인해봅니다. n명이상 심사가 가능할 경우 -1을 하여 더 짧은 시간이 있는지 탐색하고 n명 미만일 경우에는 +1을 하여 최소 시간을 늘려줍니다. 이렇게 계속계산하여 low가 high보다 작거나 같고, 모든 인원 n 을 수용할 수 있으면 해당 시간이 정답이 됩니다.
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
// 정렬을 통해 최대 시간을 쉽게 찾을 수 있다.
Arrays.sort(times);
long low = 1;
// 가장 오래 걸리는 심사관이 n명을 모두 처리하는 최악의 경우
long high = (long)times[times.length - 1] * n;
long answer = high;
// low가 high보다 작거나 같아야함
while (low <= high) {
long mid = (low + high) / 2; // 중앙값 계산
long count = 0;
// mid 시간 동안 처리 가능한 총 인원 계산
// times 배열의 각 요소에 대해, time이라는 변수 담아 반복문 실행
for (int time : times) {
count += mid / time;
// n명을 모두 심사할 수 있으면 더 이상 계산할 필요 없음
if (count >= n) {
break;
}
}
// 심사 가능한 인원이 n명 이상인 경우
if (count >= n) {
answer = mid; // 현재 mid가 정답 후보
high = mid - 1; // 더 짧은 시간이 있는지 탐색
}
// 심사 가능한 인원이 n명 미만인 경우
else {
low = mid + 1; // 시간을 더 늘려야 함
}
}
return answer;
}
}14:00 ~ 15:30
[프로그래머스] 징검다리 (이진탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/43236
어려워서 미뤄두었다.
[프로그래머스] 체육복 (탐욕법)
https://school.programmers.co.kr/learn/courses/30/lessons/42862
해당 문제는 lost 인원에게 reserve 인원이 빌려줄수 있을때의 체육 수업을 들을 수 있는총 인원을 구하면 됩니다.
그러나 n의 인원수 만큼 학생이 존재합니다. 즉, 마지막 케이스인 n=3, lost=3, reserve=1 같은 경우 n이 3이므로 1, 2, 3의 학생이 있고 1, 2번 학생이 체육복이 있어 결과는 2가 됩니다.
생각해야될 사항은
- 여벌의 체육복에 있지만 lost인 경우
- 여벌 체육복을 빌려주는 경우
- 아무에게도 빌리지 못한 경우
해당 사항은 if 문으로 처리합니다.
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
// 배열을 ArrayList로 변환하여 유연하게 처리
List<Integer> lostList = new ArrayList<>();
for (int l : lost) {
lostList.add(l);
}
List<Integer> reserveList = new ArrayList<>();
for (int r : reserve) {
reserveList.add(r);
}
// 1. 여벌 체육복을 가져왔지만 도난당한 학생 처리
// removeIf()를 사용하여 두 리스트에 있는 요소 제거(애초에 읽어버린 명단에서 제거)
lostList.removeIf(num -> reserveList.remove(Integer.valueOf(num)));
// 기본적으로 참여 가능한 학생 수(잃어버린 학생의 여분 고려 X)
int answer = n - lostList.size();
// 정렬: 대여 과정을 원활하게 하기 위해
Collections.sort(lostList);
Collections.sort(reserveList);
// 2. 남은 학생들에게 체육복 빌려주기
for(int lostStudent : lostList) {
// 바로 앞 번호 학생이 여벌 체육복있는지 확인
if (reserveList.contains(lostStudent - 1)) {
answer ++;
reserveList.remove(Integer.valueOf(lostStudent - 1));
}
// 바로 뒤 번호 학생이 여벌 체육복있는지 확인
else if ( reserveList.contains(lostStudent + 1)) {
answer++;
reserveList.remove(Integer.valueOf(lostStudent + 1));
}
}
return answer;
}
}+++원티드의 마지막 미션 4 원티드에서 지원하기 항목을 제외하고 모든 미션을 빠르게 완료했다.
이미 써져있는 이력서가 있어서 금방 끝낼 수 있었다.
17:00 ~ 20:00
Java 향상된 for문
다른 문제를 풀기전에 Java에서 향상된 for문이라는 것이 이해가 잘 되지 않아 공부를 해보았습니다. 예전에 잘만 썻는데, 몇달 안했다고 까먹었나봅니다.
향상된 for문은 배열이나 Collection(List, Set 등) 에 있는 요소를 순차적으로 꺼내 쓸 때 사용하는 구문입니다.
기본 for문과의 비교
기본적으로 알고 있는 for문은 다음과 같습니다.
int[] nums = {1, 2, 3, 4, 5};
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]); // 인덱스를 사용해서 접근
}향상된 for문을 쓰면 다음과 같이 사용할 수 있습니다.
int[] nums = {1, 2, 3, 4, 5};
for (int n : nums) {
System.out.println(n); // 요소를 직접 꺼내서 사용
}n이 nums에 있는 리스트 요소들을 직접 꺼내서 사용합니다.
기본은 인덱스를 직접 제어해야합니다. (i 사용)
향상된 for은 인덱스를 신경쓰지 않고, 요소를 순서대로 바로 꺼내줍니다.
컬렉션에서의 사용
컬렉션을 예제로 보면 다음과 같습니다.
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("Kim");
names.add("Lee");
names.add("Park");
for (String name : names) {
System.out.println(name);
}
}
}names라는 배열이 순서대로 출력되어 Kim → Lee → Park 순으로 출력됩니다.
사용 시 주의점
- 인덱스가 필요할 때는 사용할 수 없습니다.
// 잘못된 예시
for (int n : nums) {
if (n == nums[2]) { ... } // 인덱스 직접 접근 불가능
}인덱스에 직접 접근할 수 없으므로 기존 for 문을 사용해야합니다.
- 배열/컬렉션의 요소를 변경할 수 없습니다.
for (int n : nums) {
n = n * 2; // nums 배열 안의 값은 바뀌지 않음
}배열안 요소에 직접 접근 불가능합니다. 물론 편집도 안됩니다.
[프로그래머스] 조이스틱 (탐욕법)
https://school.programmers.co.kr/learn/courses/30/lessons/42860
우리가 여기서 해결해야하는건 최소한의 조작으로 원하는 알파벳을 만드는 것입니다. 고려를 좀 더 해야되는건 A에서 밑의 키를 누르면 Z가 된다는 것입니다.
커서를 왼쪽으로 가나 오른쪽으로 가나 커서 이동에 관해서는 문제되지 않을까?
→ 아닙니다. 만약에 답이 'JAAX'여야한다면 첫번째 자리에서 왼쪽을 눌러서 마지막으로 이동할 필요가 있습니다.
그럼 우리가 주력적으로 생각하야되는건, 알파벳을 만드는 경우와 커서의 위치를 바꾸는 경우입니다.
알파벳은 [만들어야하는 글자 - A] 와 [Z - 만들어야하는 글자] 중 더 작은 경우의 수를 선정하면 됩니다.
문제는 커서의 위치를 바꾸는 경우를 생각하는 것입니다. 단어 중간에 A가 얼마나 많냐에 따라서 왼쪽으로 시작할지, 오른쪽으로 시작할지 모릅니다. 그러면 오른쪽으로만 이동했을때 케이스는 전체길이에 -1을 한 값이고, 모든 글자를 순회하면서 각 위치에서 A가 아닌 글자를 만났을때, 오른쪽으로 갔다가 되돌아오는 경우를 계산하고 그 값과 기존의 최솟값을 비교하여 업데이트하는 방식으로 접근하면 됩니다. (중간의 A들을 건너뚜기위해 방향을 바꾸는 경우를 계산)
이러한 생각을 떠올리기 쉽지 않아서 도움을 많이 받았습니다. 레벨 2의 그리디 알고리즘인데 왜 이렇게 어려운지…
class Solution {
public int solution(String name) {
int answer = 0;
// 기본 좌우 이동 횟수 (오른쪽으로)
int min_move = name.length() - 1;
for(int i = 0; i < name.length(); i++) {
char current_char = name.charAt(i);
// 알파벳 변경 횟수 계산 (상하)
answer += Math.min(current_char - 'A', 'Z' - current_char + 1);
// 커서 이동 횟수 계산 (좌우)
// 연속된 A를 찾아서 그 다음 A가 아닌 글자 위치를 확인
int next_i = i + 1;
// name.charAt(1)의 문자가 'A'가 나올때까지 진행
while (next_i < name.length() && name.charAt(next_i) == 'A') {
next_i++;
}
// 오른쪽으로 갔다가 돌아오는 경로
int move_right = i;
int move_left = name.length() - next_i;
int total_move = move_right + move_left + Math.min(move_right, move_left);
// 최종 최소 좌우 이동 횟수 업뎃
/* [i + name.length() - next_i]은 문자열 끝에서부터(n-1) 다음 'A'가 아닌 글자(next_i)까지 왼쪽으로 이동하는 거리입니다. 해당 값을 모두 더하면 양쪽 끝을 모두 방문하는 총 거리가 됩니다. 즉, 이동한 총 거리입니다. */
/* [Math.min(i, name.length() - next_i)]은 'A'를 만났을때, U턴을 하기 위해 추가로 이동해야하는 거리입니다. 가장 짧아야하므로 Math.min을 사용합니다. 즉, 방향을 바꾸는 데 필요한 추가 이동입니다.*/
// 위의 둘을 더해 가장 짧은 경로가 결과가 됩니다.
min_move = Math.min(min_move, i + name.length() - next_i + Math.min(i, name.length() - next_i));
}
answer += min_move;
return answer;
}
}[프로그래머스] 최빈값 구하기 (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120812
주어진 array 배열에서 제일 많이 나오는 원소를 구하면 됩니다. 그러나 최빈값이 두개 이상이면, -1을 출력해야합니다.
배열을 정렬한다음 최빈값과 과거 최빈값의 빈도와 현재 최빈값의 빈도를 설정합니다. 배열의 원소가 인전 값과 같을 시 count +1을 하고 다르다면, 1로 초기화 합니다.
과거 빈도보다 현재 빈도가 더 크다면, 갱신을 합니다. Duplicate라는 boolean값도 false로 정상 출력됩니다. 그러나 최빈값 빈도와 현재값 빈도와 같고 최빈값 자체가 다르다면 같은 빈도를 가지는 최빈값이 두개 발생한 것이므로 Duplicate 값을 true로 설정합니다.
결과 출력시 true면 -1을 출력하고, false라면 mode라는 최빈값 원소를 출력합니다.
import java.util.Arrays;
class Solution {
public int solution(int[] array) {
Arrays.sort(array); // 정렬
int mode = array[0]; // 최빈값
int modeCount = 1; // 과거 최빈값의 빈도
int count = 1; // 현재 최빈값의 빈도
boolean Duplicate = false;
for (int i = 1; i < array.length; i++) {
if (array[i] == array[i - 1]) {
count++; // 이전 값과 같을시 count +1
}
else {
count = 1; // 값이 다르면 초기화
}
// 최빈값 갱신
if(count > modeCount) {
modeCount = count;
mode = array[i]; // 최빈값 갱신
Duplicate = false;
}
// 최빈값 빈도와 현재값 빈도가 같고 현재 최빈값이 새로운 최빈값과 다를시
else if (count == modeCount && array[i] != mode) {
// 같은 빈도 최댓값이 나올시 true
Duplicate = true;
}
}
return Duplicate ? -1 : mode; // true면 -1, false면 mode 출력
}
}마리트 코테 (20:00 ~ 23:00)
대망의 마이리얼트립 코딩테스트를 진행했다.
더이상 미룰수 없었고... 그냥 부딪혀보기로 했다.
어려운것 같다.
23:00 ~
밥을 먹고 내일을 위해 재충전 시간을 가졌다.
