본문 바로가기

항해99_코테스터디

[항해99]99클럽 코테 스터디 9일차 TIL + 탐욕법(Greedy)

 

 

탐욕법을 다시해보자~입니다.

 

1.  오늘의 학습 키워드 : 탐욕법(Greedy)

 

2.  오늘의 문제  Split a String in Balanced Strings

https://leetcode.com/problems/split-a-string-in-balanced-strings/

탐욕알고리즘인데 이건 어떻게 효율적인 코드를 짜나가 문제같습니다.

if, for문을 써서 풀었어요. L과 R의 개수가 같으면 split변수를 증가시켜 확인했습니다

 

3.  풀이 

- 처음 코드

class Solution {
    public int balancedStringSplit(String s) {
         int Rcount = 0;
         int Lcount = 0;
         int split = 0;
         for(int i = 0; i<s.length(); i++){
             if(s.charAt(i)=='R')
                 Rcount++;
             else
                 Lcount++;
             if(Rcount==Lcount){
                 split++;
                 Rcount = 0;
                 Lcount = 0;
             }
         }
}

변수가 3개나 있었고 시간도 1초가 걸렸었습니다. 

처음에 이런 오류가 났는데 매일 배열을 사용하다보니 그냥 String을 배열이라고 생각했어요.. C언어 포인터랑 좀 혼동이 온듯.....? 그래서 처음에 문자열값을 배열 인덱스를 이용해 접근을 하려 했다가 오류가 나고, 써칭해본 결과 charAt()함수를 사용해 해결할 수 있었습니다~~

But... 

근데 시간이 오래 걸려가지고 모범 답안을 찾아봐써요

 

import java.util.*;
class Solution {
    public int balancedStringSplit(String s) {
        int count = 0; int split=0;
        for(int i=0; i<s.length();i++){
            count += s.charAt(i) == 'R' ? 1 : -1;
            if(count==0)
                split++;
        }
        return split;
    }
}

모범 답안에서는 삼항연산자를 사용하여 L과 R의 개수가 같으면 0이 되도록 식을 세웠더라구요 그럼 변수도 하나 줄고 코드도 짧아지고 아주 굿..........이게 바로 코테 고수가 짜는 법인가요 저도 더 발전 했어요.

 

3.  회고 

탐욕 알고리즘은 뭔가 이름은 거창하지만 굳이 어려운 개념은 아니었다. 근데 코드를 너무 길게 짜고 불필요한 변수를 줄이는 연습이 필요하다는 것을 깨달았다. 그리고 String 기본 함수는 charAt()도 생각 안나서 좀 놀랐다. 하지만 그걸 찾아보면서 chatAt, Split, join 등과 같은 string함수들을 알게 되어 나중에 요긴하게 써먹어야겠다.

 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL