Part of your World

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

입출력 예

s result

입출력 예 설명

입출력 예 #1

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

package LV2;

import java.util.Stack;

public class H76502 {
	public int solution(String s) {
		int answer = 0;
		Stack<Character> stack = new Stack<>();

		for (int i = 0; i < s.length(); i++) {
			// 문자열을 왼쪽으로 x칸 회전시킴
			String rotated = s.substring(i) + s.substring(0, i);

			// 스택을 비우고 새로운 문자열의 괄호들을 확인
			stack.clear();
			boolean isCorrect = true;
			for (char c : rotated.toCharArray()) {
				if (c == '(' || c == '[' || c == '{') {
					stack.push(c);
				} else {
					if (stack.isEmpty()) {
						isCorrect = false;
						break;
					}
					char top = stack.pop();
					if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
						isCorrect = false;
						break;
					}
				}
			}

			// 올바른 괄호 문자열인 경우 카운트 증가
			if (isCorrect && stack.isEmpty()) {
				answer++;
			}
		}

		return answer;
	}
}

문자열을 왼쪽으로 x칸 회전시킨 후, 회전된 문자열이 올바른 괄호 문자열인지 확인하는 방법으로 문제를 해결한다. 문자열을 회전시키기 위해 substring 메소드를 사용한다.

각 회전된 문자열에 대해 스택을 사용하여 괄호들을 확인하고, 스택이 비어있는지 여부와 모든 문자를 확인한 후에도 스택이 비어있는지 여부를 체크하여 올바른 괄호 문자열인지 판별한다. 올바른 괄호 문자열인 경우 카운트를 증가시킨다.

마지막으로 카운트를 반환하여 결과를 도출한다.

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.

아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한 사항

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

입출력 예

N result

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

입출력 예 #3

위와 같은 방식으로 합니다.

public class Solution {
    public int solution(int n) {
        int ans = 0;  // 건전지 사용량을 저장할 변수 초기화
        
        // 거리가 0이 될 때까지 반복
        while(n > 0){
            // 거리가 2로 나누어 떨어지면 순간이동 가능
            if(n % 2 == 0){
                n /= 2;
            } 
            // 2로 나누어 떨어지지 않으면 점프를 해야함
            else {  
                n--;  // 점프 후 남은 거리 계산
                ans++;  // 건전지 사용량 증가
            }
        }
        
        return ans;  // 최소 건전지 사용량 반환
    }
}

"순간이동"을 우선적으로 사용하고, 순간이동으로 이동할 수 없는 경우에만 점프를 사용하는 그리디 알고리즘을 이용해 해결!

거리 **n**이 0이 될 때까지 반복하면서 현재 거리가 2로 나누어 떨어지면 순간이동을, 그렇지 않으면 점프를 하는 방식으로 문제를 해결한다.
순간이동은 건전지 사용량을 증가시키지 않지만, 점프는 건전지 사용량을 1만큼 증가시키므로, **n**이 홀수일 때마다 건전지 사용량을 1만큼 증가시킨다.
이렇게 하면 주어진 거리를 이동하는데 필요한 최소 건전지 사용량을 계산할 수 있다.

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 2 이상 2 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)20
• 1
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

N A B answer

입출력 예 설명

입출력 예 #1

첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

package LV2;

public class H12985 {
	public int solution(int n, int a, int b) {
		// 라운드 수를 나타내는 변수를 초기화
		int round = 0;

		// a와 b가 같아질 때까지 반복
		while(a != b) {
			// 다음 라운드에서 a의 번호를 갱신. 홀수일 경우 1을 더한 후 2로 나눠준다.
			a = (a + 1) / 2;

			// 다음 라운드에서 b의 번호를 갱신. 홀수일 경우 1을 더한 후 2로 나눠준다.
			b = (b + 1) / 2;

			// 라운드 수를 증가시킨다.
			round++;
		}

		// 마지막으로, 라운드 수를 반환한다.
		return round;
	}
}

토너먼트의 각 라운드에서 참가자 A와 B가 같은 그룹에 속하게 되는 시점을 찾는 것입니다. A와 B가 같은 그룹에 속하게 되는 것은 두 참가자의 번호가 같아지는 시점을 의미

토너먼트 게임에서 주어진 두 참가자(A와 B)가 몇 번째 라운드에서 만나게 되는지 계산하는 문제를 해결한다.
각 라운드에서 이긴 참가자의 번호는 다음 라운드에서 **(현재 번호+1)/2**로 갱신되며, 이를 바탕으로 A와 B의 번호를 갱신한다.
이 과정을 A와 B의 번호가 같아질 때까지(즉, 같은 라운드에서 경쟁하게 될 때까지) 반복하고, 이때까지 걸린 라운드 수를 반환한다.