문제 링크 : https://www.acmicpc.net/problem/2438


굉장히 간단한 별찍기 문제지만 자바의 입/출력에 따라서 성능 차이가 납니다.


System.out.print는 속도가 느리기 때문에 많은 출력이 필요할 때는 BufferedWriter나 StringBuilder를 사용하는 것이 좋습니다.


N 만큼의 줄을 먼저 for문으로 돌면서 현재 i 만큼만 별을 출력하는 2중 for문을 사용하여 해결할 수 있습니다.


문제 링크 : https://www.acmicpc.net/problem/1924


월, 일을 입력받아서 요일을 출력하는 문제입니다.


각 월의 일수를 담아놓는 month 배열을 사용하여서


현재 월 이전까지의 모든 일수를 더합니다.


예를 들어 3월이면 1월~2월까지의 일수를 더합니다.


그 후에 현재 일수만큼 더한 다음 7을 나눈 나머지를 요일로 출력해주시면 됩니다.


문제 링크 : https://www.acmicpc.net/problem/1157


입력 받은 String 에서 가장 많이 사용되는 알파벳을 출력하는 문제입니다.


만약 가장 많이 사용된 알파벳의 수가 동일하다면 ? 을 출력합니다.


알파벳 갯수만큼 사이즈 26인 배열 arr 을 선언하여 알파벳의 갯수를 담아둡니다.


max값보다 크다면 새로운 알파벳을 answer 값에 갱신해주고 만약 max 값과 똑같다면 '?' 값을 answer에 입력합니다.


idx 값은 소문자에서 -'a' 를 해주면 인덱스만큼 구할 수 있습니다.


이후에 값을 넣을 때는 대문자로 출력해야 하기 때문에 i+65 값을 바꿔주면 됩니다.


Problem


톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하여


접수의 합을 출력하는 문제입니다.



Solution

특별한 알고리즘은 없이 톱니의 상태에 맞추어 톱니바퀴를 회전시키는 단순 구현 시뮬레이션 문제입니다.


이 문제에서 주의해야 할 점은 두 가지 입니다.


  1. 좌, 우 톱니바퀴의 회전 여부는 회전이 이루어지기 전에 결정된다.
  2. 톱니바퀴의 번호는 0 ~ 3 이 아니라 1 ~ 4 다.


1 번은 말그대로 톱니바퀴를 회전시키기 전에 모든 톱니바퀴에 대해서 회전 여부가 결정되어야 합니다.


저는 재귀를 통해 현재 상태에서 N 극과 S 극을 비교하여 회전 여부를 결정하고


가장 끝에있는 1 번 또는 4 번 부터 회전시켰습니다.


2 번은 사소한 실수인데 보통 톱니바퀴를 배열로 선언하다보니 0 ~ 3 이라고 착각하는 경우가 있습니다.


구현하는 함수는 톱니바퀴를 회전시키는 rotate 함수와


좌, 우 톱니바퀴 회전 여부를 판단하기 위한 leftright 함수입니다.


톱니바퀴를 회전시키는 건 for 문을 사용하면 됩니다.


leftright 함수는 재귀를 통하여 모든 톱니바퀴의 회전 여부를 검사합니다.


톱니바퀴의 번호가 0 ~ 3 이라고 생각하고 2 번을 회전시키라는 명령이 들어오면 다음과 같은 로직으로 진행됩니다.


example


회전 여부를 확인하기 위해 호출되는 것이 leftright 함수고 시간 순서대로 화살표를 따라서 진행됩니다.


코드를 보시면 쉽게 이해하실 수 있습니다.


파이썬은 deque 를 자료구조를 사용하였고 deque 에 있는 rotate 함수를 사용하였습니다.



Java Code

import java.util.*;
import java.io.*;

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    // 톱니바퀴 [번호][방향]
    static int[][] arr = new int[4][8];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int i = 0; i < 4; i++) {
            String s = br.readLine();
            for (int j = 0; j < 8; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        int k = stoi(br.readLine());

        // 톱니바퀴 회전
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = stoi(st.nextToken());
            int dir = stoi(st.nextToken());

            // 톱니바퀴 번호는 1~4, 인덱스는 0~3
            solution(idx - 1, dir);
        }

        // 점수 계산
        int score = 0;
        for (int i = 0; i < 4; i++) {
            score += arr[i][0] * (1 << i);
        }

        System.out.println(score);
    }

    // 9시 방향은 2, 3시 방향은 6
    static void solution(int idx, int dir) {
        left(idx - 1, -dir);
        right(idx + 1, -dir);
        rotate(idx, dir);
    }

    // 왼쪽에 있던 톱니바퀴 회전 여부 결정
    static void left(int idx, int dir) {
        if (idx < 0) return;

        if (arr[idx][2] != arr[idx + 1][6]) {
            left(idx - 1, -dir);
            rotate(idx, dir);
        }
    }

    // 오른쪽에 있던 톱니바퀴 회전 여부 결정
    static void right(int idx, int dir) {
        if (idx > 3) return;

        if (arr[idx][6] != arr[idx - 1][2]) {
            right(idx + 1, -dir);
            rotate(idx, dir);
        }
    }

    // dir = 1 시계방향, dir = -1 반시계방향
    static void rotate(int idx, int dir) {
        if (dir == 1) {
            int temp = arr[idx][7];

            for (int i = 7; i > 0; i--) {
                arr[idx][i] = arr[idx][i - 1];
            }

            arr[idx][0] = temp;

        } else {
            int temp = arr[idx][0];

            for (int i = 0; i < 7; i++) {
                arr[idx][i] = arr[idx][i + 1];
            }

            arr[idx][7] = temp;
        }
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import collections
 
wheels = []
turns = []
 
def turnLeft(i, d):
    if i < 0:
        return
 
    if wheels[i][2] != wheels[i+1][6]:
        turnLeft(i-1, -d)
        wheels[i].rotate(d)
 
def turnRight(i, d):
    if i > 3:
        return
 
    if wheels[i][6] != wheels[i-1][2]:
        turnRight(i+1, -d)
        wheels[i].rotate(d)
 
def solve():
    for turn in turns:
        [idx, direction] = turn
        
        turnLeft(idx-1, -direction)
        turnRight(idx+1, -direction)
 
        wheels[idx].rotate(direction)
 
if __name__ == '__main__':
    for i in range(4):
        wheels.append(collections.deque(list(sys.stdin.readline())[:8]))
 
    K = int(sys.stdin.readline())
 
    for i in range(K):
        v1, v2 = map(int, sys.stdin.readline().split())
        turns.append([v1-1, v2])
 
    solve()
    sumVal = 0
    for i, wheel in enumerate(wheels):
        sumVal += int(wheel[0]) * (1 << i)
    print(sumVal)


문제 링크 : https://www.acmicpc.net/problem/9466


싸이클을 형성하지 못하는 노드 갯수를 찾는 문제입니다.


일반적인 DFS로 모든 노드를 탐색하면 시간 초과가 납니다.


테스트케이스가


2 3 4 5 1


이렇게 주어졌을 때 모든 DFS를 탐색한다면


1->2->3->4->5

2->3->4->5->1

3->4->5->1->2

4->5->1->2->3

5->1->2->3->4


O(n^2)의 시간복잡도를 갖게 되고, 최대 10만의 n 값으로 탐색한다면 시간 초과가 날 수밖에 없습니다.


따라서 이 문제의 핵심은 더이상 방문할 필요가 없는 노드를 구분해서 쓸데없는 탐색을 막는 것입니다.


그렇다면 어떻게 구분 할 것인가?


일단 이 문제는 모든 노드들은 무조건 다른 노드 한개를 가리킨다라는 조건이 있습니다.


이 말은 DFS 탐색이 끝나기 위해선 무조건 싸이클에 들어가야 한다는 뜻입니다.


예제 테스트케이스를 봐도


1->3->3

2->1->3->3

3->3


어디서 시작해도 끝은 항상 싸이클입니다.


이 점을 이용한다면 1, 2, 3 번 노드를 모두 탐색 할 필요 없이 1번 노드 탐색만으로도 싸이클을 만난다는 사실을 알 수 있습니다.


그렇다면 2번과 3번 노드는 끝까지 탐색할 필요가 없게 됩니다.


2번 노드를 탐색해서 1번 노드를 찾아 들어간다면 1번에서 탐색한 결과와 똑같이 나오기 때문에 이를 방지하여 중복을 최소화 합니다.


그래서 기본적으로 DFS 탐색에 사용되는 visited 배열 외에 finished 배열을 하나 더 만들어줍니다.


visited 배열은 단순히 방문 여부를 체크하는 것이고, finished 배열은 방문한 노드에서 싸이클을 이미 뽑아냈었는가를 확인합니다.


1->3->3


1번 노드 탐색을 할 때는 visited[3] 값이 true기 때문에 탐색이 끝납니다.


탐색의 끝은 항상 싸이클이기 때문에 3번 노드는 무조건 싸이클을 형성하는 노드 중 하나라는 사실을 알 수 있습니다.


그럼 3번 노드부터 연결된 노드를 탐색하는 for문을 통해 3번 노드와 싸이클을 이루는 노드 갯수를 카운트합니다.


이 작업이 끝나면 1번과 3번 노드는 더이상 사용할 필요가 없기 때문에 finished 값을 true로 바꿔줍니다.


2->1->3->3


2번 노드 탐색을 할 때는 1번 노드를 만납니다.


하지만 1번 노드는 이미 사용한 노드라 finished 값이 true입니다.


1번 노드와 같은 싸이클을 만날 것이기 때문에 2번 노드는 더이상 탐색을 진행하지 않고 빠져나옵니다.


같은 방식으로 모든 노드를 탐색하면 O(n)의 시간복잡도로 탐색을 끝낼 수 있습니다.


Problem


지도의 크기와 높이가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제입니다.



Solution

문제 특성상 코드가 굉장히 지저분하게 나올 수밖에 없다고 생각합니다.


우선 이 길이 맞는지 확인하는 canGo(x, y, d) 메소드를 만들었습니다.


시작 x, 시작 y, 그리고 가로 세로 여부를 판단하는 d 를 파라미터로 받습니다.


2차원으로 되어 있는 지도에서 길 하나만을 체크하는 것이기 때문에 height 라는 1차원 배열에 옮겨담았습니다.


그리고 visited 배열을 사용하였는데, 경사로를 중복으로 놓는 상황을 방지하기 위해서 만들었습니다.


height 배열을 1 ~ n-1 까지 돌면서 확인합니다.


  1. 높이가 같으면 패스
  2. 높이 차이가 2 이상이면 false
  3. 내려가야 되는 경우
  4. 올라가야 되는 경우


이렇게 4가지 경우를 만들어서 예외처리를 하였습니다.


내려가야 하는 경우는 다음 인덱스부터 앞으로 길이 L 만큼


올라가야 하는 경우는 현재 인덱스부터 뒤로 길이 L 만큼


경사로를 놓을 땅이 있는지 확인합니다.


  1. 경사로 놓는 범위가 지도를 벗어나거나 j >= n
  2. 경사로 놓는 땅의 높이가 다르거나 height[i+1] != height[j] or height[i] != height[j]
  3. 이미 다른 경사로가 놓여있는 경우 visited[j] == true


위 세가지 경우 중에 하나라도 만족하면 false 를 return 합니다.


만약 위에 세 조건에 걸리지 않고 무사히 for 문을 돌면 끝까지 도착했다는 뜻이므로 true 를 return 합니다.


x 가 0 이며 세로로 가는 길 또는 y 가 0 이며 가로로 가는 길 모두 확인하며 카운트를 해준 뒤에 출력해주면 됩니다.



Java Code

import java.io.*;
import java.util.*;
 
class Main {
    static int stoi(String s) { return Integer.parseInt(s); }
 
    static int n;
    static int L;
    static int[][] map;
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        L = stoi(st.nextToken());
        map = new int[n][n];
 
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++)
                map[i][j] = stoi(st.nextToken());
        }
 
        // 풀이 시작
        for (int i=0; i<n; i++) {
            if (canGo(i, 0, 0)) 
                count++;
            
            if (canGo(0, i, 1)) 
                count++;
        }
 
        System.out.println(count);
    }
 
    // 한 줄이 경사로인지 확인 d = 0 이면 행검사, d = 1 이면 열검사
    static boolean canGo(int x, int y, int d) {
        int[] height = new int[n];
        boolean[] visited = new boolean[n];     // 경사로가 이미 놓여있는지 체크
 
        // 알아보기 쉽게 height 배열에 옮기기
        for (int i=0; i<n; i++) {
            height[i] = (d == 0) ? map[x][y+i] : map[x+i][y];
        }
 
        for (int i=0; i<n-1; i++) {
            // 높이가 같으면 패스
            if (height[i] == height[i+1]) {
                continue;
            }
            
            if (Math.abs(height[i] - height[i+1]) > 1) {
                return false;
            }
 
            // 내려가야되는 경우
            if (height[i] - 1 == height[i+1]) {
                for (int j=i+1; j<=i+L; j++) {
                    // j가 범위를 벗어나거나 높이가 다르거나 이미 경사로가 있는 경우
                    if (j >= n || height[i+1] != height[j] || visited[j] == true) {
                        return false;
                    } 
                    visited[j] = true;
                }
            }
            // 올라가야되는 경우
            else if (height[i] + 1 == height[i+1]) {
                for (int j=i; j>i-L; j--) {
                    if (j < 0 || height[i] != height[j] || visited[j] == true) {
                        return false;
                    }
                    visited[j] = true;
                }
            }            
        }
 
        return true;
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
N = L = 0
arr = []
 
def canGoPath(heights):
    current = heights[0]
    visited = [False for i in range(N)]
 
    for i, height in enumerate(heights):
        ## 높이가 똑같으면 그냥 진행
        if current == height:
            continue
 
        ## 높은 곳으로 이동
        ## 지금까지 이동한 거리가 L보다 크거나 같으면 이동가능
        elif current + 1 == height:
            for j in range(i-1, i-1-L, -1):
                if j < 0 or current != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
 
        ## 낮은 곳으로 이동
        ## 앞으로 이동할 곳에서 L만큼 같은 거리가 있으면 가능
        elif current - 1 == height:
            for j in range(i, i+L):
                if j >= N or current - 1 != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
        
        ## 높이 차이가 1 이상이면 불가능
        else:
            return False
    
    return True
 
 
def solve():
    count = 0
    for i in range(N):
        if canGoPath(arr[i]):
            count += 1
 
    for j in range(N):
        path = []
        for i in range(N):
            path.append(arr[i][j])
        
        if canGoPath(path):
            count += 1
    
    print(count)
 
if __name__ == '__main__':
    N, L = map(int, sys.stdin.readline().split())
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve()


문제 링크 : https://www.acmicpc.net/problem/14889


Solution

주어진 N 명의 사람들을 두 팀으로 나눈 뒤에 능력치의 차이가 최소가 되는 값을 구하는 문제입니다.


N 명 중에서 N/2 명 뽑아야 하기 때문에 조합(Combination) 을 사용하였습니다.


조합에 대한 포스팅 https://bcp0109.tistory.com/15


스타트팀은 visited 값을 true, 링크 팀은 visited 값을 false 로 하여 각 팀의 능력치 합을 따로 구해서 최소값을 찾아주시면 됩니다.


** 주의사항 1.


능력치의 차를 구해야 하기 때문에 절대값으로 계산해야합니다. Math.abs 함수를 사용해줍시다.


** 주의사항 2.


2 명이 팀일때는 예시에 나온대로


(2, 1) + (1, 2)

(3, 4) + (4, 3)


이렇게 각 팀의 능력치를 구할수 있습니다.


3 명이 팀일때는


(1, 2) + (2, 1) + (1, 3) + (3, 1) + (2, 3) + (3, 2)

(4, 5) + (5, 4) + (4, 6) + (6, 4) + (5, 6) + (6, 5)


이렇게 각 팀의 능력치의 합을 구해야 합니다.



Java Code


import java.util.*;
import java.io.*;
 
// https://www.acmicpc.net/problem/14889
 
class Main {
    static int stoi(String s) { return Integer.parseInt(s); }
 
    static int n;
    static boolean[] visited;
    static int[][] arr;
    static int min = 987654321;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = stoi(br.readLine());
        visited = new boolean[n+1];
        arr = new int[n+1][n+1];
 
        for(int i=1; i<n+1; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<n+1; j++) {
                arr[i][j] = stoi(st.nextToken());
            }
        }
 
        comb(10);
        System.out.println(min);
    }
 
    // 모든 팀의 조합 구하기
    static void comb(int startint depth) {
        if(depth == n/2) {
            min = Math.min(min, getAbilityDifference());
            return;
        }
 
        for(int i=start; i<n+1; i++) {
            if(visited[i] != true) {
                visited[i] = true;
                comb(i+1, depth+1);
                visited[i] = false;
            }
        }
    }
 
    // 팀의 능력치 차이를 구하기
    static int getAbilityDifference() {
        int sumStart = 0;
        int sumLink = 0;
 
        for(int i=1; i<n+1; i++) {
            for(int j=1; j<n+1; j++) {
                // true 면 스타트팀
                if(visited[i] && visited[j])
                    sumStart += arr[i][j];
 
                // false 면 링크팀
                if(visited[i] != true && visited[j] != true)
                    sumLink += arr[i][j];
            }
        }
 
        return Math.abs(sumStart - sumLink);
    }
}


Python Code


# -*- coding: utf-8 -*-
 
import sys
import itertools
 
= 0
arr = []
 
def team(member):
    allMember = [for i in range(N)]
    start_team = []
    link_team = []
 
    ## 멤버 선택
    for i in allMember:
        if i in member:
            start_team.append(i)
        else:
            link_team.append(i)
 
    start_sum = 0
    for i in start_team:
        for j in start_team:
            start_sum += arr[i][j]
    
    link_sum = 0
    for i in link_team:
        for j in link_team:
            link_sum += arr[i][j]
 
    return abs(start_sum - link_sum)
 
def solve(members):
    ## 모든 경우의 수 뽑기
    combination_members = itertools.combinations(members, int(N/2))
    selected_members = list(combination_members)
    length = int(len(selected_members)/2)
 
    minVal = sys.maxsize
    for member in selected_members[:length]:
        minus = team(member)
 
        if minVal > minus:
            minVal = minus
    
    print(minVal)
 
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    members = [for i in range(N)]
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve(members)
    


문제 링크 : https://www.acmicpc.net/problem/2075


주어진 숫자 중에서 N 번째로 큰 수를 출력하는 문제입니다.


1. 굉장히 간단하게 N*N 크기의 배열을 만들어서 수를 넣고 정렬해버리면 되긴 합니다.



<결과>



2. 하지만 시간을 좀더 줄여보기 위해 PriorityQueue를 사용할 수 있습니다.


우선순위 큐는 아시다싶이 일반 큐와 달리 우선순위를 비교해서 자동으로 정렬이 되는 자료구조입니다.


정렬 조건을 직접 설정할 수도 있고, 기본적으로 Integer 형으로 선언 하면 작은 수가 제일 먼저 pop 됩니다.


우선순위큐의 사이즈를 N 만큼 유지하면서 삽입/삭제를 반복하면 마지막에 남는 peek() 값이 N 번째로 큰 수가 됩니다.



<결과>



생각보다 속도가 많이 줄지는 않았습니다.


3. 조금이라도 더 줄여보기 위해 peek과 비교하는 작업을 추가합니다.



<결과>


+ Recent posts