알고리즘

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


public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int M = Integer.parseInt(str[0]);
        int N = Integer.parseInt(str[1]);
        int K = Integer.parseInt(str[2]);

        String target = br.readLine();
        String total = br.readLine();
        if(total.contains(target))
            System.out.println("secret");
        else
            System.out.println("normal");
    }
}

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


public class Main
{
    static int[][] graph;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {-1,0,1,0};
    static int n; 
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        
        for(int i = 0; i < n; i++){
            String[] str = br.readLine().split("");
            for(int j = 0; j < n ;j++){
                graph[i][j] = Integer.parseInt(str[j]);
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(graph[i][j] == 1){
                    result.add(BFS(i,j));
                }
            }
        }
        Collections.sort(result);
        System.out.println(result.size());
        for(int a : result)
            System.out.println(a);
        //System.out.print(Arrays.deepToString(graph));

    }
    static int BFS(int y, int x){
        Queue<int[]> queue = new LinkedList<>();
        graph[y][x] = 0;
        int count = 1;
        queue.add(new int[]{y,x});
        while(queue.size() > 0){
            int[] current = queue.poll();

            for(int i = 0; i < 4; i++){
                int nextY = current[0] + dy[i];
                int nextX = current[1] + dx[i];
                if(0 <= nextY && nextY < n && 0 <= nextX && nextX < n)
                {
                    if(graph[nextY][nextX] == 1){
                        graph[nextY][nextX] = 0;
                        count++;
                        queue.add(new int[]{nextY, nextX});
                    }
                }

            }
        }
        return count;
    }
}

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

public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int W = Integer.parseInt(s[0]);
        int N = Integer.parseInt(s[1]);

        PriorityQueue <int []> metals = new PriorityQueue<>((o1, o2) -> o1[1] < o2[1] ? 1:-1);

        for(int i = 0; i < N; i++){
            String[] str = br.readLine().split(" ");
            metals.add(new int[]{Integer.parseInt(str[0]), Integer.parseInt(str[1])});
        }
        int sum = 0;

        while(!metals.isEmpty()){
            int[] e = metals.poll();
            if(W > e[0]) // 배낭이 여유가 있으면
            {
                sum += e[1] * e[0];
                W -= e[0]; // 다 담기
            }
            else
            {
                sum += W * e[1];
                break;
            }
        }
        System.out.println(sum);
    }
}

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


public class Main
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if(s.equals("1 2 3 4 5 6 7 8"))
            System.out.print("ascending");
        else if(s.equals("8 7 6 5 4 3 2 1"))
            System.out.print("descending");
        else
            System.out.print("mixed");
    }
}

11725번: 트리의 부모 찾기 (acmicpc.net)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        LinkedList<Integer>[] graph = new LinkedList[n + 1];
        boolean[] visited = new boolean[n+1];
        parent = new int[n+1];
        for(int i = 0; i <= n;i++)
            graph[i] = new LinkedList<Integer>();

        for(int i = 0; i < n - 1; i++){
            String[] s = br.readLine().split(" ");
            int v1 = Integer.parseInt(s[0]);
            int v2 = Integer.parseInt(s[1]);
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        bfs(1, graph, visited);
        for(int i = 2; i <= n; i++)
            System.out.println(parent[i]);

    }
    public static void bfs(int start, LinkedList<Integer>[] graph, boolean[] visited){
        Queue<Integer> queue = new LinkedList<Integer>();
        visited[start] = true;
        queue.add(start);

        while(queue.size() > 0){
            Integer current = queue.poll();

            for(int next : graph[current]){
                if(visited[next] == false){
                    parent[next] = current;
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}

27527번: 배너 걸기 (acmicpc.net)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] A = new int[1000001];
    static int[] heights;
    static int N;
    static int M;
    static int dest;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        M = Integer.parseInt(s[1]);


        String[] heights_ = br.readLine().split(" ");
        heights = new int[N];

        for(int i = 0; i < N; i++)
            heights[i] = Integer.parseInt(heights_[i]);

        if ((9 * M) % 10 == 0) {
            dest = (9 * M) / 10;
        }
        else {
            dest = (9 * M) / 10;
            dest++;
        }
        System.out.println(isPossible());
    }
    public static String isPossible(){
        for(int i = 0; i < M; i++){
            A[heights[i]] += 1;
            if(A[heights[i]] == dest)
                return "YES";
        }

        for(int i = 1; i <= N - M; i++){
            A[heights[i - 1]] -= 1;
            A[heights[i + M - 1]] += 1;
            if(A[heights[i + M - 1]] == dest)
                return "YES";
        }

        return "NO";
    }
}

2644번: 촌수계산 (acmicpc.net)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int start = Integer.parseInt(s[0]);
        int dest = Integer.parseInt(s[1]);

        int num = Integer.parseInt(br.readLine());
        LinkedList<Integer>[] graph = new LinkedList[n + 1];
        for(int i = 0; i <= n; i++){
            graph[i] = new LinkedList<>();
        }
        boolean[] visited = new boolean[n+1];

        for(int i = 1; i <= num; i++){
            String[] input = br.readLine().split(" ");
            int v1 = Integer.parseInt(input[0]);
            int v2 = Integer.parseInt(input[1]);
            graph[v1].add(v2);
            graph[v2].add(v1);

        }
        System.out.println(bfs(start, graph, visited, dest));
    }
    public static int bfs(int v, LinkedList<Integer>[] graph, boolean[] visited, int d)
    {
        Queue<int[]> queue = new LinkedList<>();
        visited[v] = true;

        queue.add(new int[]{v, 0});
        while(queue.size() != 0){
            int[] poll = queue.poll();
            int current = poll[0];
            int count = poll[1];

            //System.out.println(v + " ");
            for(int next : graph[current]){
                if(!visited[next])
                {
                    if(next == d)
                        return count + 1;
                    visited[next] = true;
                    queue.add(new int[]{next, count + 1});
                }
            }
        }
        return -1;
    }
}

코딩테스트 연습 - 주차 요금 계산 | 프로그래머스 (programmers.co.kr)

문제요약)

• 기본시간, 기본요금, 단위 시간(분), 단위 요금(원)에 대한 정보가 fees배열로 들어오고
• 입출차시간, 차량번호, IN-OUT여부가 records로 들어온다.
• 누적 주차 시간이 기본 시간 이하라면 기본 요금을 청구하고 초과한다면 단위 시간 마다 단위 요금을 청구한다.
• 초과한 시간이 단위 시간으로 나누어 떨어지지 않는다면 올림처리한다.(초과시간 == 63, 단위시간 == 10일 때, 7)
• 똑같은 차량이 여러번 출입할 수 있으며 출차된 내역이 없는 차량은 23:59분에 출차된 것으로 간주함
• 차량 번호가 작은 자동차부터 요금을 차례대로 배열에 담아서 리턴

문제풀이

차량별로 누적 주차시간만 구할 수 있다면 나머지는 연산만 하면 되는 문제이긴하다. 누적 주차 시간을 구하기 위해 처음에 접근했던 방식은 차량이 들어올 때 딕셔너리에 출입시간을 저장해놓고 차량이 나갈 때 시간을 계산해 주차 시간을 누적하는 방법을 이용하려 했는데 출차기록이 없는 차량을 처리하기 위해서는 출차할 때에 입출차 기록을 지워야 했는데 이문제를 해결하기가 어려웠다. 리스트의 인덱스를 이용해 레코드를 지울 수 있지만 지워야 할 레코드의 인덱스를 찾아낼 방법을 못찾았다. 

계속 지워야할 레코드의 인덱스를 찾는 방법을 고민하다가 정렬을 이용한다면 레코드를 지울 필요가 없지 않을까? 라는 생각을 하고 접근방식을 바꿨다.

정렬을 하면 차가 남아있는 경우를 제외하면 IN -> OUT의 순서를 가진다. 이를 이용하면 IN다음에 IN이 나온다면 이전 차량이 남아있다는 의미이다. 이전 차량의 기록을 남겨가면서 차가 들어올 때는 딕셔너리에 출입시간을 기록하고 차가 나갈 때는 출입시간을 불러와 주차시간을 계산하고 누적시킨다. 차량이 남아있을 때에는 이전 차량의 출입시간과 23:59를 이용해 주차시간을 계산한다.

records루프를 다 돌고나면 마지막 차량에 대해서만 고려하면 된다. 마지막 차량의 출입기록이 IN이라면 위와 같이 계산해준다.

알고리즘)

records 리스트화 한 다음 차량번호를 기준으로 정렬

출입 내역이 IN일 때 이전차량의 IN이라면 이전 차량 주차시간 계산(23:59 - 이전 차량 출입)

출입 시간과 이전 레코드 기록

OUT이라면 해당 차량의 출입시간을 불러와 주차시간 계산

---- 반복

루프가 끝난 뒤 마지막 차량에 대해 판단

차가 여러번 출입할 수 있기 때문에 누적처리 신경써야함

코드)

import math

def TimeResolver(t):
    time = t.split(':')
    return int(time[0]) * 60 + int(time[1])
def solution(fees, recordss):
    
    #fees[0] - 기본시간
    #fees[1] - 기본요금
    #fees[2] - 단위시간(분)
    #fees[3] - 단위요금(원)
    d = {}
    parkingTime = {}
    records = [] # [["05:34"],[5961],["IN"]]과 같은 형태로 변환
    for r in recordss:
        s =r.split(' ')
        records.append(s)
    records.sort(key = lambda x : x[1]) #차량번호를 기준으로 오름차순 정렬
    beforeRecord = [None,None,None] #정렬되어 있기 때문에 차가 남아있는게 아니라면 IN - OUT의 순서를 가짐 
    for index,rec in enumerate(records):
        record = rec
        if record[2] == "IN": 
            if beforeRecord[2] == "IN": #이전 차가 안나간것
                if parkingTime.get(beforeRecord[1]) is None: #처음 들어온 차
                    parkingTime[beforeRecord[1]] =  TimeResolver("23:59") - TimeResolver(d[beforeRecord[1]])
                else: #차가 여러번 들어올 수 있음
                    parkingTime[beforeRecord[1]] = parkingTime[beforeRecord[1]] + TimeResolver("23:59") - TimeResolver(d[beforeRecord[1]])
            
            d[record[1]] = record[0] #차 번호에 대해 출입시간을 갱신
            beforeRecord = record    
        else:
            if parkingTime.get(record[1]) is None:
                parkingTime[record[1]] =  TimeResolver(record[0]) - TimeResolver(d[record[1]])
            else:
                parkingTime[record[1]] = parkingTime[record[1]] + TimeResolver(record[0]) - TimeResolver(d[record[1]])
            beforeRecord = record
    #마지막 차에 대해
    if beforeRecord[2] == "IN": #마지막 차가 안나갔다면
                if parkingTime.get(beforeRecord[1]) is None: #처음 들어온 차
                    parkingTime[beforeRecord[1]] =  TimeResolver("23:59") - TimeResolver(d[beforeRecord[1]])
                else:
                    parkingTime[beforeRecord[1]] = parkingTime[beforeRecord[1]] + TimeResolver("23:59") - TimeResolver(d[beforeRecord[1]])
    
    answer = []
    for pTime in parkingTime:
        if parkingTime.get(pTime) > fees[0]:
            answer.append(fees[1]+ math.ceil(((parkingTime.get(pTime) - fees[0]) / fees[2])) * fees[3])
        else:
            answer.append(fees[1])

    return answer