프로그래머스LV2_9

괄호 회전하기

접근 과정

1. 문자열 길이를 돌면서 2, 3번을 반복하면 된다.
2. 문자열이 올바른 괄호 문자열이지 체크하여 answer을 증가
3. 문자열을 회전

시행착오

• 문자열 회전 로직을 처음에 반복문으로 구현했는데 substring 을 활용하면 그럴 필요가 없었다.

private String turn(String str){
	StringBuilder sb = new StringBuilder();
	for(int i = 0; i < str.length(); i++){
		sb.append(str.charAt((i + 1) % str.length()));
	}
	return sb.toString();
}

해결 코드

• 문자열 회전 로직을 substring 으로 개선하였다.
• 또한 문자열을 2배로 늘려서 해당 인덱스부터 원래 문자열 길이만큼 잘라서 검사하는 것도 가능하다!

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        for(int i = 0; i < s.length(); i++){
            if(isPossible(s)) answer++;
            s = turn(s);
        }
        return answer;
    }
    
    private String turn(String str){
        return str.substring(1) + str.charAt(0);
    }
    
    private boolean isPossible(String str){
        Stack<Character> s = new Stack<>();
        for(char c : str.toCharArray()){
            if(c == ')'){
                if(s.isEmpty() || s.peek() != '(') return false;
                s.pop();
            }
            else if(c == '}'){
                if(s.isEmpty() || s.peek() != '{') return false;
                s.pop();
            }
            else if(c == ']'){
                if(s.isEmpty() || s.peek() != '[') return false;
                s.pop();
            }
            else{
                s.push(c);
            }
        }
        if(s.size() > 0) return false;
        return true;
    }
}

시간복잡도

n^2 배열 자르기

접근 과정

1. left와 right를 돌면서 해당 인덱스의 2차원 배열의 행과 열을 찾는다.
2. 행보다 열이 커지면 열의 인덱스 + 1을 넣는다.
3. 행보다 열이 작거나 같으면 행의 인덱스 +1을 넣는다.

시행착오

• 접근 과정을 찾는데 좀 오래 걸렸다. 😅
• 2차원 배열을 채워서 왼쪽과 오른쪽에 맞춰 채우려다가 메모리 초과와 시간 초과가 발생했다. 따라서 O(N)의 시간복잡도로 풀려고 노력했다.

해결 코드

• left부터 시작하여 right까지 행과 열을 구해 맞는 값을 넣으면 된다.
• 종이에 예시 출력을 적으면서 생각하는 것이 큰 도움이 되었다!

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        List<Integer> li = new ArrayList<>();
        for(long i = left; i <= right; i++){
            long div = i / n;
            long mod = i % n;
            li.add((int)Math.max(div, mod) + 1);
        }
        return li.stream().mapToInt(i -> i).toArray();
    }
}

시간복잡도