[Leetcode]2120. Execution of All Suffix Instructions Staying in a Grid

문제 요약

• 알고리즘 분류:  이진법, 베열 
• 난이도: Medium
• 문제내용:
  • n × n 크기의 격자가 주어집니다.
  • 로봇초기 위치 startPos에서 시작.
  • 문자열 s로 주어진 방향 이동 명령 ('L', 'R', 'U', 'D').
  • 로봇은 문자열 s의 어떤 i번째 명령부터 실행을 시작할 수 있고, 로봇의 명령을 순차적으로 실행 한다.(단 격자 범위 밖으로 이동시 멈춘다.)
  • 정상적으로 실행 가능한 명령의 개수를 반환 하여라
• 사이트 주소: https://leetcode.com/problems/maximum-possible-number-by-binary-concatenation/description/

문제풀이

이 문제는 간단한 시뮬레이션 구현 문제이다. 문자열  s에서 각 명령을 시작점으로 설정하여 끝까지 실행하며, 실행 가능한 명령의 개수를 계산하면 된다. 예를 들어, 처음에는 s의 0번째부터 끝까지, 그다음에는 1번째부터 끝까지 실행하는 방식으로 진행합니다. 이동 중 격자 범위를 벗어나면 해당 명령부터는 실행 가능한 개수에 포함하지 않는다. 따라서 기본적인 시뮬레이션 구현 능력만 있으면 어렵지 않게 해결할 수 있는 문제이다. 자세한것은 아래 코드를 확인 해보면된다.

이 문제의 시간 복잡도는 문자열 sss를 두 번 반복하게 되므로 O(N^2)입니다.

 

Code

Python

 원래 파이썬에는 다른 언어와 다르게 switch ~ case구문이 없다. 그래서 if ~ elif로 처리를 해야 했지만 파이썬 3.10버전 부터 match ~ case 구문을 제공 해주고 있다.

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        size = len(s) # 명령 문자열의 길이
        counts = [0 for _ in range(size)] # 결과 배열 초기화

        for i in range(size):
            # 현재 명령의 시작점부터 끝까지 명령을 슬라이싱
            moveStr = s[i:size]
            x = startPos[0] # 로봇의 현재 x 위치
            y = startPos[1] # 로봇의 현재 y 위치
            count = 0 # 실행 가능한 명령의 개수
            for move in moveStr:
                fx = x # 이동 후의 x 위치
                fy = y # 이동 후의 y 위치

                # 현재 명령에 따라 위치 계산
                match move:
                    case "L": # 왼쪽으로 이동
                        fy -= 1
                    case "R": # 오른쪽으로 이동
                        fy += 1
                    case "U":  # 위로 이동
                        fx -= 1
                    case "D": # 아래로 이동
                        fx += 1
                # 이동 후 위치가 격자 내에 있는지 확인
                if((0 <= fx < n) and (0 <= fy < n)):
                    # 현재 위칭 갱신
                    x, y = fx, fy
                    count += 1 # 실행 가능한 명령 개수 증가
                # 격자를 벗어나면 명령 실행 중단
                else:
                    break

            counts[i] = count

        return counts

Java

class Solution {
    public int[] executeInstructions(int n, int[] startPos, String s) {
        int size = s.length(); // 명령 문자열의 길이
        int[] counts = new int[size]; // 결과 배열 초기화

        for (int i = 0; i < size; i++) {

            // 현재 명령의 시작점부터 끝까지 명령을 슬라이싱
            String moveStr = s.substring(i,size);
            int x = startPos[0]; // 로봇의 현재 x 위치
            int y = startPos[1]; // 로봇의 현재 y 위치
            int count = 0; // 실행 가능한 명령의 개수

            for (int j = 0; j < moveStr.length(); j++) {
                int fx = x; // 이동 후의 x 위치
                int fy = y; // 이동 후의 y 위치

                // 현재 명령에 따라 위치 계산
                switch (moveStr.charAt(j)) {
                    case 'L': // 왼쪽으로 이동
                        fy = y - 1;
                        break;
                    case 'R': // 오른쪽으로 이동
                        fy = y + 1;
                        break;
                    case 'U': // 위로 이동
                        fx = x - 1;
                        break;
                    case 'D': // 아래로 이동
                        fx = x + 1;
                        break;
                }

                // 이동 후 위치가 격자 내에 있는지 확인
                if(0 <= fx && fx < n && 0 <= fy && fy < n){
                    // 현재 위칭 갱신
                    x = fx;
                    y = fy;
                    count++; // 실행 가능한 명령 개수 증가
                // 격자를 벗어나면 명령 실행 중단
                }else{
                    break;
                }

            }
            counts[i] = count;
        }
        return counts;
    }
}