[99club/TIL] 4주차 - 목요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

벌써 목요일이라니.... 시간이 너무너무 빨라요...

아무튼 오늘도 세션시간에 맞춰서 참가했습니다!

99club 모각코

---

미들러 문제

---

1번. 공원 산책

https://school.programmers.co.kr/learn/courses/30/lessons/172928

프로그래머스

사실 안 바꿔도 되지만 char을 int형으로 바꿔서 해결하는(쓸데없는) 작업을 .. 했습니다..

갈 수 있는 길인 경우 = 0, 장애물인 경우 = -1, 출발 지점인 경우 = 1 

양수가 갈 수 있고 음수가 장애물임을 뭔가 표시하고 싶었는데.. 이 문제에서는 굳이 할 필요가 없더군요 ..

 

아무튼 그렇게 길 배열을 list배열로 변경하고, routes 배열을 순회하면서 

북 - N, 남 - S, 서 - W, 동 - E 의 각각 경우에 아래의 조건에 해당하는지 확인하고,

해당하면 이동하지 않고 무시하는 것으로 해결했습니다.

1. 이동 시 index가 벗어나는지?
2. 이동할 수 있는 지?(장애물(-1)이 아닌지?)

class Solution {
    public int[] solution(String[] park, String[] routes) {
        int H = park.length; // 세로
        int W = park[0].length(); // 가로
        int[][] list = new int[H][W];
        int x = 0;
        int y = 0;
        
        for(int i=0; i<H; i++) {
            char[] c = park[i].toCharArray();
            for(int j=0; j<W; j++) {
               if(c[j]=='O') {
                   list[i][j] = 0;
               } else if(c[j]=='X') { // 장애물인 경우
                   list[i][j] = -1;
               } else if(c[j]=='S') { // 출발 지점인 경우
                   list[i][j] = 1;
                   x = i;
                   y = j;
               }
            }
        }
        
        for(int i=0; i<routes.length; i++) {
            char route = routes[i].charAt(0);
            int howMany = routes[i].charAt(2) - '0';
            int beforeX = x;
            int beforeY = y;
            boolean isIgnore = false;
            
            // System.out.println("x= "+x+"y= "+y);
            // System.out.println("route="+route+"/ howMany= "+howMany);
            for(int j=0; j<howMany; j++) {
                if(route=='N') {
                    if(x-1 < 0 || list[x-1][y]==-1) {
                        isIgnore = true;
                        break;
                    }
                    x--;
                } else if(route=='S') {
                    if(x+1 >= H || list[x+1][y]==-1) {
                        isIgnore = true;
                        break;
                    }
                    x++;
                } else if(route=='W') {
                    if(y-1 < 0 || list[x][y-1]==-1) {
                        isIgnore = true;
                        break;
                    }
                    y--;
                } else if(route=='E') {
                    if(y+1 >= W || list[x][y+1]==-1) {
                        isIgnore = true;
                        break;
                    }
                    y++;
                }
            }
            if(isIgnore) {
                x = beforeX;
                y = beforeY;
            }
        }
        
        int[] answer = new int[2];
        answer[0] = x;
        answer[1] = y;
        return answer;
    }
}

 

 

세션 시간에 다른 분의 설명을 들었는데, bfs를 풀 때 단골로 나오는 dx, dy를 쓰는 풀이를 하셨었습니다.

그리고 2개의 제한조건에 대해서 메소드를 만들어서 확인을 하셨는데, 그 방식이 더 깔끔하게 코드를 볼 수 있을 듯 합니다.

 

// 이렇게 dx, dy를 만들어서 필요한 만큼 *dx *dy를 하는 방식이 더 코드가 깔끔했을 듯 싶다.
dx = [0, 1, 0 -1]
dy = [1, 0, -1, 0]

---

2번. 예상 대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

이 문제는 .. 수학 문제인가? 공식을 유도하는 문제인가? 싶어서 머리를 열심히 싸매며 생각했는데..

처음 생각했던 내용은 만약 A= 5, B=15이라면,

2^2 < A < 2^3 < B < 2^4 

이므로 A가 B가 존재하는 구간을 벗어났으므로 4번의 경쟁이 필요합니다.

여기서 4번의 경쟁은 2^4의 지수인 4에서 나옵니다. 

이런식으로 존재하는 구간을 비교하며 수학적 접근으로 해결할 수 있는지 처음에 생각했었습니다. 

 

사실 이게 아니라 이분탐색으로 푸는 것이라고 하더군요 ..!

사실 필자는 이분탐색과 친하지 않아서.. 이런 문제를 봐도 아무 생각이 없었습니다.. 이 기회에 이분탐색에 대해 다시 깨닫게 되었지요..

 

**참고)

이분탐색은 mid=(low+high)/2를 하면서 중간의 값과 비교하며

값이 mid보다 찾으려는 값이 큰지, 작은지를 파악하고

high값을 mid-1로 바꾸거나, low값을 mid+1로 바꾸는 작업을 하는 것입니다!  

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

        while(!(a==b)) {
            a = (a+1)/2; // +1을 하는 이유는 1, 2, 3, 4를 2로 나누면 0, 1, 1, 2가 되기 때문
            b = (b+1)/2; // +1을 해주면 2, 3, 4, 5를 2로 나누게 되는데 이럼 1, 1, 2, 2가 됩니다.
            answer++;
        }

        return answer;
    }
}

코드가 이렇게나 간단한데 .. 너무 꼬와서 생각했던 것 같아요..ㅠㅠ

그리고 사실 세션이 아니었으면 .. 이렇게 푸는걸 한참동안 몰랐을겁니다..

---

+ 비기너 문제

1번.

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

프로그래머스

2번.

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스

+ 챌린저 문제

1번.

https://school.programmers.co.kr/learn/courses/30/lessons/131702

프로그래머스

2번.

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

---

봐주셔서 감사합니다. 피드백 환영합니다.