아 o(logn) 꼴도 보기싫다 ㅋㅋㅋㅋ.. 지문이 제법 길지만, 뭐 대충 이거는 pivot 에 의해 정렬 이 된 상태의 배열이 주어진다. 위에 예시가 착하게 나와 있으니 예시를 보면 이해하기 쉽다. 음 ? 이해가 왜 미디엄 레벨 이지 ?
좌우 포인터 잡고 하나씩 줄여가기로 결정
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int idx = -1; // set default as -1
while (left <= right) {
if (nums[left] == target) {
idx = left;
break;
} else {
left++;
}
if (nums[right] == target) {
idx = right;
break;
} else {
right--;
}
}
return idx;
}
}
특별할것 하나 없는 코드이다. 말 그대로 -1 을 디폴트로 설정해서 좌우 번갈아 가면서 찾아준다. 주어진 문제에서 숫자는 고유하기 떄문에 이러한 방법이 가능하다.
다른사람들의 코드를 보자.
public class Solution {
public int search(int[] A, int target) {
int lo = 0;
int hi = A.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2; // 미드 값 구하기
if (A[mid] == target) return mid;
if (A[lo] <= A[mid]) {
//현재 미드값 과 레프트 값의 비교 만약 이게 성립이 된다면 현재 범위는 로테이트 된 값 이 있는 부분이다.
if (target >= A[lo] && target < A[mid]) {
hi = mid - 1; //로테이된 왼쪽 부분에 위치하는 조건이다.
} else {
lo = mid + 1; // 로테이트된 오른쪽 부분에 위치하는 조건이다.
}
} else {
if (target > A[mid] && target <= A[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return A[lo] == target ? lo : -1;
}
이 사람은 이분탐색 그대로 구현했다. 대신 미드 값에 따른 이동 포인터를 좌우 비교를 통해 현재 진행되는 방향이 로테이트 된 방향인지 아닌지를 모두 체크하는 if 문을 넣어 주었는데 비교적 코드가 직관적 이여서 가져왔다.
음 만약 1,2,3,4,5,6,7 이란 코드가 있고 4,5,6,7,0,1,2,3 이렇게 피벗 4 에 변경이 된다면 4 5 6 7 / 0 1 2 3 이렇게 나누어서 생각해 볼수 있다 여기서 찝은 미드의 값과 왼쪽 과 오른쪽 비교를 해주었을때 어느 부분을 찝었는 지 알수 있다. 또한 타겟을 이용해 범위를 명확히 줄여 나가는 것이 참 신기한 아이디어 같다.
주어진 num 범위 안에서 타겟 에 해당하는 범위를 출력하는것이다. 이미 정렬 되어진 상태이니 이분탐색으로 빠르게 해당 값을 찾고
그 값으로 부터 좌우로 증가하면서 알맞은 값을 찾는것이다.
코드를 보자.
class Solution {
public int[] searchRange(int[] arr, int target) {
int left = -1;
int right = -1;
int nLeft = 0;
int nRight = arr.length - 1;
int idx = -1;
while (nLeft <= nRight) {
int mid = nLeft + (nRight - nLeft) / 2;
if (arr[mid] < target) {
nLeft = mid + 1;
} else if (arr[mid] == target) {
idx = mid;
break;
} else {
nRight=mid-1;
}
}
if (idx == -1)
return new int[] { left, right };
left = idx;
right = idx;
while (arr[left] == target) {
if (left-1>=0 &&arr[left - 1] == target) {
left--;
} else {
break;
}
}
while (arr[right] == target) {
if(right+1 >= arr.length){
break;
}
if (right+1<arr.length && arr[right + 1] == target) {
right++;
} else {
break;
}
}
System.out.println(left + " " + right);
return new int[] { left, right };
}
}
left , right 는 -1 로 지정을 해주고 문제에서 못찾으면 -1 리턴 하라고 했으니 이니셜 지정 해주자. 가운데 값을 찾은 후 말그대로 while 돌려가며 왼쪽 끝 오른쪽 끝을 이동하며 찾는데 12 ms ~ 15ms 정도 나온다. 매우 느린 코드다 마음에 들지 않는다. 양쪽으로 이분탐색을 다시해봐도 별반 차이가 없다... ㅎㅎ
고수들의 코드를 봐보자.
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = findFirst(nums, target);
result[1] = findLast(nums, target);
return result;
}
private int findFirst(int[] nums, int target){
int idx = -1;
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] >= target){
end = mid - 1;
}else{
start = mid + 1;
}
if(nums[mid] == target) idx = mid;
}
return idx;
}
private int findLast(int[] nums, int target){
int idx = -1;
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] <= target){
start = mid + 1;
}else{
end = mid - 1;
}
if(nums[mid] == target) idx = mid;
}
return idx;
}
이분탐색 을 이렇게 반반 나눠서 한다. 와 미쳤다.. 생각 하지도 못했다.... 정형화된 이분탐색 에서 break else 에 변화를 주고 점점 가지치기 해나가는데 와... 멋진 코드이다.
public class Solution {
public int[] searchRange(int[] A, int target) {
int start = Solution.firstGreaterEqual(A, target);
if (start == A.length || A[start] != target) {
return new int[]{-1, -1};
}
return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
}
//find the first number that is greater than or equal to target.
//could return A.length if target is greater than A[A.length-1].
//actually this is the same as lower_bound in C++ STL.
private static int firstGreaterEqual(int[] A, int target) {
int low = 0, high = A.length;
while (low < high) {
int mid = low + ((high - low) >> 1);
//low <= mid < high
if (A[mid] < target) {
low = mid + 1;
} else {
//should not be mid-1 when A[mid]==target.
//could be mid even if A[mid]>target because mid<high.
high = mid;
}
}
return low;
}
}
와 이건 ㅋㅋㅋㅋㅋㅋ 아이디어의 발상이 참 대단하다. 찾고자 하는수에 +1 을 해서 그수를 찾고 그인덱스 -1 과 찾고자 하는 수 와 정말 멋진코드가 많다. 이걸보고 다시 내 코드보니 왜이리 구려보이 는지..... 내일 다시풀때는 이 코드로 작성해보자.
주어진 needle의 스트링이 haystack 내에 존재하는지 그렇다면 그에 대한 인덱스를 아니라면 -1을 출력하는 간단한 문제이다. 스터디 원 분들도 손쉽게 스트링을 잘 잘라서 이용해서 넣어주시면서 푸셨다.
// 1번 솔루션 1ms
class Solution {
public int strStr(String hay, String needle) {
if(needle.length() > hay.length())return -1; // 니들이 길다면 굳이 탐색해줄 필요없이 -1 뱉어줍니다.
if(needle.length() == hay.length()){ // 만약 서로의 길이가 같다면 ? 서로 문자열 비교해서 맞으면 0 리턴해줍니다.
if(cal(needle,hay)){
return 0;
}else{
return -1; // 아닌경우
}
}
for (int i = 0; i < hay.length()-needle.length()+1; i++) { //for 를 끝까지 이동할 필요 없이 needle 을 셀수있을만큼만 이동
String sub = hay.substring(i,i+needle.length()); //문자 잘라주기
if(cal(sub,needle)){ //넘겨줘서 트루면 현재 인덱스 반환
return i;
}
}
return -1; // for 를 다돌아도 함수가 종료 안된다면 -1
}
public boolean cal(String s1,String s2){ //스트링 2개를 가져와 비교해서 같으면 트루,폴스 리턴 해줌 생각해보니, eqaul 쓰면됨 ㅋㅋㅋ
for (int i = 0; i < s2.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)){
return false;
}
}
return true;
}
}
문자의 서브 스트링 을 해서 잘라서 비교해주는 방법을 생각했고, 이렇게 비교를 진행했다. 예외 케이스는 항상 신경 써주자 너희들의 길이가 매우 자유 로우니 잊어먹지 말자. 특별할 게 없는 코드이다. 이 문제의 연관 주제 중 하나가 투 포인터이다. 억지로 한번 넣어서 풀어보자.
class Solution {
public int strStr(String hay, String needle) {
if(needle.length() > hay.length())return -1;
int start = 0; //시작 점
int end = needle.length(); // 찾을 문자열 끝점
int answer = -1;
while(end <= hay.length()){
String sub = hay.substring(start,end); // 위와 유사하게 문자열 잘라줍니다,
if(checker(sub,needle)){ // 체커 말고 equal 쓰세요 ㅠㅠㅠㅠ
answer = start; // 인덱스 업데이트
break;
}
start++; // 아니면 ++해줍니다
end = start + needle.length(); //문자열 끝점도 업데이트
}
return answer;
}
public boolean checker(String s1 ,String s2){
for (int i = 0; i < s1.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)) return false;
}
return true;
}
}
포인터를 각각 앞뒤로 지정한 후 이동하면서 확인한다. 이 코드를 작성하다 보니 슬라이딩 윈도 가 떠오른다. 아낌없이 아이디어를 발휘해 작성하자.
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() > haystack.length())return -1;
if(needle.length() == 0 )return 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < needle.length(); i++) {
sb.append(haystack.charAt(i)); //0번부터 추가해줍니다.
}
if(sb.toString().equals(needle)){
return 0 ; //같으면 0번 시작이니 고대로 리턴해줍니다.
}
int leftWindow = 0, rightWindow = needle.length()-1; // 윈도우 세팅 해줍니다.
while(rightWindow < haystack.length()){
sb.delete(0,1); //빌더에 요렇게 앞에서 지울수 있는 편의기능 !
rightWindow++; // 윈도우 오른쪽으로 이동 시켜줍니다.
leftWindow++;
if(rightWindow > haystack.length()-1) break; //while 에서 범위에 맞게 들어오더라도 안에서 추가를 했기때문에 다시 확인해야합니다.
//안하면 인덱스 나가요
sb.append(haystack.charAt(rightWindow)); // 늘린만큼 추가해주어 현재 스트링 갯수를 유지해 줍니다.
if(sb.toString().equals(needle)) return leftWindow;
}
return -1;
}
}
사실 이렇게 우아하게 풀지는 않았고 슬라이딩 윈도우 느낌만 내려고 좌우로 버려주고 추가해주고 이동시키면서 비교했는데 다른 사람들의 코드를 보니 이렇게 이퀄도 이용하고 스트링 빌더를 이용해서 앞에서부터 후려치는 게 매우 아름답다. 디큐를 이용해도 되지 않을까 싶지만 문자열 이니깐 복잡하니 그냥 저렇게 하는 게 아름답다.
전형적인 투 포인터 문제이지만, 각 구간의 최대합을 구한다는 부분에서 지난번 공부한 카 데인 알고리즘을 적용하려고 했지만 이해부족인지 구현능력 부족인지 못풀었다... ㅠㅠ 카데인 알고리즘을 다시 공부해보자.
문제 가져오신 분의 코드를 보자.
package backjoon2559;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, K;
static int[] temperatures;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0]); // 온도를 측정한 전체 날짜 수
K = Integer.parseInt(s[1]); // 합을 구하기 위한 연속적인 날짜의 수
temperatures = new int[N]; // 측정한 온도를 저장하기 위한 배열
String[] s_temperature = br.readLine().split(" ");
int max_temp = 0;
for (int i = 0; i < N; i++) {
temperatures[i] = Integer.parseInt(s_temperature[i]);
if (i < K) {
max_temp += Integer.parseInt(s_temperature[i]);
}
}
// N = 10, K = 5 일 때
// 위에서 temperatures[0] ~ temperatures[4] 까지 더한 값을 max_temp에 저장하고 temp_sum에 넣어 줌
// 1. 그리고 둘째 날부터 시작해서 temperatures[1] ~ temperatures[5] 까지의 합을 temp_sum에 넣어주고 첫째 날짜는 temp_sum에서 빼준 후
// 2. max_temp와 비교해서 더 큰 값을 업데이트
// 1번, 2번을 for문이 끝날 때 까지 반복
int temp_sum = max_temp;
for (int i = 1; i < N - K + 1; i++) {
int p1 = i - 1;
int p2 = K + i - 1;
temp_sum += -temperatures[p1] + temperatures[p2];
max_temp = Math.max(max_temp, temp_sum);
}
System.out.println(max_temp);
}
}
스터디장 님답게 주석 이 매우 깔끔하다. 핵심만 보고 간다면 좌우측으로 빼주고 더해주는 값을 현재 값에 더해주고 최댓값을 찾아가면서 업데이트를 한다. 입력을 받아올 때 저렇게 for문을 이용해 가장 첫 번째 경우를 미리 계산해주는 모습이 인상 깊다. 지난번 전선 때도 그러시더니 이건 훔쳐야겠다. 설명을 듣다 보니 이것도 슬라이딩 윈도 가 될 것 같은 느낌이다. 바로 구현해주자. (사실 30분 정도 푼 거 같다..ㅋㅋ)
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int[] arr = new int[Integer.parseInt(inputs[0])];
int day = Integer.parseInt(inputs[1]);
int curSum = 0;
int max = 0;
String[] input2 = br.readLine().split(" ");
for (int i = 0; i < input2.length; i++) {
arr[i] = Integer.parseInt(input2[i]);
if (i < day) {
curSum += arr[i];
max += arr[i];
}
}
for (int i = day; i < arr.length; i++) {
curSum += (arr[i] - arr[i - day]);
max = Math.max(curSum, max);
}
System.out.println(max);
}
}
p1 p2 없이 그냥 슬라이딩 윈도 느낌으로 구현해 봤다. for 문으로 입력받아오면서 미리 계산하기 매우 좋다.
특별할 것 없이 위의 내용 중 p1, p2를 없애고 창문이 움직이듯이 구현했다 움직일 때마다 좌우로 계산해서 빼주는 것이다.
매번 가장 작은 카드 2장을 골라 주어진 연산만큼 더해주고 대입해주는 연산이다. 그 이후 결과 값을 출력! 유일하게 푼 문제다...ㅋㅋ
최초 접근을 arraylist를 이용해서 작성하다 보니 sort를 중복해서 계속 사용해야 된다는 사실을 깨닫고 priorityQueue로 전환했다. 자동으로 해주는데 손 아프게 해주지 말자.
코드를 보자.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = bf.readLine().split(" ");
int cnt = Integer.parseInt(inputs[1]);
PriorityQueue<Long> q = new PriorityQueue<>();
String[] input = bf.readLine().split(" ");
for (int i = 0; i < input.length; i++) {
q.offer(Long.parseLong(input[i]));
}
for (int i = 0; i < cnt; i++) {
long first = q.poll();
long second = q.poll();
q.add(first + second);
q.add(first + second);
}
long rs = 0;
while (!q.isEmpty()) {
rs += q.poll();
}
System.out.println(rs);
}
}
int로 했다가 범위 오류 나서 long으로 다급하게 수정했다. 우리의 아름다운 큐가 이미 정렬을 해주니 q.poll을 두 번 실행하고 더해준 값을 2번 넣어주면 된다. 심플하고 간단하다.
문제 가져오신 분은 다르게 작성하셨다. 색다른 방법이니 확인해보자.
import java.io.*;
import java.util.*;
public class Practice082 {
// 풀이 1 - 0, 1번 원소를 그때마다 삽입정렬
// 메모리 14632 KB, 시간 168ms
public static void solution(int n, int m, long[] arr) {
long answer = 0;
// n이 2면 걔들 둘만 계속 돌리면 됨
if(n == 2) {
for (int i = 0; i < m; i++) {
long tmp = arr[0] + arr[1];
arr[0] = tmp;
arr[1] = tmp;
}
System.out.println(arr[0] + arr[1]);
return;
}
// m이 0이면 배열 더하고 끝
if(m == 0) {
for (long item : arr) {
answer += item;
}
System.out.println(answer);
return;
}
// 배열 정렬
Arrays.sort(arr);
// m번 수행
for (int i = 0; i < m; i++) {
// 0, 1번 원소를 tmp로 업데이트한 후 매번 정렬을 하기 때문에
// 계속 0번, 1번을 더하면 됨
long tmp = arr[0] + arr[1];
arr[0] = tmp;
arr[1] = tmp;
sort(arr, 1); // 1번 인덱스에 있는것 정렬
sort(arr, 0); // 0번 인덱스에 있는것 정렬
}
// 배열 모두 더해서 출력
for (long item : arr) {
answer += item;
}
System.out.println(answer);
}
// 정렬 메서드
public static void sort(long[] arr, int startIdx) {
// 인덱스가 배열길이 - 1까지 (그 뒤에거랑 비교를 하니 -1까지)
while(startIdx < arr.length - 1) {
if(arr[startIdx] > arr[startIdx + 1]) {
// 스왑
long tmp = arr[startIdx];
arr[startIdx] = arr[startIdx + 1];
arr[startIdx + 1] = tmp;
} else { // 뒤에 원소가 더 크면 정렬 종료. (오름차순 정렬되어있기 때문)
break;
}
startIdx++;
}
}
우아한 정렬 메서드를 보자. 직접 구현해서 삽입 정렬을 실행해 주었다. 보통 다 sort를 이용할 텐데 이렇게 접근한다는 것 자체가 매우 신기한 접근법이었다. 지금 당장 나 자신에게 정렬 구현해보라고 하면 자신이 없는데... 블로그 글 작성하고 팬으로 한번 끄적여봐야겠다.
와 문제는 단순했지만 아이디어를 생각하기 꽤 어려웠다.. 반복문을 이용해 앞뒤로 비교해서 지워 나가는 것 을 키포인트로 잡고 왜냐하면 항상 큰 수는 제일 앞에 자리에 의해 결정되기 때문에 이렇게 생각했다. 코드를 작성해서 제출을 해보니 2개가 시간 초과 가 나는 것이다. 보고 가자.
class Solution {
public String solution(String number, int k) {
String answer = "";
StringBuffer sb = new StringBuffer(number);
while (sb.length() + k != number.length()) {
for (int i = 1; i < sb.length(); i++) {
if (sb.charAt(i - 1) < sb.charAt(i)) {
sb.deleteCharAt(i - 1);
break;
}
}
}
return sb.toString();
}
}
빌더를 이용해 앞에서부터 하나씩 잘라줄 생각을 했다. 크다면 자르고 아니라면 브레이크를 넣어주면서 계속 돌린다. 이 코드의 결점이 있다. 바로 821인데 1개를 지워야 한다. 위와 같은 로직이라면 무한 반복을 돈다. 앞에서 뒤로만 비교하는 경직된 코드이기 때문에 어쩔 수가 없다... 고쳐보려고 노력했으나. while 문과 for의 전체적인 부분을 수정해야 해 다른 우아한 코드를 보여주려고 한다.
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder(number);
for (int i = 0; i+1 < sb.length() && k>0; i++) {
if(sb.charAt(i) < sb.charAt(i+1)) {
sb.deleteCharAt(i);
i=-1;
k--;
}
}
if(k!=0)
sb.delete(sb.length()-k, sb.length());
return sb.toString();
}
}
ㅋㅋㅋㅋㅋ for 문을 이용해서 그냥 한번 훑어주고 남은 개수만큼 뒤에서 잘라주면 된다 왜 와이? 앞뒤로 정렬된 상태이기 때문이다. for의 조건 상태가 특이한데 천천히 뜯어보면 i+1 은 sb.length 보다 작다 뒤에 수와 비교하기 위한 조건이고 추가로 k 가 0보다 클떄 까지 만 반복 한다. 저걸 못해서 while을 쓴 나 자신을 반성한다... 그래도 아이디어가 틀리지 않았다는 것에 조그만 위안을 삼고
코드 가져오신 분의 황홀한 코드를 보자.
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
int curK = k;
for (int i = 0; i < number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && curK-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i = 0; i < number.length()-k; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
으응? 여기서 스택을 이렇게 쓴다고? 와 자료구조는 이렇게 이용하는구나라고 감탄만 나온다.. 현재 문자열을 뽑아서 스택에 들어있는 아이들과 비교하고 작다면 과감하게 버려준다. 물론 버려주는 카운트를 하면서 진행한다. 와.. 아름다운 코드다.
문제를 이해하기는 어렵지 않다. 구현하는데 엄청 애먹었다.. ㅠㅠ 범위가 2억이라는 엄청난 범위가 주어지기 때문에 for 문이 아닌 뭔가 색다른 접근법이 필요하다고 생각했고 현재 와이파이 위치에 대한 거리를 이용해 최대 설치 개수를 구해주면서 비어있는 부분 체크를 하려고 했으나 시간 부족 능력 부족으로 구현에 실패했다.
모임 종료 이후 혼자 구현을 마무리했다.
코드를 보자.
class Solution {
public int solution(int n, int[] stations, int w) {
int current = 1, answer = 0,standard = (w*2+1); //자주사용될 아이들 미리 변수선언했다.
for (int i = 0; i < stations.length; i++) { // 범위가 2억이지 주어지는 와이파이가 2억이 아니다. 포문 과감하게 돌리자.
if (current < stations[i] - w) { //와이파이는 정렬된 상태로 들어오기 때문에 이렇게 연산 가능하다.
int left = stations[i] - w - 1 - current + 1; //와이파이가 터지는 왼쪽으로 부터의 거리
answer += left / standard; // 나눗셈을 이용해 정답에 더해주자 왜? 이게 와이파이 설치 최대거리이니깐
if (left % standard != 0) // 이렇게 한이후 나머지 처리를 해주어야한다.
answer++; //0이아니라면 짜잘한 애들이 있으니 추가를 해주고 , 현재 포인트도 업데이트
current = stations[i] + w + 1;
} else { //아니라면 현재포인트만 업데이트한다.
current = stations[i] + w + 1;
}
}
// 위의 기지국을 이용해 갈수 있는 최대 거리까지 이동했으나 n 보다 모자른 경우에 대한연산이다.
// 위와동일한 개념으로 작성했다.
if (current <= n) {
int left = n - current + 1;
answer += left / standard;
if (left % standard != 0)
answer++;
}
return answer;
}
}
왼쪽에 보는 이미지와 같이 저기 사이의 공간을 구해 나눠주는 곳에서 착안해 위와 같이 작성하였다.
문제 가져오신 분의 보다 직관적인 풀이를 보자 이거는 이해를 못 할 수가 없다.
// 기지국 설치
// https://programmers.co.kr/learn/courses/30/lessons/12979
import java.util.*;
public class T3 {
public static int solution(int n, int[] stations, int w) { // 16, [9], 2
int cnt = 0; // 기지국 개수
int position = 1; // 1동부터 시작
int idx = 0; // stations[] 내의 idx
// 전파가 터지는 최대 위치 position
while(position <= n){
// 기지국 설치 하지 않아도 되는 상황
// 현 위치 position은 station[idx]으로부터 전파가 터지는 상황이다.
if(idx < stations.length && stations[idx] - w <= position ){
// position에 2w + 1만큼 온전히 더할 수 없는 상황이니까 position을 변경한다.
// stations[idx] - w 부터 stations[idx] + w 까지 전파 터지니까 그 다음으로 이동
position = stations[idx] + w + 1;
++idx;
// System.out.println("position: " + position + ", idx: "+ idx);
continue;
}
// 기지국 설치해야하는 상황
++cnt;
position += 2 * w + 1;
// System.out.println("position: " + position + ", cnt: " + cnt);
}
return cnt;
}
public static void main(String[] args){
int[] stations = {4, 11};
System.out.println(solution(11, stations, 1)); // 3
stations = new int[]{9};
System.out.println(solution(16, stations, 2)); // 3
stations = new int[]{3, 7, 9};
System.out.println(solution(16, stations, 1)); // 4
}
}
전체적인 맥락은 매우 비슷하다. while을 이용해서 앞에부터 포인터를 이동해가며 설치를 해야 한다면 cnt를 추가해주는 것이다. 이 문제 출제자 님의 설명을 듣고 한 가지 의문이 들었다 굳이 앞에부터 할 이유가 없다고 생각했다. 과감하게 넘기고 연산을 줄일 수 있는 방법에 내 아이디어를 적용한다면 더 빠르게 구현 가능하겠다 싶어 여쭤보니 철저하신분 이라 비슷한 아이디어로 작성한 코드가 있다고 보여주셨다.
class Solution {
public int solution(int n, int[] stations, int w) { // 11, [4, 11] , 1
int left = 0; //기지국 범위 외 왼쪽
int right = 0; //기지국 범위 외 오른쪽
int baseL = 0; //기지국 범위 내 왼쪽
int baseR = 0; //기지국 범위 내 오른쪽
int result = 0;
for(int i = 0; i < stations.length; ++i){
int base = stations[i]; // 4, 11
left = baseR; // 왼쪽 값은 기지국 내의 오른쪽 값, 나중에 개수를 구하기위해 굳이 +1하지않는다.
baseL = base - w;
baseR = base + w; // 너비 w에 따른 기지국의 범위 baseL ~ baseR
if(baseL < 0 ) baseL = 0;
if(baseR > n ) baseR = n; // 배열의 범위를 초과할 때 한정시켜준다.
right = baseL - 1;
if(right < 0) continue;
if(left == right) continue; // 같다면 기지국 사이가 커버 되었을 때이다. ??
if(left > right) continue;
double temp = (double) (right - left) / ((2 * w) + 1);
if(temp % 1 == 0) result += (int) temp; // temp가 정수 일 때
else result += (int) temp + 1;
}
if(baseR != n){ // 모두 처리한 후, baseR은 n이 되어야 한다.
double temp = (double) (n - baseR) / ((2 * w) + 1);
if(temp % 1 == 0) result += (int) temp;
else result += ((int) temp) + 1 ;
}
return result;
}
}
문제 가져오신분의 코드에 정확하게 내가 말한 아이디어만 추가가 되어 구현 된 부분이다. 아이디어는 비슷한대 내가 구현한 코드가 조금더 빨랐다. 미리 처리를 해줘서 그런건가. 잘 모르겠지만 빠르면 좋은게 아닌가 ? 정신승리 하고 넘어가자.
이번 모임 문제의 난이도는 나에게 어려웠다. 투 포인터 그리디가 부족한 부분을 느끼는 하루였다.
매번 문제를 풀며 좌절하는데 이제 너무익숙해져 가는 내 자신이 참 그렇다. 다음 모임 에는 어떤 문제가 나올지 두렵다.. ㅋㅋ 모임에서 문제를 풀고 즉각적인 피드백 과 예외케이스 등을 알아가고 질문을 던지면서 어떤 방식으로 접근했는지 왜 그렇게 생각했는지 등의 이 접근법을 얻는것이 정말 도움이 많이 되는것 같다. 얻어가는 게 많은 하루였다.
주어진 숫자 배열 안에 연속된 부분 배열 중 가장 큰 값을 리턴하면 되는 심플 한 문제이다. 문제만 심플하지 생각할 것이 꽤 많은 문제였다.
문제풀이를 하면서 다양하게 접근했다. 저기 주어진 예시들 은 길고 특별한 케이스이니 심플하게 만들어서 생각해보자.
[-3,2,3,-1]
뭐 있나 1번 부터 다 쓰자...
1번 인덱스 : 뭐 할 게 없다 그냥 리턴해줘야 한다...-3
2번 인덱스 : [-3], [2] / [-3,2] 오 뭔가 느낌이 온다.
3번 인덱스 : [-3], [2], [3] / [-3,2], [2,3] / [-3,2,3] 왔다, 약간 dp 스럽게 풀어야 하는 건가 싶었다.
현재 인덱스까지 진행된 것 중 버릴 거 버리면서 진행한다면 나쁘지 않은 효율이 나올 것 같았다.
뭘 어떻게 버려 주어야 할까 고민하다가, 현재 진행 중인 값에 다음 값을 더해서 그 값이 다음값 보다 작다면? 뒤에 까지 다 더한 것은 쓸모가 없어진다.. -2 1 -3을 예로 들어보자 -2 1 => -1 인 상태에서 -3 을 더하면? -4인데 우리는 연속된 수를 구해야 하니 버리자 대신 저 앞에 까지 더해진 부분을 따로 기록을 해 두어야 할 것이다.
class Solution {
public int maxSubArray(int[] arr) {
if(arr.length == 1) return arr[0];
int p1 = 0;
int p2 = 1;
int maxSum = arr[p1];
int currentSum = arr[p1];
while(p2<arr.length){
int nextCur = currentSum + arr[p2];
if(nextCur < arr[p2]){
p1 = p2;
currentSum = arr[p2];
}else{
currentSum = nextCur;
}
maxSum = Math.max(maxSum,currentSum);
p2++;
}
return maxSum;
}
}
오늘 two pointer 강의를 듣고 와서 그런가 엄청 비슷하게 푼 거 같은데 허점이 존재한다.... p1을 선언해 놓고 쓰지도 않는다...... 고수들의 코드를 보자.
class Solution {
public int maxSubArray(int[] nums) {
int currSum = nums[0], result = nums[0];
for (int i=1;i<nums.length;i++){
currSum = Math.max(nums[i], currSum + nums[i]);
result = Math.max(result, currSum);
}
return result;
}
}
호 올리 몰리...... math.max를 이렇게 선언하면서 깔끔하게 for 반복문으로 해결해 버리는 아름다운 코드이다. 조금 더 디스커스를 둘러보면 Kadane's Algorithm 이란 글로 엄청 아름답게 써놓은 글이 있다. 따로 퍼오기 좀 그러니 링크를 첨부하겠다.
개괄적으로 설명을 하자면 위의 풀이법 그대로가 카 데인 알고리즘이다. 글 설명 10줄보다 그림 이 훨씬 보기 편하니 아래 링크로 이동해서 확인하면 더 도움 이 됩니다. 보러 가기
이 사람이 작성한 글에 의하면 어느 부분이던 합이 - 에 도달한다면, 이걸 계속 가지고 있을 의미가 없기 때문에 합을 0으로 초기화시켜준다고 한다.
-2 1 -3 4 -1 2 1 -5 4 (예시 1번)
i = 0 일 때 합은 -2 가 되고 , 최대 합은 -2 , 합이 0 보다 작기 때문에 현재 합은 0으로 초기화된다.
i = 1 일 때 합은 0+1(현재 합을 0 으로 초기화 시켜서 전 인덱스에서) 이되고, 합이 1 이된다 최대합은 1
i = 2 일 때 합은 1 -3 -2 가 되고 최대합은 1, 현재합은 0으로 초기화된다 왜 ? 0보다 작아서
i = 3 일때 합은 0+4 4 가되고 최대합은 4, 현재합은 4 가된다
이런 식으로 쭉쭉 이어나가면 된다. 위 링크에 더 자세히 설명되어 있으니 참고 바랍니다.!!
자세히 다시 보니 브루트 포스 에서 내가 느낀 그 디피 느낌이 이 카데인 알고리즘 이였다 그냥 디피라고 하면 될걸 왜 굳이 이름을 이렇게 붙이는지 다시보니 도둑이 집터는 문제랑 매우 유사하다고 생각된다...... 현재 합과, 현재 인덱스 중 큰 것, 또 맥스 값과 큰 것을 비교하는 법 왜 항상 모든 블로그 혹은 유튜브 비디오에서 항상 브루트 포스를 먼저 하라고 하는지 다시 한번 느끼는 문제였다..
주어진 단어 를 3조각으로 나눠주고 그 조각의 역순을 이어 붙여 사전 순서로 했을때 제일 첫번쨰 단어를 반환하라는 문제의 조건이다.
제일 처음 접근했던 나의 방법은 두개의 인덱스를 두어 가장 작은 알파벳을 찾아가면서 업데이틀 해가며 단어를 나눈다면 제일 작은 단어를 찾을수 있다고 생각을했다.
즉 "mobitel" => b가 제일 작다 "mob" 나눠주고 , b다음 부터 시작점으로 다음 작은 알파벳을찾고 또 업데이트해주고 하면 예제의 있는답이 나온다. ㅋㅋㅋㅋ 틀렸다.
통과못한 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = bf.readLine();
bf.close();
StringBuilder sb = new StringBuilder();
char[] arr = s.toCharArray();
int start = 0;
int end = 0;
while (sb.length() != s.length()) {
int minIdx = 0;
char minChar = 'z' + 1;
for (int i = start; i < arr.length; i++) {
if (arr[i] < minChar) {
minChar = arr[i];
minIdx = i;
}
}
end = minIdx;
for (int i = end; i >= start; i--) {
sb.append(arr[i]);
}
start = minIdx + 1;
}
System.out.println(sb.toString());
}
}
"caba" 이런경우 acab 를 반환한다. abac 가 되어야 하는데... 그래서 생각한 두번째 방법이 나눠준 것들을 list 에 집어넣고 소팅후 이어붙혀주기로 했는데 ... 이것도 실패했다... ㅠㅠ 최후 의 보루 이중 for 문 으로 선택
패스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = bf.readLine();
bf.close();
List<String> result = new ArrayList<>();
String[] willAdd = new String[3];
for (int i = 1; i < s.length() - 1; i++) {
for (int j = i + 1; j < s.length(); j++) {
willAdd[0] = s.substring(0, i);
willAdd[1] = s.substring(i, j);
willAdd[2] = s.substring(j, s.length());
String rs = "";
for (String x : willAdd) {
StringBuilder sb = new StringBuilder(x);
rs += sb.reverse().toString();
}
result.add(rs);
}
}
Collections.sort(result);
System.out.println(result.get(0));
}
}
패스했다.... 아니 이게 왜 되는거지,,, 곰곰히 생각을 해보니 알파벳 최대 50 개 2중 포문 돌아도 2500 번 나머지 몇개 연산한다고 하더라도 2초 안에 완전 넉넉하게 해결이 되더라 ... 이중포문 은 나에게 안좋은 인식이 있는데 이중포문이 나쁜게 아니라 문제범위 를 생각 못하고 코드갈긴 내가 나쁜놈 이였다...
