장문의 글이 될 예정입니다.
와.. 나는 이번 모임 문제가 교육받는 곳에서 보는 알고리즘 테스트보다 어려웠다... 1문제? 푼 거 같은데.. ㅠㅠ 분발하자.
문제 1번 strStr() 구현하기 (28. Implement strStr(), LeetCode, Java)
Implement strStr() - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
주어진 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;
}
}사실 이렇게 우아하게 풀지는 않았고 슬라이딩 윈도우 느낌만 내려고 좌우로 버려주고 추가해주고 이동시키면서 비교했는데 다른 사람들의 코드를 보니 이렇게 이퀄도 이용하고 스트링 빌더를 이용해서 앞에서부터 후려치는 게 매우 아름답다. 디큐를 이용해도 되지 않을까 싶지만 문자열 이니깐 복잡하니 그냥 저렇게 하는 게 아름답다.
다음
문제 2번 수열(백준 2559 , Java)
전형적인 투 포인터 문제이지만, 각 구간의 최대합을 구한다는 부분에서 지난번 공부한 카 데인 알고리즘을 적용하려고 했지만 이해부족인지 구현능력 부족인지 못풀었다... ㅠㅠ 카데인 알고리즘을 다시 공부해보자.
문제 가져오신 분의 코드를 보자.
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를 없애고 창문이 움직이듯이 구현했다 움직일 때마다 좌우로 계산해서 빼주는 것이다.
문제 3 카드 합체 놀이 (백준 15903, Java)
매번 가장 작은 카드 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를 이용할 텐데 이렇게 접근한다는 것 자체가 매우 신기한 접근법이었다. 지금 당장 나 자신에게 정렬 구현해보라고 하면 자신이 없는데... 블로그 글 작성하고 팬으로 한번 끄적여봐야겠다.
문제 4 큰 수 만들기(프로그래머스 , Java)
와 문제는 단순했지만 아이디어를 생각하기 꽤 어려웠다.. 반복문을 이용해 앞뒤로 비교해서 지워 나가는 것 을 키포인트로 잡고 왜냐하면 항상 큰 수는 제일 앞에 자리에 의해 결정되기 때문에 이렇게 생각했다. 코드를 작성해서 제출을 해보니 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);
}
}으응? 여기서 스택을 이렇게 쓴다고? 와 자료구조는 이렇게 이용하는구나라고 감탄만 나온다.. 현재 문자열을 뽑아서 스택에 들어있는 아이들과 비교하고 작다면 과감하게 버려준다. 물론 버려주는 카운트를 하면서 진행한다. 와.. 아름다운 코드다.
문제 5번 기지국 설치 (프로그래머스, Java)
문제를 이해하기는 어렵지 않다. 구현하는데 엄청 애먹었다.. ㅠㅠ 범위가 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;
}
}
문제 가져오신분의 코드에 정확하게 내가 말한 아이디어만 추가가 되어 구현 된 부분이다. 아이디어는 비슷한대 내가 구현한 코드가 조금더 빨랐다. 미리 처리를 해줘서 그런건가. 잘 모르겠지만 빠르면 좋은게 아닌가 ? 정신승리 하고 넘어가자.
이번 모임 문제의 난이도는 나에게 어려웠다. 투 포인터 그리디가 부족한 부분을 느끼는 하루였다.
매번 문제를 풀며 좌절하는데 이제 너무익숙해져 가는 내 자신이 참 그렇다.
다음 모임 에는 어떤 문제가 나올지 두렵다.. ㅋㅋ
모임에서 문제를 풀고 즉각적인 피드백 과 예외케이스 등을 알아가고 질문을 던지면서 어떤 방식으로 접근했는지 왜 그렇게 생각했는지 등의 이 접근법을 얻는것이 정말 도움이 많이 되는것 같다. 얻어가는 게 많은 하루였다.
긴글 읽어주셔서 감사합니다.
'PS > Algorithm' 카테고리의 다른 글
| 다익스트라 알고리즘(Dijkstra) (0) | 2022.07.21 |
|---|---|
| [5번째 알고리즘 모임] 4문제 (0) | 2022.07.11 |
| [3번째 알고리즘 모임] 4문제 (0) | 2022.06.25 |
| 순열 을 다양하게 돌아보자. (0) | 2022.06.20 |