boj-dgsw / ps Goto Github PK

View Code? Open in Web Editor NEW

18.0 0.0 0.0 598 KB

problem solving 🌊🌊🌊

Java 40.17% C++ 57.22% Lua 0.44% D 0.02% Python 0.11% JavaScript 2.04%

baekjoon problem-solving programmers

ps's People

Contributors

Stargazers

ps's Issues

programmers - 석유시추

효율성 테스트 시간초과나네요 ㅜㅜ

    public int solution(int[][] land) {
        int answer = 0;

        int n = land.length;
        int m = land[0].length;

        for(int i = 0; i<m; i++) {
            int cnt = 0;
            boolean[][] visit = new boolean[n][m];
            for(int j = 0; j<n; j++) {
                if(land[j][i] == 1 && !visit[j][i]) {
                    Queue<Place> que = new LinkedList<>();
                    que.add(new Place(j, i));

                    while(!que.isEmpty()) {
                        Place place = que.poll();
                        int x = place.x;
                        int y = place.y;

                        if(!visit[x][y]) {
                            cnt++;
                            visit[x][y] = true;

                            if(x + 1 < n && land[x + 1][y] == 1 && !visit[x + 1][y]) {
                                que.add(new Place(x + 1, y));
                            }
                            if(x - 1 > -1 && land[x - 1][y] == 1 && !visit[x - 1][y]) {
                                que.add(new Place(x - 1, y));
                            }
                            if(y + 1 < m && land[x][y + 1] == 1 && !visit[x][y + 1]) {
                                que.add(new Place(x, y + 1));
                            }
                            if(y - 1 > -1 && land[x][y - 1] == 1 && !visit[x][y - 1]) {
                                que.add(new Place(x, y - 1));
                            }
                        }
                    }
                }
            }

            answer = Math.max(answer, cnt);
        }

        return answer;
    }

    static class Place {

        int x, y;

        Place(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

boj - 탈출 3055

왜 틀릴까..? 예시는 다 맞음.

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

public class Main {

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

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int startX = 0, startY = 0;
        char[][] map = new char[r][c];

        for(int i = 0; i<r; i++) {
            String s = br.readLine();
            for(int j = 0; j<c; j++) {
                map[i][j] = s.charAt(j);
                if(map[i][j] == 'S') {
                    startX = i;
                    startY = j;
                }
            }
        }

        boolean[][] visit = new boolean[r][c];
        Queue<Place> que = new LinkedList<>();
        que.add(new Place(startX, startY,0));

        int minute = 0;
        while(!que.isEmpty()) {
            Place place = que.poll();
            int x = place.x;
            int y = place.y;
            int dis = place.dis;

            if(minute != dis) {
                for(int i = 0; i<r; i++) {
                    for(int j = 0; j<c; j++) {
                        if(map[i][j] == '*') {
                            if(i + 1 < r && map[i + 1][j] == '.') {
                                map[i + 1][j] = '*';
                            }
                            if(i - 1 > -1 && map[i - 1][j] == '.') {
                                map[i - 1][j] = '*';
                            }
                            if(j + 1 < c && map[i][j + 1] == '.') {
                                map[i][j + 1] = '*';
                            }
                            if(j - 1 > -1 && map[i][j - 1] == '.') {
                                map[i][j - 1] = '*';
                            }
                        }
                    }
                }
                minute++;
            }

            if(!visit[x][y]) {
                visit[x][y] = true;

                if(map[x][y] == 'D') {
                    System.out.print(dis);
                    return ;
                }

                if(x + 1 < r && (map[x + 1][y] == '.' || map[x + 1][y] == 'D')) {
                    que.add(new Place(x + 1, y, dis + 1));
                }
                if(x - 1 > -1 && (map[x - 1][y] == '.' || map[x - 1][y] == 'D')) {
                    que.add(new Place(x - 1, y, dis + 1));
                }
                if(y + 1 < c && (map[x][y + 1] == '.' || map[x][y + 1] == 'D')) {
                    que.add(new Place(x, y + 1, dis + 1));
                }
                if(y - 1 > -1 && (map[x][y - 1] == '.' || map[x][y - 1] == 'D')) {
                    que.add(new Place(x, y - 1, dis + 1));
                }
            }
        }
        System.out.print("KAKTUS");
    }

    static class Place {

        int x, y, dis;

        Place(int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }

    }

}

programmers - 예상 대진표

맞왜틀? 알고리즘이 그냥 떠오르는 대로 해서 틀렸을 수도 있습니다.

class Solution{
    public int solution(int n, int a, int b){
        int answer=0;
        for(int i=1;i<n;i*=2){
            answer++;
        }
        int s=1,l=n;
        int m=(s+l)/2;
        boolean flag=true;
        if(a>b){
            int temp=a;
            a=b;
            b=temp;
        }
        while(flag){
            flag=false;
            if(s<=a && m>=b){
                l=m;
                m=(s+l)/2;
                flag=true;
            }
            if(m<a && l>=b){
                s=m+1;
                m=(s+l)/2;
                flag=true;
            } 
            if(flag) answer--;
        }
        return answer;
    }
}

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12985#

문제 설명

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력 :
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

답 : 3

O는 산봉우리, "인접하다"는 상하좌우 대각선
O X X X X X O
X X X X X X O
X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X O O X X X
X X X X O X X

코드

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

public class Main {

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] farm = new int[n][m];

        for(int i = 0; i<n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++) {
                farm[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

        int result = 0;
        boolean[][] top = new boolean[n][m];
        Set<Grid> topSet = new HashSet<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(!top[i][j]) {
                    result++;
                    topSet.clear();
                    boolean isTop = true;

                    boolean[][] visit = new boolean[n][m];
                    Queue<Grid> que = new LinkedList<>();
                    que.add(new Grid(i, j));

                    while(!que.isEmpty()) {
                        Grid grid = que.poll();
                        int x = grid.x;
                        int y = grid.y;
                        int height = farm[x][y];

                        if(!visit[x][y]) {
                            visit[x][y] = true;
                            int[] xArr = {x - 1, x, x + 1};
                            int[] yArr = {y - 1, y, y + 1};
                            topSet.add(new Grid(x, y));

                            for(int k = 0; k<3 && isTop; k++) {
                                for(int l = 0; l<3; l++) {
                                    if(k == x && l == y) {
                                        break;
                                    }

                                    if(xArr[k] > -1 && xArr[k] < n && yArr[l] > -1 && yArr[l] < m) {
                                        int compare = farm[xArr[k]][yArr[l]];
                                        if(compare > height) {
                                            result--;
                                            isTop = false;
                                            que.clear();
                                            break;
                                        } else if(compare == height) {
                                            que.add(new Grid(xArr[k], yArr[l]));
                                        }
                                    }
                                }
                            }
                        }
                    }

                    if(isTop) {
                        for(Grid grid : topSet) {
                            top[grid.x][grid.y] = true;
                        }
                    }
                }
            }
        }
        System.out.print(result);
    }

    static class Grid {

        int x, y;

        Grid(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

}

programmers - 프로세스

이 코드의 시간복잡도를 개선할 수 있는 방법을 고민해봅시다. (문제 풀고 코드 올려주세요~ 언어 제한 X)

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.atomic.AtomicBoolean;

public class Solution {

    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Process> que = new LinkedList<>();

        for(int i = 0; i<priorities.length; i++) {
            que.add(new Process(i, priorities[i]));
        }

        int cnt = 1;
        while(!que.isEmpty()) {
            AtomicBoolean canWork = new AtomicBoolean(true);
            Process process = que.poll();

            que.forEach(p -> {
                if(p.priority > process.priority) {
                    canWork.set(false);
                }
            });

            if(canWork.get()) {
                if(process.index == location) {
                    answer = cnt;
                }
                cnt++;
            } else {
                que.add(process);
            }
        }

        return answer;
    }

    static class Process {

        int index, priority;

        Process(int index, int priority) {
            this.index = index;
            this.priority = priority;
        }

    }

}

boj - 게임 1072

아래의 풀이 말고도 훨씬 많은 풀이가 나올 수 있을거 같습니다.
한 번 풀어보세요.

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

public class Main {

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

        int answer = Integer.MAX_VALUE;
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        int z = (int) (y * 100.0 / x);
        int l = 1;
        int r = x;
        while(l<=r) {
            int m = (l + r) / 2;
            int newZ = (int) ((y + m) * 100.0 / (x + m));

            if(newZ > z) {
                answer = Math.min(answer, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

}

programmers - 택배 배달과 수거하기

자료구조없이 구현할 수 있을것 같아 해봤는데, 오답과 시간초과가 나네요(85점)
한 수 가르쳐주세요

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver,pick;
        boolean first,last;
        while(true){
            deliver=cap;
            pick=cap;
            first=true;
            last=true;
            for(int i=n-1;i>=0;i--){
                if(i==0 && deliveries[i]==0 && pickups[i]==0) return answer;
                if(deliveries[i]!=0){
                    if(first){
                        first=false;
                        answer+=(i+1)*2;
                    }
                    if(deliveries[i]<=deliver){
                        deliver-=deliveries[i];
                        deliveries[i]=0;
                    }else{
                        deliveries[i]-=deliver;
                        deliver=0;
                        if(last){
                            n=i+1;
                            last=false;
                        }
                    }
                }
                if(pickups[i]!=0){
                    if(first){
                        first=false;
                        answer+=(i+1)*2;
                    }
                    if(pickups[i]<=pick){
                        pick-=pickups[i];
                        pickups[i]=0;
                    }else{
                        pickups[i]-=pick;
                        pick=0;
                        if(last){
                            n=i+1;
                            last=false;
                        }
                    }
                }
                if(pick==0 && deliver==0) break;
            }
        }
    }
}

백준 관련 크롬 확장 프로그램 추천

https://chromewebstore.google.com/detail/%ED%86%A0%ED%83%90%EC%A0%95/hannhecbnjnnbbafffmogdlnajpcomek?hl=ko

자신의 수준에 맞게 랜덤 문제를 뽑아주는 토탐정이라는 백준용 브라우저 확장 프로그램입니다.

사용법:
토탐정 설정(확장 프로그램 옵션) 내 "알고리즘 설정"에서 아는 알고리즘을 모두 체크해준 후
"문제 추첨 설정"에서 난이도 범위를 설정해주면 됩니다. (나머지는 선택 작성)

그리고 나서 추첨 생성을 누르면 추첨된 문제가 나오는 것이 아닌 추첨, 즉 필터가 생성됩니다.
그 상태로 백준에 접속하면 우하단에 파란색 원 모양 버튼이 나올 것입니다.
그것을 우클릭하면 5가지 정도 기능이 나올텐데 주사위 버튼을 누르면 현재 설정된 필터로 랜덤 문제가 걸러져서 나옵니다.
필터 바꾸는 것이 귀찮다면 필터의 순서(번째)를 확인한 후 백준 사이트 내에서 Alt+0~9 를 눌러 그 필터로 걸러진 문제가 랜덤으로 나오게 할 수도 있습니다.

♠ 주의사항 ♠ (퍼 옴)

BOJ 설정에서 알고리즘 분류를 반드시 "성공일 경우만 보기", "성공/부분 성공일 경우만 보기" 중 하나로 설정해 주세요. 그렇지 않을 경우 토탐정은 해당 문제를 이미 풀린 문제거나 알고리즘 분류가 없는 문제로 간주하고 기능을 제공하지 않습니다.
만약 BOJ Extended 확장 프로그램을 사용 중이면서 토탐정 테마를 사용하고 싶으실 경우에는, BOJ Extended의 테마를 '밝은 테마' 로 설정해 주세요. 테마가 서로 충돌할 수 있습니다.

전용 테마, 알고리즘 보기 잠금과 같은 나머지 기능 및 설정 방법은 공식 사이트를 참고해 주세요.
초반 설정이 귀찮기는 하지만 한 번 설정해 놓으면 랜덤 디펜스 하는 데 편하니 참고하시면 좋을 것 같습니다.

boj - N과 M(4)

백트레킹 공부하고 있는데 제가 부족해서 발상이 안떠오르네요. 도움 부탁드립니다.
https://www.acmicpc.net/problem/15652

boj-dgsw / ps Goto Github PK

ps's People

Contributors

Stargazers

ps's Issues

programmers - 석유시추

boj - 탈출 3055

programmers - 예상 대진표

boj - 농장 관리

문제 링크

문제 설명

코드

programmers - 프로세스

boj - 게임 1072

programmers - 택배 배달과 수거하기

백준 관련 크롬 확장 프로그램 추천

boj - N과 M(4)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent