Algorithm/Baekjoon
[백준] 9375 패션왕 신혜빈 - Java
[백준] 9375 패션왕 신혜빈 - Java
2022.04.21여집합으로 접근하는 편이 더 합리적이다. 문제를 풀 때 의상의 이름은 어차피 중복되지 않으니 별로 중요하지 않다. 의상의 종류에 초점을 맞춰 풀이하자. 해시맵에 의상의 종류를 넣어준다. (중복되면 값을 +1) 입지 않는 경우를 함께 고려해 value+1 을 진행한 후 모든 경우의 수에서 아무것도 입지 않는 경우를 빼주면 된다. 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)); StringBuilder sb = new S..
[백준] 9663 N-Queen - Java
[백준] 9663 N-Queen - Java
2022.04.18백트래킹을 사용해서 풀 수 있다. import java.util.*; import java.io.*; // 엔퀸 public class Main1 { static int ans; static int N; static int col[]; // 퀸의위치저장용 i , col[i] public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); col = new int[N+1]; backtracking(1); // 1부터 시작해서 백트래킹함 dfs느낌으로 System.out...
[백준] 20301 반전 요세푸스 - Java
[백준] 20301 반전 요세푸스 - Java
2022.04.18Iterator를 사용하면 쉽게 풀 수 있다. 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()..
[백준] 3078 좋은 친구 - Java
[백준] 3078 좋은 친구 - Java
2022.04.17처음에 풀다가 틀린 코드 먼저 소개하겠다. 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); LinkedList q = new LinkedList(); for(int i=..
[백준] 17262 팬덤이 넘쳐흘러 - Java
[백준] 17262 팬덤이 넘쳐흘러 - Java
2022.04.06(가장 늦게 등교하는 사람의 등교 시간) - (가장 빨리 하교하는 사람의 하교 시간) 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)); int N = Integer.parseInt(br.readLine()); Student[] arr = new Student[N]; for(int i=0;i o2.end){ return 1; }else{ return -1; } } }); int temp1 = arr[0].end; Arr..
[백준] 14888 연산자 끼워넣기 - Java
[백준] 14888 연산자 끼워넣기 - Java
2022.03.06N과 M 시리즈 문제들처럼 재귀를 통해 완전탐색을 구현해서 풀 수 있는 문제이다. 전체적인 흐름은 N과 M 문제에서 사용한 풀이와 같다. 연산자들을 갱신하는 배열인 order배열을 사용해 지금까지 등장한 연산자들을 갱신하고, 연산자에 대한 탐색이 끝났으면 탐색된 연산자와 숫자 배열에 대해 조건에 맞게 계산해 준 다음 최댓값과 최솟값을 비교해서 답을 갱신한다. 이 과정에서 답을 계산해서 갱신하는 부분은 따로 함수로 빼서 처리했는데, 연산자를 갱신하는 과정에서 답까지 함께 계산하게 되면 답을 갱신하는 함수를 돌릴 필요가 없어 좀 더 빠르게 처리할 수 있다. Java import java.io.*; import java.util.*; public class Main { static int N, max, min..
[백준] 15649 N과 M (1) - Java
[백준] 15649 N과 M (1) - Java
2022.03.05https://13months.tistory.com/172 [백준] 15651 N과 M (3) - Java 완전탐색 문제이다. for문을 적당히 사용하면 쉽게 해결할 수 있지만, 답을 구하는 함수와 메인 함수를 구분해서 코드를 작성하고, 답을 구할 때 재귀를 사용해 좀 더 효율적으로 풀어보자. Java im 13months.tistory.com N과 M (3) 문제에서 중복을 허용하지 않는 조건이 추가된 문제다. boolean타입 변수를 선언해 중복된 수인지 확인해주는 방향으로 쉽게 해결할 수 있다. Java import java.io.*; import java.util.*; public class Main { static int N; static int M; static StringBuilder sb ..
[백준] 15651 N과 M (3) - Java
[백준] 15651 N과 M (3) - Java
2022.03.05완전탐색 문제이다. for문을 적당히 사용하면 쉽게 해결할 수 있지만, 답을 구하는 함수와 메인 함수를 구분해서 코드를 작성하고, 답을 구할 때 재귀를 사용해 좀 더 효율적으로 풀어보자. Java import java.io.*; import java.util.*; public class Main { static int N; static int M; static StringBuilder sb = new StringBuilder(); static int[] selected; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..
[백준] 3987 보이저 1호 - Java
[백준] 3987 보이저 1호 - Java
2022.03.04이차원 배열을 활용해서 풀 수 있는 구현 문제이다. 언제 break를 걸어주고 언제 방향을 바꾸는지 잘 파악하고 풀도록 하자. 풀이 로직은 다음과 같다. 1. C를 만나거나 경로에서 이탈하게 되면 break 2. .을 만나면 continue 3. 행성을 만나게 되면 현재 방향에 따라서 방향을 틀어준다. 마지막으로 무한으로 순환하게 되는 경우가 있는데, 이런 경우는 충분히 큰 수를 cnt변수와 비교해 무한으로 순환한다고 판단할 수 있다. dir배열을 사용해 현재 진행하고 있는 방향을 표시했고, 방향을 전환할 때도 배열을 사용했다. Java import java.io.*; import java.util.*; public class Main { static char[][] map; static int N; s..
[백준] 1706 크로스워드 - Java
[백준] 1706 크로스워드 - Java
2022.03.02지난번에 풀었던 경사로 문제와 비슷한 문제이다. 이차원 배열을 사용해 크로스워드 퍼즐을 구현하고, 조건에 맞춰 가로 단어와 세로 단어를 구해낸 다음 정렬을 진행한다. 풀이 로직은 다음과 같다. 1. 배열을 하나씩 반복하면서 현재 탐색하는 원소가 #가 아닌 경우 seq변수를 1 추가한다. (단어가 몇 번 연속되는지 확인) 2. #를 만나거나 행의 끝에 도달했을 때 seq변수가 2이상이면 (두 번 이상 연속됐으면) 정답을 갱신한다. 3. row방향으로, column방향으로 한 번씩 갱신한다. Java import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ ..
[백준] 17299 오등큰수 -Java
[백준] 17299 오등큰수 -Java
2022.03.02지난번에 풀었던 오큰수와 같은 로직으로 풀 수 있는 문제이다. 배열의 인덱스와 값을 가지는 스택 두 개를 선언하고 조건에 맞게 push와 pop을 진행해서 풀 수 있다. 오큰수 문제에서는 현재 탐색하는 원소보다 더 큰 수를 만나면 정답을 갱신했었는데, 이 문제에서는 원소들이 나온 횟수를 센 다음 현재 탐색하는 원소가 나온 횟수보다 더 많이 나온 횟수를 만났을 때 정답을 갱신해야 한다. Java import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReade..
[백준] 14890 경사로 -Java
[백준] 14890 경사로 -Java
2022.03.01생각할 부분이 많은 구현 문제다. 전체적인 풀이 로직은 다음과 같다. 1. 반복문을 돌면서 같은 숫자가 몇 번째 연속으로 나오고 있는지 확인한다. - 현재 확인하고 있는 수가 이전 수와 같으면 continue - 현재 확인하고 있는 수가 이전 수보다 크면 - 입력받은 L 이상으로 연속되고 있고, 경사로가 중복되지 않으면 경사로를 놓고, 연속을 초기화하며 continue - 현재 확인하고 있는 수가 이전 수보다 작으면 - 뒷부분을 확인한다. 뒷부분의 연속되는 수가 L이상이고, 경사로가 중복되지 않으면 경사로를 놓고 연속을 초기화 하며 continue 2. L이 1일 경우와 1이 아닐 경우를 따로 생각해 줬다. (더 좋은 풀이가 생각나지 않음) - L이 1일 경우는 간단하게 처리할 수 있다. 경사로를 중복해..