728x90
반응형

문제 해설

이 문제는 a는 S에서 출발하여 A까지 가야하고, b는 S에서 출발하여 B까지 도착해야 한다. 그리고 만약 같이 합승한다면 돈은 한번만 내도 된다.
처음에는 진짜 너무 복잡하게 생각했었는데, S->A로 가는 모든 경로를 구하고 S->B로 가는 모든 경로를 구한다음.. 서로 조합을 해서 같은 경로를 구하고.. 같으면 비용 안내도 되니까 한번만 계산해서 그 중 최솟값을 구할려고 했다...

이걸 굳이 각각 나누어서 경로를 구할 필요가 없었다. 결국에는 어떤 노드까지는 a와 b가 같이 가고, 그 다음 그 노드에서 a는 A까지, b는 B까지 가면 된다. 만약 x->y로 가는 최소비용을 알고 있으면 쉬워진다. 그럼 1부터 n까지의 노드들을 다 탐색하여 같이 가는 노드를 구한 다음, a,b 따로 가는 비용을 구해주면 된다.

여기서 x->y로 가는 최소비용을 구하는 방법은 2가지이다. 다익스트라를 이용해서 구할 수 있고, 모든 비용을 구해야하기 때문에 플로이드 워셜을 사용해도 된다.

다익스트라를 이용한 방법

플로이드 워셜보다 다익스트라를 먼저 생각한 것은 시간 효율성 때문이다. 다익스트라는 시간복잡도가 O(ElogV)이기 때문에 여기서 n은 200이하의 자연수이기 때문에 O(E)가 나온다. 즉, 간선의 개수와 시간복잡도가 같다. (O(Elog200) -> O(2E) -> O(E))

파이썬

import heapq

def solution(n, s, a, b, fares):
    INF = int(1e9)
    answer = INF

    def dijkstra(start):
        dist = [INF for _ in range(n + 1)]
        dist[start] = 0
        q = []
        heapq.heappush(q, [dist[start], start])
        while q:
            cur_dist, node = heapq.heappop(q)
            for tmp_node, tmp_dist in cost[node]:
                if dist[tmp_node] > cur_dist + tmp_dist:
                    dist[tmp_node] = cur_dist + tmp_dist
                    heapq.heappush(q, [dist[tmp_node], tmp_node])
        return dist

    cost = [[] for _ in range(n + 1)]
    for start, end, val in fares:
        cost[start].append((end, val))
        cost[end].append((start, val))

    dist = []
    for i in range(n + 1):
        dist.append(dijkstra(i))
    # print(dist)
    for i in range(1, n+1):
        answer = min(dist[s][i] + dist[i][a] + dist[i][b], answer)
    return answer
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    class Node implements Comparable<Node> {
        int node;
        int distance;

        public Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;

        ArrayList<Node>[] cost = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            cost[i] = new ArrayList<>();
        }

        for (int[] fare : fares) {
            int start = fare[0];
            int end = fare[1];
            int val = fare[2];
            cost[start].add(new Node(end, val));
            cost[end].add(new Node(start, val));
        }

        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        for (int i = 1; i <= n; i++) {
            dijkstra(i, n, cost, dist[i]);
        }

        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
        }

        return answer;
    }

    public void dijkstra(int start, int n, ArrayList<Node>[] cost, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            for (Node next : cost[cur.node]) {
                int newDist = dist[cur.node] + next.distance;
                if (newDist < dist[next.node]) {
                    dist[next.node] = newDist;
                    pq.add(new Node(next.node, newDist));
                }
            }
        }
    }
}

플로이드-워셜을 이용한 방법

플로이드 워셜은 노드들을 거치는 최단거리를 모두 다 구하게 된다. 그래서 노드들을 3번 탐색하게 되어 시간복잡도가 O(N^3)이 나오게 된다.
이 방법은 시간초과를 항상 유념해야 하는데, 문제조건에서 N은 200이하이기 때문에 O(10^6)정도가 나오게 되어 가능하다.

파이썬

def solution(n, s, a, b, fares):
    INF = int(1e9)
    cost = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost[i][i] = 0
    for fare in fares:
        start = fare[0]
        end = fare[1]
        val = fare[2]
        cost[start][end] = val
        cost[end][start] = val
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    answer = INF
    for i in range(1, n + 1):
        answer = min(answer, cost[s][i] + cost[i][a] + cost[i][b])
    return answer

자바

import java.util.Arrays;
class Solution {
    static int[][] cost;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        cost = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(cost[i], 1000000);
        }

        for (int[] fare : fares) {
            int start = fare[0];
            int end = fare[1];
            int val = fare[2];
            cost[start][end] = val;
            cost[end][start] = val;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i != j) {
                        cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            cost[i][i] = 0;
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            answer = Math.min(answer, cost[s][i] + cost[i][a] + cost[i][b]);
        }

        return answer;
    }
}

정답 및 후기

python은 두 가지 방법 모두 통과하였지만, java의 경우 다익스트라에서 효율성에서 4개를 틀렸었다.
원인은 시간복잡도 때문인데, 시간초과가 나는 이유는 다익스트라에서 간선이 많은 경우에 문제가 생기는 것 같다.
간선이 많으면 위의 문제에서 시간복잡도가 초과될 수 있다.

항상 음수간선이 없으면 플로이드-워셜보다 다익스트라를 먼저 생각했는데(일반적으로 간선보다 노드 개수에 제한이 많은 경우가 많아서..)
이 경우는 노드가 200이하라 플로이드-워셜이 더 효과적인 문제였다.

728x90
반응형

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[알고리즘] 2048 (Easy)  (0) 2023.10.08
[알고리즘] 친구비  (2) 2023.06.03
[백준] 타임머신 11657  (0) 2023.03.22
[백준 2636] 치즈  (0) 2023.03.11
[백준 - 1062] [파이썬] 가르침  (0) 2023.01.08
728x90
반응형

문제 설명

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

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

문제 자체는 2048 게임을 해보았다면 알 수 있는 문제이다. 물론 게임과는 달리 블록이 추가되지는 않는다. 

처음에 생각한 방법은 브루트포스로 모든 가지수를 해보는 것이다. 최대 5번 이동한다고 하였으므로 사실 모든 가지수를 구하더라도 

4가지 방향에 5번이면 4*4*4*4*4 = 1024 이므로 10의 세제곱 정도면 나머지 연산에서 10000번의 미만의 연산이면 시간 부족 문제는 없을거라 판단하였다. 

 

물론 왼쪽, 오른쪽, 위, 아래 이동하는 것에서 생각하거나 헷갈려서 오래 걸렸던 것 같다. 그리고 살펴볼 개념이 조금 더 있는 것 같다. 

1. 반복할때 product 사용하는 부분 -> DFS로도 해결 가능
2. left right는 다르다
3. 백트래킹의 개념과 활용법
해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법.
4. DeepCopy의 개념과 copy와의 차이점

문제 해설

2번 먼저 생각하면 왼쪽과 오른쪽은 당연히 다른데, 구현하기가 힘들어서 잠깐 생각해보았다.. 

왼쪽 오른쪽과 왼쪽 왼쪽의 결과는 최대값만 구하면 된다고 생각하여 동일한 결과가 나오지 않을까? 라고 생각했는데 

중간에 위로 올라가는 간단한 예시만 들어도 반례를 찾을 수 있다. 

224

022

204

 

1번과 3번은 같은 맥락이다.

나는 product를 사용하여 중복 순열을 통해서 모든 가지수를 구하였지만, 이를 백트래킹과 DFS를 이용하여 연산의 수를 줄일 수 있다.

def dfs(board, cnt):
    global ans
    if cnt == 5:
        for i in range(n):
            for j in range(n):
                ans = max(ans, board[i][j])
        return

    for i in range(4):
        tmp_board = move(deepcopy(board), i)
        dfs(tmp_board, cnt + 1)

위와 같은 코드를 사용하면 백트래킹과 DFS를 둘 다 적용할 수 있는 코드이다. https://hongcoding.tistory.com/126

 

[백준] 12100 2048 (Easy) (Python 파이썬)

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모

hongcoding.tistory.com

사실 4번째 이슈에서 제일 해결못했었는데 python에 대한 문법이였다.

python은 List가 1차원일 경우에는 list.copy()로 복사를 할 수 있지만, 2차원이 넘어갈 경우 오류가 생긴다.

무조건 같은 배열을 깊은 복사하기 위해서는 from copy import deepcopy를 한 뒤 deepcopy를 해서 복사를 하도록 하자. 

코드

from itertools import product
from copy import deepcopy

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))


def move_left(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = 0
        next_index = start_index + 1
        while next_index < n:
            if new_graph[i][start_index] == new_graph[i][next_index]:
                new_graph[i][start_index] = new_graph[i][start_index] + new_graph[i][next_index]
                new_graph[i][next_index] = 0
                start_index = next_index + 1
                next_index = start_index + 1
                if start_index > n or next_index > n:
                    break
            else:
                if new_graph[i][next_index] == 0:
                    next_index += 1
                    if next_index > n:
                        break
                else:
                    start_index = next_index
                    next_index = start_index + 1
                    if start_index > n or next_index > n:
                        break
        temp = new_graph[i]
        zero = []
        for j in range(n):
            if temp[j] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[i][zero.pop(0)] = new_graph[i][j]
                    new_graph[i][j] = 0
                    zero.append(j)
    return new_graph


def move_right(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = n - 1
        next_index = start_index - 1
        while next_index >= 0:
            if new_graph[i][start_index] == new_graph[i][next_index]:
                new_graph[i][start_index] = new_graph[i][start_index] + new_graph[i][next_index]
                new_graph[i][next_index] = 0
                start_index = next_index - 1
                next_index = start_index - 1
                if start_index <= 0 or next_index < 0:
                    break
            else:
                if new_graph[i][next_index] == 0:
                    next_index -= 1
                    if next_index < 0:
                        break
                else:
                    start_index = next_index
                    next_index = start_index - 1
                    if start_index <= 0 or next_index < 0:
                        break
        temp = new_graph[i]
        zero = []
        for j in range(n - 1, -1, -1):
            if temp[j] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[i][zero.pop(0)] = new_graph[i][j]
                    new_graph[i][j] = 0
                    zero.append(j)
    return new_graph


def move_up(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = 0
        next_index = start_index + 1
        while next_index < n:
            if new_graph[start_index][i] == new_graph[next_index][i]:
                new_graph[start_index][i] = new_graph[start_index][i] + new_graph[next_index][i]
                new_graph[next_index][i] = 0
                start_index = next_index + 1
                next_index = start_index + 1
                if start_index > n or next_index > n:
                    break
            else:
                if new_graph[next_index][i] == 0:
                    next_index += 1
                    if next_index > n:
                        break
                else:
                    start_index = next_index
                    next_index = start_index + 1
                    if start_index > n or next_index > n:
                        break
        zero = []
        for j in range(n):
            if new_graph[j][i] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[zero.pop(0)][i] = new_graph[j][i]
                    new_graph[j][i] = 0
                    zero.append(j)
    return new_graph


def move_down(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = n - 1
        next_index = start_index - 1
        while next_index >= 0:
            if new_graph[start_index][i] == new_graph[next_index][i]:
                new_graph[start_index][i] = new_graph[start_index][i] + new_graph[next_index][i]
                new_graph[next_index][i] = 0
                start_index = next_index - 1
                next_index = start_index - 1
                if start_index <= 0 or next_index < 0:
                    break
            else:
                if new_graph[next_index][i] == 0:
                    next_index -= 1
                    if next_index < 0:
                        break
                else:
                    start_index = next_index
                    next_index = start_index - 1
                    if start_index <= 0 or next_index < 0:
                        break
        zero = []
        for j in range(n - 1, -1, -1):
            if new_graph[j][i] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[zero.pop(0)][i] = new_graph[j][i]
                    new_graph[j][i] = 0
                    zero.append(j)
    return new_graph


ways = product([0, 1, 2, 3], repeat=5)
ans = 0
for way in ways:
    temp = deepcopy(graph)
    for i in way:
        if i == 0:
            temp = move_left(temp)
        elif i == 1:
            temp = move_right(temp)
        elif i == 2:
            temp = move_up(temp)
        elif i == 3:
            temp = move_down(temp)
    for i in range(n):
        for j in range(n):
            ans = max(ans, temp[i][j])
print(ans)

 

728x90
반응형

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[알고리즘] 합승 택시 요금  (2) 2023.11.27
[알고리즘] 친구비  (2) 2023.06.03
[백준] 타임머신 11657  (0) 2023.03.22
[백준 2636] 치즈  (0) 2023.03.11
[백준 - 1062] [파이썬] 가르침  (0) 2023.01.08
728x90
반응형

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

[문제 정보]

먼저 온도가 여러 개 나오는데 실내온도, 실외온도, 희망온도가 주어지고, 또 승객들 등등 여러 가지 정보가 한번에 나온다. 한번에 읽으면 정리가 안되기 때문에 어떤 걸 해결해야하는지 고민해봐야 한다. 

 

먼저 온도가 변하는 것을 생각하지 말고 온도가 어떤 범위 내에 있어야 하는지를 생각해보자. 승객이 있을 때는 온도는 t1~t2에 있어야 한다. 그리고 승객이 없을 때는 온도가 어디든지 사실 상관이 없다. 그러나 문제는 온도는 1도씩밖에 바뀌지 않기 때문에 승객이 있기 1분 전에는 반드시 t1-1에 있거나 t2+1에 있어야 승객이 있을 때 범위 내에 있게 된다. 

 

이번엔 온도가 어떻게 변하는지 살펴보겠다. 일단 에어컨이 꺼져 있을 경우, 온도는 실외온도를 따라간다. 에어컨을 껐는데 실외온도에 차이가 없다면 온도는 그대로 유지가 된다.

에어컨이 켜져 있을 경우엔 2가지 이다. 에어컨을 켜고 온도를 유지하는 경우와 에어컨을 켜서 실내온도와 반대 방향으로 1도 변경하는 경우이다. 

이렇게 단계적으로 생각해보면 희망온도는 사실 의미가 없다. 에어컨을 켜서 온도를 변하게 할 것인지 아니면 유지할 것인지의 문제일 뿐이다.

  • 에어컨 X, 실내온도 방향으로 1도 변경하는 경우(비용 0)
  • 에어컨 X, 온도를 유지하는 경우(비용 0)
  • 에어컨 O, 온도를 유지하는 경우(비용 b)
  • 에어컨 O, 온도를 실내온도와 반대 방향으로 1도 변경하는 경우(비용 a)

여기까지 이해하고 문제를 풀면 된다.

[문제 해설]

먼저 시간의 흐름이 있고, 온도의 변화도 있으므로 dp 2차원을 생각해내야 한다. 시간이 흐름에 따라 온도가 어떻게 변화하는지 확인하여 최적의 비용을 계산할 수 있기 때문이다.

 

DP를 사용하려면 문제가 있다. 지금 온도 범위는 -10도에서 40도까지인데 2차원 배열의 인덱스에는 음수가 들어갈 수 없다는 점이다. 그래서 온도를 임의로 10도씩 올려서 계산한다. 

 

그리고 dp를 사용하여 int(1e9)의 큰 값으로 모든 값들을 초기화 한다.

처음의 온도는 실외온도와 같다고 하였으므로 dp[0][temperature]은 0으로 초기화해준다. (여기가 출발점이다.)

 

그 이후에는 dp를 1부터 주어진 onboard의 길이까지 진행하면 된다. 

 

승객이 있을 경우는 dp 온도를 t1에서 t2만 구하면 된다. 그리고 승객이 없다면 나머지를 굳이 구할 필요없이 min(t1, 실외온도) 에서 max(t2, 실외온도)로 구하면 된다. 실외온도는 t1~t2 바깥 값이므로 이렇게 범위를 구하면 된다. 온도가 계속하여 이 사이의 값에 있어야 효율적임을 알 수 있다. 이유는 예시를 하나 생각해보면 된다. t1이 10도 이고, 실외온도가 8도라고 가정하면 8도 이상이어야 된다. 에어컨을 사용하여 8도 밑으로 내려갈 이유가 없다. (에어컨의 소비전력이 최소화가 되지 않는다)

 

그래서 먼저 범위를 구해주고 범위내의 dp값을 업데이트하는 식을 통해서 진행하면 된다. 

 

이 업데이트 하는 식이 조금 고민해야 한다. 

for j in range(start, end + 1):
    if j - 1 < 0:
        x = int(1e9)
    else:
        x = dp[i - 1][j - 1]
    if j + 1 > 50:
        y = int(1e9)
    else:
        y = dp[i - 1][j + 1]
    if j < temperature:
        dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
    elif j > temperature:
        dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
    elif j == temperature:
        dp[i][j] = min(x, y, dp[i - 1][j])

여기서 먼저 j-1이 0보다 작거나 j+1이 50을 넘어가면 계산이 안되므로 해당 값들을 처리해준다. 

 

먼저 j가 실외온도보다 낮을때 처리하는 경우를 생각해보자. dp[i][j]는 i분에 j온도가 되기 위한 비용이다. 

첫번째 먼저 i-1분에 j-1온도일 때는 실외온도를 따라가므로 에어컨이 없더라도 1도 올라간다. 

두번째 i-1분에 j+1온도일 때는 실외온도를 따라가면 j+2가 되거나 j+1이 유지(실외온도가 j+1이라면)되므로 j가 되기 위해서는 에어컨을 틀어서 온도를 낮춰야 한다. 

세번째 i-1분에 j온도일때는 유지만 하면 된다. 만약 에어컨을 끄면 실외온도를 따라가서 온도가 올라가므로 유지하려면 에어컨을 켜서 유지해야 한다. 에어컨이 유지하는 비용은 b라고 명시해주었다. 따라서 식은 다음과 같다. 여기서 x는 dp[i-1][j-1], y는 dp[i-1][j+1]이라고 생각하면 된다.

if j < temperature:
    dp[i][j] = min(x, y + a, dp[i - 1][j] + b)

 

그 다음에는 j가 실외온도보다 높을때 살펴보겠다. 

먼저 현재온도가 j-1이라면 j가 되려면 에어컨을 켜야한다. 아니면 실외온도를 따라가므로 온도가 떨어지거나 유지되기 때문이다.

두번째 j+1온도라면 실외온도를 그냥 따라가면 내려가므로 에어컨을 꺼도 된다.

세번째 j온도라면 유지를 해야한다. 그럼 그냥 b 비용을 내면된다. 이 세 개중에서 최소가 dp[i][j]가 된다.

elif j > temperature:
    dp[i][j] = min(x + a, y, dp[i - 1][j] + b)

 

마지막으로 j와 실외온도가 같을때 이다.

첫번째 현재온도가 j-1이라면 실외온도를 따라 올라가면 되므로 에어컨이 필요없다.

두번째 현재온도가 j+1이라면 실외온도를 따라 내려가면 되므로 에어컨이 필요없다.

세번쨰 현재온도가 j라면 실외온도 현재온도 목표온도가 다 같으므로 그냥 나두면 된다.

elif j == temperature:
    dp[i][j] = min(x, y, dp[i - 1][j])

 

이렇게 점화식을 계산하고 마지막 dp[i][j]에서 i가 onboard의 마지막일때 가능한 비용들이 나온다. 이 중 최소값이 정답이 되게 된다.

[코드]

def solution(temperature, t1, t2, a, b, onboard):
    temperature = temperature + 10
    t1 = t1 + 10
    t2 = t2 + 10

    dp = [[int(1e9)] * 51 for _ in range(len(onboard))]
    dp[0][temperature] = 0
    for i in range(1, len(onboard)):
        if onboard[i] == 1:
            start = t1
            end = t2
        else:
            start = min(t1, temperature)
            end = max(t2, temperature)
        for j in range(start, end + 1):
            if j - 1 < 0:
                x = int(1e9)
            else:
                x = dp[i - 1][j - 1]
            if j + 1 > 50:
                y = int(1e9)
            else:
                y = dp[i - 1][j + 1]
            if j < temperature:
                dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
            elif j > temperature:
                dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
            elif j == temperature:
                dp[i][j] = min(x, y, dp[i - 1][j])
        if i == len(onboard) - 1:
            return min(dp[len(onboard) - 1])

[후기]

실제 현대모비스 알고리즘 대회 때 머리만 싸매다가 못풀었었는데.. 다시 풀어도 머리가 터질 뻔했었다.
어려운 알고리즘이 있는 것보다 더 어려운 문제가 아닐까..(dp만 알면 풀 수는 있는)
그래도 좋은 문제 같아서 나중에 코딩 테스트 전에 한번 풀어보면 또 좋을것 같다.

728x90
반응형
728x90
반응형

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

 

16562번: 친구비

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,

www.acmicpc.net

문제 설명

(문제를 다 읽고나서 일단 슬펐다 ㅠㅠ) 준석이는 친구를 사귀기 위해서 친구비를 내야되는데 친구의 친구는 똑같이 준석이의 친구이므로, 만약 A라는 친구를 사귀면 A의 친구들도 모두 준석이의 친구가 되는 논리이다. 그래서 k원이 있을 때 준석이는 모든 친구를 사귈 수 있는지에 대해서 판단하는 문제였다.

문제 해설

먼저 친구들끼리는 이미 연관관계가 있을 것이다. 해당 정보를 graph에 1차원 배열로 정리하였다. (혹시나 2차원으로 정의했을 경우 시간초과에 대비했다)
그리고 친구가 되었는지 아닌지를 판단하기 위해 visited라는 변수를 두었다.
bfs함수를 정의하였다. bfs함수는 시작 노드를 파라미터로 입력받는다.

그리고 bfs를 진행하면서 연결된 모든 노드들을 확인하고 친구비가 최소인 값을 반환한다.

즉, 만약 1번 3번 5번 친구의 친구비가 각각 10,20,30 이고 서로 연결되어있다고 가정하자.

bfs(1)을 넣으면 1,3,5은 visited가 True로 바뀌고 제일 최소값인 10이 반환된다.

(연결된 친구들 정보도 컴파일을 위해 member 집합으로 확인하였다)

그리고 n번 반복해서 해당 노드를 방문하지 않았을 경우 bfs(node값)을 해주면 된다.

 

그리고 반환값은 최소이므로 해당 값들을 모두 더해준것이 정답이 된다. 그리고 해당 정답이 k보다 크다면 문제에서 주어진대로 Oh no를 출려해주면 된다.

from collections import deque

n, m, k = map(int, input().split())  # 학생 수, 친구관계 수, 가지고 있는 돈
costs = list(map(int, input().split()))  # 친구별 필요한 돈
graph = [[] for _ in range(n)]

for _ in range(m):
    v, w = map(int, input().split())
    graph[v - 1].append(w - 1)
    graph[w - 1].append(v - 1)
temp = [i for i in range(n)]
answers = []
visited = [False for _ in range(n)]

def bfs(start):
    q = deque()
    members = set()
    min_node = 10000
    q.append(start)
    while q:
        x = q.popleft()
        if costs[x] < min_node:
            min_node = costs[x]
        visited[x] = True
        members.add(x)
        for node in graph[x]:
            if not visited[node]:
                q.append(node)
    return min_node
min_cost = 0
for i in range(n):
    if not visited[i]:
        min_cost += bfs(i)
if min_cost > k:
    print("Oh no")
else:
    print(min_cost)
728x90
반응형

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[알고리즘] 합승 택시 요금  (2) 2023.11.27
[알고리즘] 2048 (Easy)  (0) 2023.10.08
[백준] 타임머신 11657  (0) 2023.03.22
[백준 2636] 치즈  (0) 2023.03.11
[백준 - 1062] [파이썬] 가르침  (0) 2023.01.08
728x90
반응형

알고리즘 스터디를 진행하다가 접한 문제이다. 음수 간선이 나온다 라는 사실을 어떤 알고리즘으로 풀 수 있었는데.. 이런 생각만 하다가 알고리즘을 찾아보게 되었다.

11657번: 타임머신

 

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

www.acmicpc.net

최단 거리 알고리즘

최단 거리 알고리즘에는 여러 종류가 있다. 먼저, 제일 먼저 떠오르는 건 다익스트라 알고리즘이다.

다익스트라 알고리즘

다익스트라는 해당 노드에서 출발하여서 다른 노드로 가는 각각의 최단 경로를 구해준다. 그리디 알고리즘을 배우고 접했었는데, 매번 가장 비용이 작은 노드를 선택하기 때문이다.

  1. 출발 노드 설정
  2. 최단 거리 테이블 초기화 (현재 방문하지 않은 점들은 int(1e9)등으로 설정)
  3. 현재 노드와 연결된 노드들 거리 테이블 업데이트
  4. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
  5. 해당 노드를 거쳐서 다른 노드로 가는 비용을 계산
  6. 위의 내요을 반복한다.

다익스트라 알고리즘는 시간복잡도 O(ElogV)로 구현할 수 있다.

여기서 E는 간선의 개수이고, V는 노드의 개수이다.

하지만 다익스트라 알고리즘의 단점은 모든 간선의 가중치가 양수여야 한다는 점이다. 그래서 벨만 포드 알고리즘이 필요하다.

벨만-포드 알고리즘

벨만 포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이라는 내용은 같은데, 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다는 점이 장점이다.

다음과 같은 그래프가 주어졌을 때, 1번에서 3번으로 가는 경우를 생각해보자.

다익스트라의 경우 1번은 2번과 3번이 이어져 있는데, 3번으로 바로 가는게 더 짧기 때문에, 그리디에 의해서 2번은 선택되지 않는다. 그런데 실제로는 1→2→3이 가중치가 14이기 때문에 더 짧다.

따라서, 다익스트라만 이용하면 음수 간선에 대한 처리가 어렵게 된다.

반면, 벨만 포드는 모든 간선을 전부 확인하므로, 최단 거리를 찾을 수 있게 된다.

벨만 - 포드 알고리즘

해당 알고리즘의 과정은 아래의 11657 타임머신 문제를 통해 확인하였다.

[Gold IV] 타임머신 - 11657

[문제 링크]https://www.acmicpc.net/problem/11657

[내가 푼 정답]

import sys

input = sys.stdin.readline


def shortcut(start):
    graph[start] = 0
    for i in range(n):  # 노드 개수만큼 반복
        for j in range(m):
            current_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if graph[current_node] != int(1e9) and graph[next_node] > graph[current_node] + cost:
                graph[next_node] = graph[current_node] + cost
                if i == n - 1:
                    return True
    return False


n, m = map(int, input().split())
graph = [int(1e9)] * (n + 1)
edges = []
for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((x, y, z))

if shortcut(1):
    print(-1)
else:
    for i in range(2, n + 1):
        if graph[i] == int(1e9):
            print(-1)
        else:
            print(graph[i])

성능 요약

메모리: 32276 KB, 시간: 968 ms

분류

그래프 이론, 벨만–포드

문제 설명

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

내가 푼 풀이

먼저 벨만-포드 알고리즘의 시간 복잡도는 O(VE)이다. 해당 문제에서 V는 500, E는 6000까지 될 수 있으니까 O(30000)은 연산이 1초를 넘지 않아서 사용해도 된다고 판단하였다.

먼저 n,m,edge들을 입력받고, 다익스트라와 비슷하게 그래프를 초기화 해준다.

n, m = map(int, input().split())
graph = [int(1e9)] * (n + 1)
edges = []
for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((x, y, z))

나는 shortcut이라는 함수를 만들어서 벨만 포드 알고리즘을 진행하였다.

def shortcut(start):
    graph[start] = 0
    for i in range(n):  # 노드 개수만큼 반복
        for j in range(m):
            current_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if graph[current_node] != int(1e9) and graph[next_node] > graph[current_node] + cost:
                graph[next_node] = graph[current_node] + cost
                if i == n - 1:
                    return True
    return False

해당 문제에서는 1번 도시만 확인하면 되니까 나중에 start에 1을 넣어서 확인하면 된다.

먼저 시작점은 0으로 초기화해준다.

그리고 노드 개수만큼, edge 개수만큼 이중 for문을 수행해야 한다.

간선을 모두 확인하는데, edges[j]안에 edges의 정보를 current_node, next_node, cost로 다시 받는다.

만약에 현재 노드를 거쳐서 다음 노드로 가는 것이 기존에 시작노드에서 다음노드로 가는 값(graph[next_node])보다 작다면, graph[next_node]를 업데이트 해주면 된다.

여기까지가 벨만-포드의 핵심이다.

 

 

이 문제에서는, 해당 반복을 끝냈는데, 가중치가 음수가 되어있는 결과를 확인해야 한다. 왜냐하면 음수가 되었다면, 해당 루트를 계속 반복하면 시간은 거꾸로 간다.(그래서 타임머신 문제이다.)

 

따라서 노드 개수만큼 반복할 때, 마지막 업데이트를 하는데 또 바뀌어 있다는 뜻은 모든 노드와 간선에 따라서 다 업데이트 했는데 또 바뀌는 것은 해당 가중치가 음수라는 의미이다. 그래서 이 때는 출력을 -1만 하면 된다.

 

 

[참고]

https://velog.io/@kimdukbae/알고리즘-벨만-포드-알고리즘-Bellman-Ford-Algorithm

728x90
반응형

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[알고리즘] 2048 (Easy)  (0) 2023.10.08
[알고리즘] 친구비  (2) 2023.06.03
[백준 2636] 치즈  (0) 2023.03.11
[백준 - 1062] [파이썬] 가르침  (0) 2023.01.08
[17609] [파이썬] 회문  (0) 2023.01.08
728x90
반응형

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

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

[문제 이해와 내가 푼 방법]

처음에 문제를 읽고 나서는 간단한 탐색 문제라고 생각하였다.

일단 치즈인지 아닌지 판단하여, 제일 겉에 있는 치즈들을 모두 없애주고 사이클을 도는 횟수를 저장하고, 남은 치즈도 따로 저장하는 이 과정을 반복하면 된다고 생각하였다.

 

이렇게 단순한게 생각하고 접근하였는데 고려해야할 사항이 하나 더 있었다.

제일 겉에 있는 것을 어떻게 판단할 것인가의 문제였는데, 처음에는 0이 있는 칸이 상하좌우에 하나라고 있으면 겉에 있는 치즈라고 생각하였는데, 그것만으로는 판단이 불가능 했다.

해당 그림에서 파란색은 모두 겉에 있는 치즈가 맞지만 빨간색까지 포함시킨다는 점이 문제였다. 

그래서 탐색을 할 때 수정이 필요했다. 

 

나는 BFS를 사용하였는데, 일단 (0,0)을 BFS의 deque로 받았다. 그리고 방문하였는지 확인해야하기 때문에 visited 배열도 따로 만들어주었다. 

 

그리고, q에는 아직 방문하지 않았고, 그래프에서 0인 점을 q에 append 한다. 

만약 아직 방문하지 않았고, 그래프에서 1인점은 치즈인 점이다. 해당 좌표는 겉에 있는 치즈이기 때문에 0으로 바꿔주고 갯수를 체크해준다. 그치만 이 점은 q에 넣어주지 않는다. 해당 점을 넣어주게 되면 겉에 있는 치즈 이외에 안쪽에 있는 치즈까지 탐색이 되기 때문이다.

즉, 이렇게 되면 겉에 있는 치즈들과 외부의 0인 점들만 다 탐색을 하게 된다. 위에 있는 빨간색 점들과 빨간색 점들과 파란색 점들로 둘러싸인 0인 점들은 탐색을 하지 못하게 된다. (겉에서 치즈를 탐지하면 q에는 더이상 넣지 않기 때문이다.)

 

이 반복을 q가 없어질 때까지 하면, 이게 한 사이클이다. 나는 해당 사이클이 끝나면 남아있는 치즈들을 배열에 넣어주었다. 이 부분은 출력을 위해서 left_cheese에 넣어서 마지막에 정답을 출력해주었다. 

(물론 cycle이 한번밖에 없을때 조심해줘야 한다.)

 

[코드]

from collections import deque

row, col = map(int, input().split())  # 세로, 가로
graph = []
for _ in range(row):
    graph.append(list(map(int, input().split())))
cnt = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def total_cheese(graph):
    cnt = 0
    for i in range(row):
        for j in range(col):
            if graph[i][j] == 1:
                cnt += 1
    return cnt

def isCheese(a, b):  # 해당 칸이 제일 겉의 치즈인지 파악
    q = deque()
    q.append([a, b])
    visited = [[False] * col for _ in range(row)]
    cnt = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < row and 0 <= ny < col:
                if not visited[nx][ny]:
                    if graph[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                    elif graph[nx][ny] == 1:
                        visited[nx][ny] = True
                        graph[nx][ny] = 0
                        cnt += 1  # 겉의 치즈 개수
    return cnt

time = 0
left_cheese = []
left_cheese.append(total_cheese(graph))
while True:
    cheese = total_cheese(graph)
    time += 1
    left_cheese.append(cheese - isCheese(0, 0))
    if left_cheese[-1] == 0:
        break
print(time)
print(left_cheese[-2])
728x90
반응형

'알고리즘 > 알고리즘 문제' 카테고리의 다른 글

[알고리즘] 친구비  (2) 2023.06.03
[백준] 타임머신 11657  (0) 2023.03.22
[백준 - 1062] [파이썬] 가르침  (0) 2023.01.08
[17609] [파이썬] 회문  (0) 2023.01.08
[파이썬] [백준 - 7432번] 디스크 트리  (0) 2022.11.04
728x90
반응형

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

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

[문제 정의]

이 문제는 n개의 단어가 주어지면 k개의 알파벳을 배워서 몇 개나 읽을 수 있는지 판단하는 것이다. 근데 조건에서 단어는 무조건 앞에는 anta로 시작되고 끝은 tica로 끝난다.

 

해당 조건에서 알 수 있는 사실은 a, c, i, n, t는 최소한 배워야 단어를 읽을 수 있다는 사실이다. 만약에 k가 5보다 작으면 a,c,i,n,t를 다 배우지 못하기 때문에 판단하기도 전에 제외된다. 

[풀이]

먼저, 나는 alreadyLearned변수에 a,c,i,n,t를 집합으로 정의하였다. 그리고 단어를 입력받을때 단어는 무조건 anta로 시작하고 tica로 끝난다고 하였으므로 해당 단어를 잘라서 나머지 부분만 letter에 저장하여 letters에 넣었다. 그리고 toLearnList라는 변수에는 배워야하는 단어들을 다 추가하였다.

 예를 들어 단어가 antacbtica와 antaztica라고 한다면 letter는 [c,b], [z]가 들어가고 toLearnList에는 c,b,z,를 모두 합한 집합인 {c,b,z}가 들어간다. 

 

그리고 나는 조합을 이용하여서 toLearnList에서 k-5개를 뽑았다. k-5개를 뽑은 이유는 이미 alreadyLearned에 있는 5개는 벌써 배웠다고 가정하는 것이다.

 

그래서 뽑은 경우의 수를 하나씩 테스트해서 letter에 있으면 continue를 하고 없다면 break를 하는 식으로 반복문을 빠져나와서 조합으로 뽑은 경우의 수마다 몇 개의 단어를 배울 수 있는지 answer에 모두 넣는다. 그래서 answer배열 중 제일 큰 수가 제일 많이 배울 수 있는 경우이므로 해당 값을 출력한다.

 

 예를 들어 letters로 antartica, antahellotica, antartica를 입력 받은경우 나머지 변수들은 아래와 같다.

[['r'], ['h', 'o', 'e', 'l'], ['r']] # letters
['e', 'h', 'o', 'r', 'l'] # toLearnList
[('o',), ('l',), ('h',), ('e',), ('r',)] # checks

[놓친 부분]

처음에 계속 틀렸었는데 이유를 찾지 못하였다. 같은 스터디원에게 도움을 요청한 결과 combination을 완벽하게 사용하지 못한 것이 이유였다.

 

1C3과 같은 경우는 combination에서 처리를 하지 못하기 때문에 (1개에서 3개를 뽑는 경우는 되지 않는다) 해당 코드는 오류처리를 해주었어야 하는데 놓쳤었다.

[정답]

import sys

input = sys.stdin.readline
from itertools import combinations


def antarctica(letters, toLearnList):
    # print(letters) [['r'], ['h', 'o', 'e', 'l'], ['r']]
    # print(toLearnList) ['e', 'h', 'o', 'r', 'l']
    if len(toLearnList)<k-5:
        print(len(letters))
    else:
        checks = list(combinations(toLearnList, k - 5))
        # print(checks) # [('o',), ('l',), ('h',), ('e',), ('r',)]
        answer = []
        for check in checks:
            ans = len(letters) # 처음엔 다 배울 수 있다고 가정하고 못배우는 걸 뺴는 방법으로
            check = list(check) # 필요한지 잘 모르겠음
            for letter in letters:
                if len(letter) > k - 5:  # 배워야 되는 숫자가 더 많음
                    ans -= 1
                    continue
                elif len(letter) == 0:  # 이미 다 배움
                    continue
                else:
                    for i in range(len(letter)):
                        if letter[i] in check:  # 조합으로 k-5만큼 선택한 배열 안에 있는 경우
                            continue  # 계속 진행
                        else:
                            ans -= 1  # 없을 경우 이 단어는 이 조합으로는 일단 만들 수 없다
                            break
            answer.append(ans)
        print(max(answer))


n, k = map(int, input().split())
alreadyLearned = {'a', 'c', 'i', 'n', 't'} # 무조건 a,c,i,n,t는 배워야 함. 최소 5개
letters = []  # 가르치는 단어들
toLearnList = set()  # 배워야하는 글자들
for i in range(n):
    letter = set(list(input())[4:-5]) - alreadyLearned  # 입력받은 단어를 앞뒤 다 짜르고 이미 배운거 빼기
    toLearnList.update(letter) # 배워야하는 곳에 추가하기
    letters.append(list(letter))
if k < 5:
    print(0)  # 아무것도 배울 수 없다.
else:
    antarctica(letters, list(toLearnList))

[다른 풀이]

스터디원의 다른 풀이 중 비트마스킹을 사용하는 풀이가 있었다. (다시 봐도 생각해내기는 어려울것 같긴하다..)

 

비트 마스킹이란 컴퓨터 내부적으로 모든 자료는 이진수로 표현하기 떄문에 이런 특성을 이용해서 이진수 표현을 자료구조로 사용하는 기법을 비트 마스킹이라고 한다. 

 

비트마스크를 이용하면 집합을 쉽게 표현할 수 있다. 집합에 원소를 추가, 삭제하는 연산을 굉장히 빠르게 할 수 있다. 

 

원소의 개수가 N인 집합이 있다고 하면, 각각의 원소를 0부터 (N-1)번까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현할 수 있다.

 

이전 풀이는 집합으로 단어를 저장했는데 이번에는 이진법으로 알파벳을 포함하는지 아닌지를 저장하는 차이이다. 

 

메모리를 훨씬 줄일 수 있어서 더 효율적인 코드인것 같다.

참고 :  https://coder38611.tistory.com/136

 

from itertools import combinations
n, k = map(int, input().split())
if k < 5:
    print(0)
else:
    k -= 5
    alreadyLearned = {'a', 'n', 't', 'i', 'c'}
    input_chars = []
    alpha = {ky: v for v, ky in enumerate(
        (set(map(chr, range(ord('a'), ord('z')+1))) - alreadyLearned))} # 이미 배운것은 뺴줌
    cnt = 0
    for _ in range(n):
        tmp = 0
        for c in set(input())-alreadyLearned:
            tmp = tmp | (1 << alpha[c])
        input_chars.append(tmp)
    power_by_2 = (2**i for i in range(21))
    for comb in combinations(power_by_2, k):
        test = sum(comb)

        ct = 0
        for cb in input_chars:
            if test & cb == cb:
                ct += 1

        cnt = max(cnt, ct)
    print(cnt)

 

 

 

728x90
반응형
728x90
반응형

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

 

17609번: 회문

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

www.acmicpc.net

[문제 정의]

이 문제는 회문을 판단하는 것 이외에 유사 회문이라는 것을 정의하였다. 회문은 앞뒤가 똑같은 단어이고, 유사 회문은 회문이 아닐경우 단어 하나만 제외하면 회문이 되는 단어를 말한다. 그럼 경우가 3가지를 구분하여 정답을 출력해주면 되는 문제였다.

 

[풀이]

1. [잘못된 풀이] : 처음에 생각한 풀이는 문자열의 맨 앞 단어와 맨 뒤의 단어를 없애버리면서 하나씩 고려하는게 좋다고 생각하였다. 그래서 맨 앞의 단어와 맨 뒤의 단어가 같으면 파이썬 list에 있는 pop함수를 이용하여 제외시켰다. 

그리고 만약 앞 뒤의 단어가 다르다면 경우를 2개로 나눈다. 남은 단어의 젤 앞을 제외하는 경우와 젤 뒤를 제외하는 두 개의 case로 나누어서 해당 단어를 다시 회문인지 아닌지 판단하여 해당 단어가 회문이면 결국에 처음에 제공된 문자열은 유사회문인 것이다. 

import sys
input = sys.stdin.readline
T = int(input())
letterlist = []
answers = []
for i in range(T):
    letter = list(input())
    letterlist.append(letter[:-1])
for letter in letterlist:
    left = 0
    right = len(letter) - 1
    answer = 2
    while True:
        if letter[left] == letter[right]:
            letter.pop(right)
            letter.pop(left)
            right = len(letter) - 1
            if len(letter) == 0 or len(letter) == 1:
                answer = 0
                break
        elif letter[left] != letter[right]: # 다른 경우
            temp1 = letter[left + 1:right + 1]
            if temp1[:] == temp1[::-1]:
                answer = 1
                break
            else:
                temp2 = letter[left:right]
                if temp2[:] == temp2[::-1]:
                    answer = 1
                break
    answers.append(answer)
for answer in answers:
    print(answer)

위의 풀이는 예제는 맞지만, 시간 초과가 나는 코드이다. 어느 부분이 문제인지 몰랐었는데 pop이 문제였다. 맨 앞의 단어를 pop하는 경우는 시간 복잡도가 O(1)이라서 괜찮았지만 문자열 맨 뒤의 단어를 pop하는 경우는 O(n)이 될 수 있어서 시간초과가 나는 것이였다.

그래서 해당 코드를 비슷하게 유지하되 pop시키지 않고 비교만 하는 코드로 바꾸었다.

 

[정답]

import sys
input = sys.stdin.readline

T = int(input())
letterlist = []
answers = []

for i in range(T):
    letter = list(input())
    letterlist.append(letter[:-1])


for letter in letterlist:
    left = 0
    right = len(letter) - 1
    answer = 2
    while True:
        if letter[left] == letter[right]:
            letter.pop(right)
            letter.pop(left)
            right = len(letter) - 1
            if len(letter) == 0 or len(letter) == 1:
                answer = 0
                break
        elif letter[left] != letter[right]: # 다른 경우
            temp1 = letter[left + 1:right + 1]
            if temp1[:] == temp1[::-1]:
                answer = 1
                break
            else:
                temp2 = letter[left:right]
                if temp2[:] == temp2[::-1]:
                    answer = 1
                break
    answers.append(answer)

for answer in answers:
    print(answer)
728x90
반응형

+ Recent posts