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

안녕하세요. delay100 입니다!

오늘도 9시부터 11시까지 진행되는 정기세션에 참가했어요.

99club gather 채팅

11시가 거의 다될도록 1번 시간초과를 해결을 못해서.. 채팅으로 어려움을 호소했더니

"커띵"님께서 미들러문제 1번을 화면공유로 알려주셨어요ㅠㅠ

99club gather 참가

 

---

미들러 문제

---

1번. 숫자 변환하기

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

프로그래머스

 

1-1. 실패 코드 - 시간초과

단순히 bfs를 돌려 +n, *2, *3하는 모든 경우의 수를 찾게 되어 시간 초과가 발생합니다.

이미 도달한 index에 대해서 이후에 온 값이 크거나 같다면 다시 확인하지 않도록하는 처리가 필요합니다.(1-2에서 다룸) 

import java.io.*;
import java.util.*;

class Solution {
    static int result;
    public int solution(int x, int y, int n) {
        result = -1; 
        bfs(x, y, n);
        return result;
    }
    
    /**
    * 최단 거리를 찾는 bfs
    * @param x 현재 x
    * @param y 도착해야하는 y
    * @param n x에 더할 값
    */
    public static void bfs(int x, int y, int n) {
        Queue<Node> queue = new LinkedList<>();
        
        queue.offer(new Node(x, 0));
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            int nodeX = node.getX();
            int nodeCntPls1 = node.getCnt() + 1;
            
            if(nodeX > y) continue;
            if(nodeX == y) {
                result = node.getCnt();
                break;
            }  
            
            queue.offer(new Node(nodeX + n, nodeCntPls1));
            queue.offer(new Node(nodeX * 2, nodeCntPls1));
            queue.offer(new Node(nodeX * 3, nodeCntPls1));
        }
        
    }
}
class Node {
    int x, cnt;
    
    Node(int x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }
    
    int getX() {
        return this.x;
    }
    
    int getCnt() {
        return this.cnt;
    }
}

1-2. 성공 코드

 

1. 유지

• bfs 
• Node 클래스
• x값에서 y값으로 이동

 

2. 변경

• int[] visited 방문 횟수 배열 추가

 

모든 경우의 수를 확인하는 것이 아닌,

이전 방문 횟수보다 현재 방문 횟수가 더 작은 경우에만 다음 방문을 실행하도록 코드를 변경했습니다.

// 이미 방문한 경우 && 현재 값이 이전 방문 값보다 큰 경우 더이상 실행x
if(visited[nodeX] > 0 && visited[nodeX] <= nodeCnt) continue;

visited[nodeX] = nodeCnt;

위의 코드가 핵심인데,

이미 방문한 경우와 현재 값이 이전 방문 값보다 큰 경우에는 굳이 탐색하지 않아도 되므로 다시 while문을 실행하도록 했습니다.

만약 위의 조건을 만족하지 않고(뒤늦게 방문한 값이 더 작다면) 방문배열의 값을 더 작은 값으로 초기화 해주었습니다. 

import java.io.*;
import java.util.*;

class Solution {
    static int result;
    static int[] visited;
    public int solution(int x, int y, int n) {
        result = -1;
        visited = new int[y+1];
        bfs(x, y, n);
        return result;
    }
    
    /**
    * 최단 거리를 찾는 bfs
    * @param x 현재 x
    * @param y 도착해야하는 y
    * @param n x에 더할 값
    */
    public static void bfs(int x, int y, int n) {
        Queue<Node> queue = new LinkedList<>();
        
        queue.offer(new Node(x, 0));
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            int nodeX = node.getX();
            int nodeCnt = node.getCnt();
            
            if(nodeX > y) continue;
            if(nodeX == y) {
                result = nodeCnt;
                break;
            }  
            
            // 이미 방문한 경우 && 현재 값이 이전 방문 값보다 큰 경우 더이상 실행x
            if(visited[nodeX] > 0 && visited[nodeX] <= nodeCnt) continue;
            
            visited[nodeX] = nodeCnt;
            
            if(nodeX + n <= y) queue.offer(new Node(nodeX + n, nodeCnt + 1));
            if(nodeX * 2 <= y) queue.offer(new Node(nodeX * 2, nodeCnt + 1));
            if(nodeX * 3 <= y) queue.offer(new Node(nodeX * 3, nodeCnt + 1));
        }
        
    }
}
class Node {
    int x, cnt;
    
    Node(int x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }
    
    int getX() {
        return this.x;
    }
    
    int getCnt() {
        return this.cnt;
    }
}

---

2번. 가장 큰 수

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

프로그래머스

이 문제는 금요일에 해결하도록 하겠습니다.

---

+ 비기너 문제

1번.

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

프로그래머스

2번.

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

+ 챌린저 문제

1번.

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

프로그래머스

2번.

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

---

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