수테크📱⌚️👀

문제 😵‍💫

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

내 풀🦷

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<String> str = new Stack<>();
        boolean answer = true;
        
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if(c == '(') {
                str.push(String.valueOf(c));
            } else if(c ==')') {
                if(str.isEmpty()) {
                    answer = false;
                    break;
                }
                str.pop();
            }
        }
        
        if (!str.isEmpty()) {
            answer = false;
        }
        return answer;
    }
}

정말정말 오랜만에 괄호 검사 문제를 풀었다 ㅎㅎㅎ

진짜 괄호 검사 추억이 많은 문제라 너무 기억나는데 파이썬 했던시절이라 잠시 흠칫했다 ㅎㅎㅎㅎ

당연히 스택 써서 풀어야 겠다 했는데 다른 사람 풀이가 스택도 쓰지 않고 정말 간단하게 썼던 풀이가 있어서 한번 가져와 봤다...

// 다른 사람 풀이

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }
}

참고하면 좋을 개념들 ✍️

스트링으로 변환 : String.valueOf(바꿀 값);

문제 😵‍💫

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

내 풀🦷

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        // 수포자들의 패턴 정의
        int[] pattern1 = {1, 2, 3, 4, 5};
        int[] pattern2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] pattern3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        // 점수를 계산할 배열
        int[] scores = new int[3];
        
        // 각 문제에 대해 수포자들의 답안을 비교하여 점수 계산
        for(int i = 0; i < answers.length; i++) {
            if(answers[i] == pattern1[i % pattern1.length]) {
                scores[0]++;
            }
            if(answers[i] == pattern2[i % pattern2.length]) {
                scores[1]++;
            }
            if(answers[i] == pattern3[i % pattern3.length]) {
                scores[2]++;
            }
        }
        
        // 제일 높은 점수를 찾음
        int maxScore = Math.max(scores[0], Math.max(scores[1], scores[2]));
        
        // 가장 높은 점수를 받은 수포자를 리스트에 추가
        List<Integer> result = new ArrayList<>();
        for(int i = 0; i < scores.length; i++) {
            if(scores[i] == maxScore) {
                result.add(i+1);
            }
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}

가장 많은 점수를 획득한 사람을 배열로 반환하는 간단한 문제였다!!

담는것 까지는 정말 쉬운데 return 문 작성하는 과정에서 어려움이 있었다!

참고하면 좋을 개념들 ✍️

• .stream()
  • stream : 데이터 컬렉션의 추상화로, 요소들을 차례차례 꺼내 처리할 수 있는 "데이터 흐름" 
  • List<Integer> 객체에서 각 요소에 접근할 수 있는 스트림을 생성한다 
  • 스트림은 데이터 처리 작업을 쉽게 할 수 있도록 도와주는 추상화 도구이다
• .mapToInt(i -> i) 
  • 스트림의 각 요소를 정수로 변환한다
  • i -> i는 람다 표현식으로, 리스트의 각 요소를 i 그대로 변환한다는 의미이다
  • 이 과정에서 객체(Integer)를 원시 타입(int)으로 변환하게 된다
• .toArray() 
  • 스트림의 결과를 배열로 변환한다
  • 최종적으로 List<Integer> 가 int[] 배열로 변환된다

문제 😵‍💫

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

내 풀🦷

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    private int dfs(int[] numbers, int target, int index, int sum) {
        // 모든 숫자를 다 사용했을 떄
        if(index == numbers.length) {
            // 목표 숫자와 합이 같으면 경우의 수 1 증가
            return sum == target ? 1 : 0;
        }
        // 현재 숫자를 더하는 경우와 빼는 경우로 재귀 호충..
        return dfs(numbers, target, index + 1, sum + numbers[index]) + dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}

이미 한번 풀었던 dfs 문제!!

모든 가능한 경로를 다 탐색하여 특정 조건을 찾아야하는 문제이므로 dfs를 사용하였다

if문을 쓰는것까지는 쉬운데 마지막에 재귀를 어떻게 시켜야하는지는 항상 고민되는 부분인거 같다..

하지만 이번문제는 수월하게 통과~~

참고하면 좋을 개념들 ✍️

 DFS를 사용했을 때 효과적인 문제 유형

1. 모든 경로를 탐색하여 특정 조건을 찾는 경우 : 주어진 숫자 배열을 더하고 빼서 특정 값을 만드는 문제
2. 해다 존재하는지 확인하는 경우 : 미로에서 출구까지 가는 경로가 있는지 확인할 때
3. 조합과 순열을 생성하는 문제 : 특정 길이의 조합을 생성하거나, 순열을 만드는 문제
4. 백트래킹과 함께 사용할 때 : N-Queens 문제처럼 제한 조건을 만족하는 경우의 수를 찾을 때

DFS 사용 시 주의사항

- 무한 루프 주의 : 재귀 호출에서 종료 조건을 명확히 설정해야 합니다

- 메모리 사용량 : 깊이가 깊어질 경우 메모리 사용량이 커질 수 있으므로, 너무 깊은 재귀 호출이 필요한 문제에서는 스택 오버플로우에 주의해야 합니다

- 탐색 최적화 : 백트래킹을 사용하여 불필요한 경로는 조기에 중단하여 효율성을 높일 수 있습니다

문제 😵‍💫

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

내 풀🦷

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i = 0; i < commands.length; i++) { 
            int start = commands[i][0] -1;
            int end = commands[i][1];
            int k = commands[i][2] - 1;
            
            // 배열의 특정 구간을 복사하고 정렬
            int[] arr = Arrays.copyOfRange(array, start, end);
            Arrays.sort(arr);
            
            // k번째 숫자를 결과 배열에 추가
            answer[i] = arr[k];
            
            }
        return answer;
    }
}

오랜만에 풀어보는 정렬문제라 간단한 문제지만 당황했다 ㅎㅎ

어떻게 배열을 가져오는것이 좋을지 for문 돌면서 새로운 배열을 만들어서 넣어줄까했는데 찾아보니 copyOfRange라는 배열 복사 메서드가 존재하여 사용해서 쓰니까 금방 해결 !!!

copyOfRange 꼭 기억해 두겠음~

참고하면 좋을 개념들 ✍️

Arrays.copyOfRange(원본배열, 시작인덱스, 끝인덱스);

원본배열 : 복사하려는 배열
시작 인덱스 : 복사를 시작할 인덱스(포함)
끝인덱스 : 복사를 종료할 인덱스(미포함)

int[] array = {1, 5, 2, 6, 3, 7, 4};
int[] slicedArray = Arrays.copyOfRange(array, 1, 5); // {5, 2, 6, 3}

문제 😵‍💫

https://school.programmers.co.kr/learn/courses/30/lessons/68935?language=java

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록

solution 함수를 완성해주세요

제한사항

- n은 1이상 100,000,000 이하인 자연수입니다.

입출력 예

내 풀🦷

class Solution {
    public int solution(int n) {
        String sam = Integer.toString(n, 3);
        String reverse_sam = new StringBuilder(sam).reverse().toString();
        int decimal = Integer.parseInt(reverse_sam, 3);

        return decimal;
    }
    
}

다시 알고리즘 하기로 하고 처음으로 유나가 골라준 문제라 그런지 쉬운 문제였다!!

이해력이 안 좋은데 프로그래머스는 예시를 설명해줘서 좀 더 풀기 좋은 듯 하다

10진법을 3진법 으로 바꾸고 3진법을 뒤집어서 다시 10진법으로 바꾸어서 도출!!

뒤집는 메서드인 reverse()는 파이썬과 동일하게 있다

그리고 Intger,toString()으로 바로 진법 변환할 수 있다는 것을 알게되었다!!!

다른 사람 풀이

class Solution {
    public int solution(int n) {
        String a = "";

        while(n > 0){
            a = (n % 3) + a;
            n /= 3;
        }
        a = new StringBuilder(a).reverse().toString();


        return Integer.parseInt(a,3);
    }
}

깔끔하다!!

변수명을 한 단어로 하는것도 좋은 방법일듯!!

참고하면 좋을 개념들 ✍️

• Integer.parseInt(String s) : 문자열(s)을 인자값으로 받으면 해당 값을 10진수의 Integer 형으로 변환
  ex) Integer.parseInt("1004")    // 1004
• Integer.parseInt(String s, int radix) : 숫자형의 문자열을 첫번째 인자값으로 받고 변환할 진수값을 입력하면 해당 진수에 맞춰서 Integer 형으로 변환
  ex) Integer.psrseInt("45", 3)    // 1200
• Integer.toString() : 숫자를 문자로 변환하는 형 변환 방법!!!
  ex) int num = 123;
        String str1 = Integer.toString(num);  .// 숫자가 아니고 문자 123임

문제 😵‍💫

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오

내 풀🦷

# 1446. 지름길
import sys
import heapq
input = sys.stdin.readline
INF = 1e9

n, d = map(int, input().split())
graph = [[] for _ in range(d + 1)]
distance = [INF] * (d + 1)

for i in range(d):
    graph[i].append((i + 1, 1))

# 지름길 있는 경우 인접 리스트에 추가해주기
for _ in range(n):
    s, e, l = map(int, input().split())
    # 마지막 도착지점이 실제 고속도로 보다 멀면 넘긴다
    if e > d:
        continue
    graph[s].append((e, l))

# print(graph)
distance[0] = 0
heap = [[0, 0]]
while heap:
    dist, now = heapq.heappop(heap)

    if dist > distance[now]:
        continue

    for i in graph[now]:
        mn_dist = dist + i[1]
        if mn_dist < distance[i[0]]:
            distance[i[0]] = mn_dist
            heapq.heappush(heap, (mn_dist, i[0]))

print(distance[d])

역주행이 안되는데 들어오기는 실제 고속도로보다 먼곳도 들어오고해서 어떻게 처리해줘야 할지 고민을 오래했다... 그리고 지름길이 있지만 더 멀어서 이용을 안 하는 경우는 어떻게 처리해야할까 고민을 했다...

가장 먼저 모든 두 길이1만큼 갈때 1이 걸린다고 초기화해줬고... 지름길 값을 입력하면서 역주행은 할 수 없으므로 마지막 값이 고속도로의 끝을 넘어버리는 경우는 넣어주지 않았다... 

그리고 나머지는 우리가 아는 다익스트라를 사용해서 구현하면 끝!!! 😊😊😊

참고하면 좋을 개념들 ✍️

Dijkstra

1. 작동원리

• 간선 : 인접 리스트, 거리 배열 : 초기값 무한대로 설정, 힙 시작점 추가
• 힙에서 현재 노드 빼면서, 간선 통할 때 더 거리가 짧아진다면 거리 갱신 및 힙에 추가해준다
• 힙 : 최댓값, 최솟값을 빠르게 찾을 수 있는 자료 구조

2. 기본 코드

# 더익스트라 구현하기

# k : 시작점
# dist : 거리배열

dist[k] = 0 
heapq.heappush(heap, (0, K))

while heap:
	w, y = heapq.heappop(heap)
    if w > dist[v] : continue
    for nw, nv in edge[v]:
    	if dist[nv] > dist[v] + nw:
        	dist[nv] = dist[v] + nw
            heapq.heappush(heap, dist[nv], nv))

3,  아이디어

• 한점에서 다른 모든 점으로의 최단 경로 > 다익스트라 사용
• 모든 점 거리 초기값 무한대로 설정
• 시작점 거리 0 설정 및 힙에 추가
• 힙에서 하나씩 빼면서 수행할 것
• 현재 거리가 새로운 간선을 거칠때보다 크다면 갱신
• 새로운 거리힙에 추가!!!

문제 😵‍💫

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇가지 자연수의 예를 들어 보면 다음과 같다.

• 3: 3(한 가지)
• 41 : 2+3+4+7+11+13 = 11+13+17 = 41(세 가지)
• 53 : 5+7+11+13+17 = 53(두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

내 풀🦷

# 1644. 소수의 연속합

import sys
input = sys.stdin.readline

N = int(input())
prime = []
arr = [True for _ in range(N+1)] 
arr[0] = arr[1] = False
for i in range(2, N+1):
    if arr[i]:
        prime.append(i)
        # i의 2배 이상 부터는 다 false...
        for j in range(2*i, N+1, i):
            arr[j] = False

result = start = end = 0
while end <= len(prime):
    each = sum(prime[start:end])
    if each == N:
        result += 1
        end += 1
    elif each < N:
        end += 1
    else:
        start += 1
print(result)

골드 3 요량하고는 엄청 어려운 문제는 아니지만 비교적 빠른 시간에 소수를 구하고 또 투포인터를 써야 하기 땨문에 두가지 알고리즘 개념을 알고 있어야 한다... 그래서 이거전에 풀 문제로 소수 구하는 문제 추천한다!!!!

참고하면 좋을 개념들 ✍️

• 에라토스 테네스의 체(소수 판별 알고리즘 : 소수들을 대량으로 빠르고 정확하게 구현할 수 있다)

// 에라토스테네스의 체를 사용하여 소수 구하기

// 주어진 범위 내에 있는 각 숫자에 대해 초기에는 모두 True인 리스트를 생성한다
arr = [True for _ in range(N+1)] 
// 0과 1은 소수가 아니므로 False로 값을 설정한다
arr[0] = arr[1] = False
// 2부터 N까지의 각 숫자에 대해 소수인지 판별한다
for i in range(2, N+1):
	// 현재 숫자가 소수인 경우, 해당 숫자를 소수 목록에 추가하고,,,
    // 현재 숫자의 배수들을 모두 False로 설정한다... (적어도 i를 포함하니까 소수가 아니다)
    if arr[i]:
        prime.append(i)
        # i의 2배 이상 부터는 다 false...
        for j in range(2*i, N+1, i):
            arr[j] = False

• 투 포인터 (리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 ex) 특정한 합을 가지는 부분 연속 수열 찾기 )

// 투 포인터 구현하기

// 다 더했을 경우 N이 되는 결과와 시작, 끝 점을 0으로 초기화
result = start = end = 0
// 끝 포인터가 소수의 길이보다 작서나 같은 동안 수행
while end <= len(prime):
	// 현재 시작부터 긑가지의 소수 합을 계산
    each = sum(prime[start:end])
    // 합이 N과 같다면 결과를 1 증가, 끝 포인터 또한 1 증가
    if each == N:
        result += 1
        end += 1
    // 합이 N보다 작다면 끝 포인터 1 증가
    elif each < N:
        end += 1
    // 합이 N보다 크다면 시작 포인터 1 증가
    else:
        start += 1

문제 😵‍💫

독일 로또는 {1, 2,...,49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1, 2, 3, 5, 8, 13, 21, 34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1,2,3,5,8,34], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램ㅇ을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 이싿. 각 테스트 케이스는 한 줄로 이루어져 있다, 첫 번째 수는 k(6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

내 풀🦷

# 6603. 로또
def backtracking(depth, beginwith):
    if depth == 6:
        print(*result)
        return

    for i in range(beginwith, k):
        if not visited[i]:
            result[depth] = nums[i]
            backtracking(depth+1, i+1)
            visited[i] = False


while True:
    lotto = list(map(int, input().split()))
    k = lotto[0]
    nums = lotto[1:]
    result = [0] * 6
    visited = [False] * k
    backtracking(0, 0) // 깊이, 어디서 부터 시작할건지

    if k == 0:
        quit()
    print()

N과 M으로 다진 백트래킹 개념을 다른 문제에도 적용시키고 싶어서 로또라는 문제를 풀어보았습니다!!!!

어려웠던 점....

1. 테스트 케이스마다 한줄 뛰우는걸 어떻게 하지....

2. 마지막 0이 나왔을 때 종료를 어떻게 하지...

3. 테스트 케이스의 수가 안주어졌는데 어떻게 하지...

백트래킹 개념적인부분 보다는 다른것들에 더 시간을 많이 잡아먹었다....

순,조에 대한 개념은 👇👇👇

https://jeniffer0812techstory.tistory.com/94

참고하면 좋을 개념들 ✍️

• exit() : 프로그램 강제 종료

for i in range(100):
    if i == 5:
        quit()
    print(i)
    
/* 
0
1
2
3
4
*/