흰색기린

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://programmers.co.kr/learn/courses/30/lessons/81301

Think🤔

영어로 one5seveneight이 들어오면 1578 을 반환한다.

문자열로 s가 들어온다.. 어떻게 반환하면 좋을까?

앞글자씩 따 보기도 하고, 글자 수의 패턴을 찾다가.. charAt으로 뽑으면 어떨까 해서 아스키코드표를 참고했다.숫자 0~9 까지는 48~57 번호이고 영단어는 소문자이므로 97~122 까지 A부터 오름차순이다.그럼 charAt의 값이 48~57 사이면 그냥 넣어주고 만약에 소문자 번호 라인에서 걸리면 그것을 판별한다.근데 판별을 어떻게 할까?one는 111,110,101 이렇게 나오는데.. 자칫하다가는 반복문을 돌렸을 때 null포인트 익셉션이 발생하기 마련이다..

0은 z(122)부터 시작1은 o(111)2,3 은 t(116)4,5 는 f(102)6,7은 s(115)8은 e(101)9는 n(110) 이렇게 시작한다.

그러면 두개씩 나오는 2,3 그리고 4,5 그리고 6,7을 처리해줘야 한다.

for문으로 짜면 i는 항상 1씩밖에 증가하지 않으므로 while문으로 작성한다.

두 개씩 나오는 구문을 처리할 때는

two와 three를 if문으로 작성한다고 예를 들자면,

t까지는 같으므로 두 번째 char가 w(119)이면 뒤를 안 봐도 된다 무조건 two이기 때문!

class Solution {
    public int solution(String s) {
        int size = s.length();
        int i=0;
        
        String tmp = "1";
        while(i>size){
            if(s.charAt(i) > 47 && s.charAt(i) < 58){
                tmp+=s.charAt(i);
                i++;
            }else if(s.charAt(i) == 122){
                tmp+="0";
                i+=4;
            }else if(s.charAt(i) == 111){
                tmp+="1";
                i+=3;
            }else if(s.charAt(i) == 101){
                tmp+="8";
                i+=5;
            }else if(s.charAt(i) == 110){
                tmp+="9";
                i+=4;
            }else if(s.charAt(i) == 116){
                if(s.charAt(i+1) == 119){ // w 119
                    tmp+="2";
                    i+=3;
                }else{
                    tmp+="3";
                    i+=5;
                }
            }else if(s.charAt(i) == 102){
                if(s.charAt(i+1) == 111){
                    tmp+="4";
                    i+=4;
                }else{
                    tmp+="5";
                    i+=4;
                }
            }else if(s.charAt(i) == 115){
                if(s.charAt(i+1) == 105){
                    tmp+="6";
                    i+=3;
                }else{
                    tmp+="5";
                    i+=5;
                }
            }
        }
        int answer = Integer.parseInt(tmp);
        
        return answer;
    }
}

처음 작성한 코드이다.

String tmp = ""; 로 초기화하면 널 포인트 익셉션이 찍힌다.

이걸 작성하면서 while문을 들여다보니 부등호 방향이 틀렸다..

부등호 방향을 고쳐주고 실행헀는데 마지막 charAt비교하는 곳에서도 에러가 있었음 seven은 7인데

5를 넣어줘서 테스트 케이스에 맞지 않게 들어갔다.

Solution✍

class Solution {
    public int solution(String s) {
        int size = s.length();
        int i=0;
        
        String tmp = "";
        while(i<size){
            if(s.charAt(i) > 47 && s.charAt(i) < 58){
                tmp+=s.charAt(i);
                i++;
            }else if(s.charAt(i) == 122){
                tmp+="0";
                i+=4;
            }else if(s.charAt(i) == 111){
                tmp+="1";
                i+=3;
            }else if(s.charAt(i) == 101){
                tmp+="8";
                i+=5;
            }else if(s.charAt(i) == 110){
                tmp+="9";
                i+=4;
            }else if(s.charAt(i) == 116){
                if(s.charAt(i+1) == 119){ // w 119
                    tmp+="2";
                    i+=3;
                }else{
                    tmp+="3";
                    i+=5;
                }
            }else if(s.charAt(i) == 102){
                if(s.charAt(i+1) == 111){
                    tmp+="4";
                    i+=4;
                }else{
                    tmp+="5";
                    i+=4;
                }
            }else if(s.charAt(i) == 115){
                if(s.charAt(i+1) == 105){
                    tmp+="6";
                    i+=3;
                }else{
                    tmp+="7";
                    i+=5;
                }
            }
        }
        int answer = Integer.parseInt(tmp);
        
        return answer;
    }
}

replaceAll을 이용해서 문자를 치환해주는 메서드가 있었다..

왜 생각하지 못했을까 .. 흑 엄청 간단하게 짤 수 있었다 한번 만들어 보도록 하자..

class Solution {
    public int solution(String s) {
        
        s = s.replaceAll("zero","0");
        s = s.replaceAll("one","1");
        s = s.replaceAll("two","2");
        s = s.replaceAll("three","3");
        s = s.replaceAll("four","4");
        s = s.replaceAll("five","5");
        s = s.replaceAll("six","6");
        s = s.replaceAll("seven","7");
        s = s.replaceAll("eight","8");
        s = s.replaceAll("nine","9");
        
        int answer = Integer.parseInt(s);
        
        return answer;
    }
}

Review🤩

while문의 중요성을 알았고, 문제를 풀려고 먼저 노트에 작성하는 것이 좋다는 것을 느꼈다. 

replace,replaceAll 을 기억하자..!

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://programmers.co.kr/learn/courses/30/lessons/42840

Think🤔

1번 수포자는 12345 12345 가 반복

2번 수포자는 21 23 24 25 21 23 24 25 반복 

3번 수포자는 33 11 22 44 55 가 반복

문제의 정답은 1,2,3,4,5 중 하나이다.

answer[] 배열로 문제의 정답을 파라미터 값으로 준다.

문제의 답이 [1,2,3,4,5] 가 나왔으면 수포자 1이 모든 문제를 맞혔으므로 return 1을 해준다.

문제가 [1,3,2,4,2]가 나왔으면 모두 2문제씩 맞춰서 [1,2,3]을 배열로 반환한다.

정해진 패턴이 있으므로 패턴을 사용해도 된다.

지금 5개의 숫자가 반복되는 것을 확인할 수 있다. 이것을 이용하자!

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int a=0; // 1번 수포자
        int b=0;; // 2번 수포자
        int c=0;; // 3번 수포자
        
        // a패턴,b패턴,c패턴
        int acnt = 1;
        int[] bp = {2,1,2,3,2,4,2,5};
        int bcnt = 0;
        int[] cp = {3,3,1,1,2,2,4,4,5,5};
        int ccnt = 0;
        
        for(int i=0; i<answers.length; i++){
            if(acnt == answers[i]){
                a++;
            }
            acnt++;
            
            if(bp[i] == answers[i]){
                b++;
            }
            bcnt++;
            
            if(cp[i] == answers[i]){
                c++;
            }
            ccnt++;
            
            if(acnt == 5){acnt = 1;}
            if(bcnt == 8){bcnt = 0;}
            if(ccnt == 10){ccnt = 0;}
        }
        
        int bestscore = Math.max(a,Math.max(b,c));
        
        ArrayList answer = new ArrayList();
        
        if(a == bestscore && b == bestscore && c == bestscore){
            answer.add(1);
            answer.add(2);
            answer.add(3);
        }if(a > b && a > c){
            answer.add(1);
        }else if(b > a && b > c){
            answer.add(2);
        }else if(c > a && c > b){
            answer.add(3);
        }else if(a == b && a > c){
            answer.add(1);
            answer.add(2);
        }else if(a == c && a > b){
            answer.add(1);
            answer.add(3);
        }else if(b == c && b > a){
            answer.add(2);
            answer.add(3);
        }
        
        int[] arr = new int[answer.size()];
        
        for(int i=0; i<answer.size(); i++){
            arr[i] = (int)answer.get(i);
        }
        
        return arr;
    }
}

경우의 수를 다 적어봤다.. 이렇게 하면 테스트 코드 2~3개는 통과할 수 있지만 런타임이 길어서 나머지 테스트 케이스를 통과하지 못했다. 물론 통과할 거라고 생각도 하지 않았음..

이 코드를 줄여야 한다. 공통되는 부분이 많다.

Solution✍

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int a[] = {1,2,3,4,5};
        int b[] = {2,1,2,3,2,4,2,5};
        int c[] = {3,3,1,1,2,2,4,4,5,5};
        
        int score[] = {0,0,0};
        for(int i=0; i<answers.length; i++){
            if(a[i%5] == answers[i]){
                score[0]++;
            }
            if(b[i%8] == answers[i]){
                score[1]++;
            }
            if(c[i%10] == answers[i]){
                score[2]++;
            }
        }
        
        // 최고 점수
        int best =  Math.max(score[0],Math.max(score[1],score[2]));
        
        ArrayList<Integer> arr = new ArrayList();
        
        // i+1을 해줘야지 1,2,3 이렇게 가능
        for(int i=0; i<score.length; i++){
            if(best == score[i]){
                arr.add(i+1);
            }
        }
        
        int[] answer = new int[arr.size()];
        
        for(int i=0; i<arr.size(); i++){
            answer[i] = arr.get(i);
        }
        
        return answer;
    }
}

패턴을 쪼개줬고, 하나하나 돌아가던 변수들을 i%5, i%8로 각각의 나머지를 구함으로써 계속 돌 수 있게 만들었다.

최고 점수는 Math함수로 구했고,

score 배열을 이용해서 비교했다, 변수였으면 세개를 비교해야 했으므로 코드가 길어졌던 것이었다.

ArrayList를 사용할 수밖에 없는 이유는 배열은 크기를 만들면 리턴 값에 [1]이 아닌 [1,0,0]이런 식으로 들어가기 때문이다.

또 중요한 건, arr.add(i+1) 괄호 안의 i+1 부분이다 그냥 i를 넣어주게 되면 0,1,2가 들어가게 되는데 수포자 1,2,3이 존재하지 수포자 0,1,2가 존재하는 것은 아니다.

우리가 return 해 줄 answer의 사이즈를 arr 사이즈로 만들면 딱 맞는 크기의 배열이 나온다.

Review🤩

나머지를 이용해서 코드를 간결화시킬 수 있었고, 컬렉션 리스트를 상황에 맞게 잘 쓰면 좋을 것 같다.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://leetcode.com/problems/cousins-in-binary-tree/

Think🤔

주어진 x,y의 노드 위치가 같으면 true를 반환하는 문제이다.

1. q를 먼저 만든다.

2. root를 q에 담아준다.

3. q가 빌떄까지 돌아준다.

4. 노드의 층(?)이랑 left right가 같은지 판별 

4번까지 적는데 세 번째의 경우는 위치가 같은데도 false가 나왔다. 2에 자식이 있어서 일까?

문제를 다시 살펴본 결과 부모가 달라야 한다.

부모도 비교를 해줘야 함.

5. 부모가 같은지를 어떻게 판별할까?

6. boolean 체크를 이용해서 처음에 판별을 먼저 한다. left right가 같으면 바로 false를 반환.

 이렇게 하면 같은 부모를 가질 수 없게 되고, 다음을 판별하면 된다.

7. 변수를 더 만들까 하다가 주어진 파라미터 x,y를 이용하기로 했다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        
        Queue<TreeNode> q = new LinkedList();
        
        q.offer(root);
        
        int count = 0; // 처음 0층
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                
                TreeNode node = q.poll();
                if(node.val == x){
                    x = count;            
                }
                if(node.val == y){
                    y = count;
                }
                
                if(node.left != null){
                    q.offer(node.left);
                }else if(node.right != null){
                    q.offer(node.right);
                }
            }
            count++;
            if(x == y){
                return true;
            }
        }
        
        return false;
    }
}

1,2,3, n,4, n,5를 넣으면 true가 나와야 하는데 false가 나온다 왜 false가 나오는 걸까..

결국 x랑 y가 같지 않은데 count로 같은 층은 ++하게 해 줬는데 도대체 why???

node.left!= null 이면 q.offer(node.left);를 하는 건 맞지만 else if!

right도 넣어줘야 하는데 if 한 번만 타고 if문이 끝나기 때문 그래서 else if로 적는 것이 아닌 if로 적어줘야 한다!

int형인 변수 xc, yc를 0으로 두고 풀 수 있지만 변수를 생성하지 않고 파라미터 값에 바로 값을 주는 방향으로 택했다

이제 부모가 같을 때를 처리해야 되는데 x, y값이 바뀌었을 때 if문을 만들어 줘야 한다.

근데 답이 맞지 않는다... 뭘까?

오타였다.. node.left.val node.left.val을 두 번 적어줬기 때문!

Solution✍

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        
        Queue<TreeNode> q = new LinkedList();
        
        q.offer(root);
        
        int count = 0; // 처음 0층
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode node = q.poll();
                
                if(node.val == x){
                    x = count;            
                }
                if(node.val == y){
                    y = count;
                }
                
                if(node.left != null && node.right != null){
                    if(node.left.val == x && node.right.val == y){
                        return false;
                    }else if(node.left.val == y && node.right.val == x){
                        return false;
                    }
                }
                
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
            count++;
            
            
            if(x == y && count > 0){
                return true;
            }
        }
        
        return false;
    }
}

Review🤩

if문에서 실수하지 말자...

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

String 문제

Think🤔

음.. 

문자열 s, t가 주어지는데 둘이 겹치는 문자열을 반환해야 한다.

문자열의 최대공약수를 구하는 문제

근데 입력 ABCDEF , ABC가 출력 ""이다... 겹치는 문자를 반환하는 문제가 아닌가?

같은 문자가 있으면 그것은 공약수이다. 공약수 문자를 또 저장하고 둘 중 큰 문자열과 비교해서 있으면 그것을 반환하는 문제

class Solution {
    public String gcdOfStrings(String str1, String str2) {
		int s1 = str1.length();
		int s2 = str2.length();
		boolean status = s1 > s2;
		int s3 = (s1 > s2) ? s1 - (s1 - s2) : s2 - (s2 - s1);
		
		
		if(status) {
			String nam = str1.substring(s3, s1);
			if (str1.contains(str2)) {
				if (str2.startsWith(nam)) {
					return nam;
				}else {
					return"";
				}
			}
		}else {
			String nam = str2.substring(s3, s2);
			if (str2.contains(str1)) {
				if (str1.startsWith(nam)) {
					return nam;
				}else {
					return "";
				}
			}
		}
        
        return "";
    }
}

처음 코드이다.. 하지만 

이 곳에서 막혔다. TAUXX가 공약수가 되니깐 이 단어를 뽑아야 되는데 뽑을 수 없다.

계속 공통으로 나오는 단어를 뽑으려면 어떻게 해야 될까...

18,19일 동안 고민을 해봤는데도 뭔가 잘 되지 않았다.

다시 노트에 적어보면서 모르는 개념 + 어떻게 이 문제를 해결해야 할지 생각해보았다.

Solution✍

class Solution {
    public String gcdOfStrings(String str1, String str2) {

        // str2가 null(빌 때)까지 반복문을 돌려줍니다.
        while(!str2.isEmpty()){
            // str2가 더 큰 값이면 바꿔줍니다. str1한테 더 큰값이 들어감.
            if(str2.length() > str1.length()){
                String tmp="";
                tmp = str1;
                str1 = str2;
                str2 = tmp;
            }
            
            //str2의 문자열까지 str1의 문자열도 똑같다면 
            if(str1.substring(0,str2.length()).equals(str2)){
                String r = str1.substring(str2.length());
                str1 = str2;
                str2 = r;
            }else{
                return "";
            }
        }
        
        return str1;
    }
}

str2가 없어질 때 까지 돌아준다.

첫 if문에서 str2.length()가 더 크면 둘이 자리를 교체해야 함.

교환 법칙을 사용하기 위해서 tmp 변수를 뒀음!

이 if문을 통해서 str1에 계속 큰 값이 들어감!!😀

그리고 두 번째 if문은
str1 = TAXUUTAXUUTAXUU

str2 = TAXUUTAXUU

빨간색만큼 잘라서 str2랑 비교를 하는 것임!

String r을 이용해서 나머지 TAXUU값을 넣어주고 str1에다가는 str2를 넣어줌으로써

str1 = TAXUUTAXUU 가 되고

str2 = TAXUU

뒤에 잘랐던 TAXUU가 오는 것.. 이렇게 해서 계속 같으면 결국 str1에는 TAXUU가 남게 된다.

Review🤩

if else if 문을 이용해서 str1과 str2의 크기를 이용해서 짜려고 했는 것보다 교환 법칙을 통해서 str1의 자리에 계속 큰 값이 오도록 만들어줬고, 재귀(recursion)적으로 찾는 방법이 중요하다는 것을 알았다.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

Think🤔

음 IDID가 들어오면 0,4,1,3,2 가 반환됨.

III가 들어오면 0,1,2,3이 반환

DDI가 들어오면 3,2,0,1

I가 들어오면 앞에서 부터 번호가 찍히고 D가 들어오면 뒤에서부터 번호가 찍히는 것

그럼 파라미터 s를 먼저 확인하고 output은 문자길이보다 1개 더 길게 만들어 준다.

반복문은 s의 길이만큼 돌게 만들어준다.

I가 나오면 ret 배열에 icount를 더하면서 넣어준다.

D가 나오면 뒤에부터니깐 s.length의 값을 넣어주고 하나 줄어들게 한다.

그러면 문자열을 다돌고나면 마지막에 남는 것은 icount에서 하나를 더 한값이 나와야 하므로 마지막 값에 icount++를 대입해준다.

Solution✍

class Solution {
    public int[] diStringMatch(String s) {
        int[] ret = new int[s.length()+1];
        int icount = 0;
        int dcount = s.length();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == 'I'){
                ret[i] = icount;
                icount++;
            }else if(s.charAt(i) == 'D'){
                ret[i] = dcount;
                dcount--;
            }
        }
        ret[s.length()] = icount++;
        
        return ret;
    }
}

Review🤩

삼항 연산자로도 풀 수 있다는 사실!

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://leetcode.com/problems/same-tree/

Think🤔

주어진 TreeNode의 값이 같으면 true를 반환하는 문제이다.

그럴려면 이 두 개의 val값 , left값, right값이 같으면 true를 반환하는 문제인데

스택을 두개 만들어서 ArrayList를 이용해서 순서가 맞는지 비교해서 같으면 true를 반환하고 아니면 false로 반환하게 짜 보자.

일단 ArrayList를 다 만들고 다 비교해주는 방법으로 해줬다.

근데 엄청 비효율적이다.. 풀고 보니깐 굳이 ArrayList가 필요하지도 않고, Stack도 하나만 있으면 될 것 같다.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){return true;} // 같으면 둘 다 null true
        
        ArrayList<Integer> pArr = new ArrayList();
        ArrayList<Integer> qArr = new ArrayList();
        
        Stack<TreeNode> pstack = new Stack();
        Stack<TreeNode> qstack = new Stack();
        
        TreeNode pcur = p;
        TreeNode qcur = q;
        while(pcur != null || qcur != null || !pstack.isEmpty() || !qstack.isEmpty()){
            while(pcur != null || qcur != null){
                if(pcur == null && qcur != null){
                    return false;
                }else if(pcur != null && qcur == null){
                    return false;
                }
                pstack.add(pcur);
                qstack.add(qcur);
                pcur = pcur.left;
                qcur = qcur.left;
            }
            pcur = pstack.pop();
            qcur = qstack.pop();
            pArr.add(pcur.val);
            qArr.add(qcur.val);
            pcur = pcur.right;
            qcur = qcur.right;
        }
        
        if(!Arrays.equals(pArr.toArray(),qArr.toArray())){
            return false;
        }
        
        return true;
    }
}

하나 배운 것은 Arrays.equals로 두 개의 ArrayList를 비교할 수 있었다 

Solution✍

public boolean isSameTree(TreeNode p, TreeNode q) {
	Stack<TreeNode> ps = new Stack<>();
	Stack<TreeNode> qs = new Stack<>();
	ps.push(p);
	qs.push(q);

	while (!ps.isEmpty()){
		TreeNode pPop = ps.pop();
		TreeNode qPop = qs.pop();

		if (pPop != null && qPop != null){
			if (pPop.val != qPop.val){
				return false;
			}
			ps.push(pPop.left);
			ps.push(pPop.right);
			qs.push(qPop.left);
			qs.push(qPop.right);
		}
		else if (pPop != qPop){
			return false;
		}
	}
	return true;
}

stack을 하나 만들고 p , q를 푸시하는 방법으로 해줬다. ArrayList도 만들지 않고 메모리도 엄청 아꼈다

근데 여기 로직에서 20Line 이 이해하기 어려웠다..

pPop 하고 qPop은 노드 형식인데 그 둘을 비교해서 같지 않으면 false를 반환하는 거였는데 비교가 가능할 수 있을 거라고도 생각하지 못했다. 다음에 이런 비슷한 node문제가 나온다면 node를 비교하는 방법도 생각해 봐야겠다.

Review🤩

Array끼리 비교하는 방법을 알게 되었고, 노드 형식을 비교해서 false를 반환하는 방법도 알게 되었다.