오답 노트 & 새로 알게 된 점 문제에서 단어의 개수가 최대 10개, 알파벳 길이는 최대 8이고 서로 다른 문자는 서로 다른 숫자를 나타내기 때문에 10!로 TLE가 나지 않다고 생각이 들어 백트래킹을 이용하여 풀었다. 중복된 알파벳을 제거하기 위해 Set 컬렉션을 사용했고, arr라는 배열에 set의 내용을 그대로 옮겼다. 백트래킹을 이용하여 0~9의 숫자를 possible 배열에 넣어주었다. 이 때, possible의 index는 알파벳을 뜻하고, value는 알파벳에 해당한 숫자였다. findNum 메서드를 사용하여 인자로 string을 보내면 각 자리의 알파벳에 해당하는 숫자를 possible 배열에서 찾아 숫자로 만들어 반환시켜준다. 이렇듯 문제를 해결하는데 어려움은 없었다. 그러나 계속 TLE..

오답 노트 & 새로 알게 된 점 문제를 읽자마자 백트래킹으로 접근했다. 맞왜틀을 시전 후, 게시판에 반례를 보는 중에 99999 2 9 8 경우에 100000 - 1 로 2가 나오는데 나의 답은 27777이 나왔다. 백트래킹을 하여 자릿수마다 비교하기 때문에 100,000은 나올 수 없었다. 그래서 어떻게 풀어야하는지 고민을 했지만, 생각이 나질 않아 구글링을 했다. 참고 블로그 : https://moonsbeen.tistory.com/64 우리가 비교해야할 값은 + 또는 -만 누를 경우 vs 숫자를 누르고 N과 차이 만큼 +나 -를 누를 경우이다. 그래서 초기값을 Math.abs(N-100)으로 한다. 이 경우가 + 또는 - 만 누를 경우이다. 이제 리모컨을 눌러 나올 수 있는 최대값을 생각해서 0부터..

오답 노트 & 새로 알게 된 점 이 문제를 풀면서 배운 점이 많았다. 좋은 문제인 것 같다. pro메서드 문제에서 짧은 경로가 여러 개일 경우, 사전 순으로 가장 먼저 오는 것을 택한다고 했다. 그래서 연결리스트를 모두 오름차순 정렬해주었다. S -> E 를 가는 bfs를 탐색해주어 경로 값을 ans에 저장한다. bfs설명은 아래에서 하겠다. 제일 중요한 부분은 E -> S로 가는 경로이다. E->S로 갈 때는 S->E로 갈 때의 방문한 노드를 제외하고 이동한다. 즉, S->E로 bfs 탐색할 때 경로를 저장해줘야 한다. realVisit를 이용하여 역추적을 하고 S->E에서 방문했던 노드들은 visit[]를 true로 초기화한다. E->S 를 가는 bfs를 탐색하여 ans에 값을 더해주면 된다. bfs..

오답 노트 & 새로 알게 된 점 이번 문제는 18번의 시도 끝에 AC를 받았다. 문제 풀이 방법 : bfs를 사용한 풀이, 다익스트라를 사용한 풀이 처음에는 최소 시간 구하라해서 bfs를 이용하면 되겠다라는 생각으로 쉽게 생각했다. 하지만 보통이 아닌 문제였다. 코드1 코드1에서 중요한 점은 *2를 할 때의 while문이다. 문제에서 *2를 하게 되면 cnt를 늘리지 않는다. 즉, 최소 시간을 구해야하기에 범위가 넘지 않고, 방문을 하지 않았다면 2배에서 끝내지 않고, 4배 8배 16배 계속 해줘야하는 것이다. 왜? 최소 시간을 구해야하고, *2는 cnt를 늘리지 않기 때문이다. 지금 if문의 순서가 *2, -1, +1 순서로 되어있지만, *2가 -1이나 +1의 뒤에 가게 된다면 틀리게 된다. 그 이유는..

오답 노트 & 새로 알게 된 점 기본적인 BFS 문제이다. 다만, 원래 갈 수 있는 땅 중에 가지 못하는 곳은 -1을 출력하고 원래 갈 수 없는 땅은 0을 출력해야한다. 이 조건식을 세울 줄 아느냐를 물어보는 문제인 것 같다. 원래 갈 수 있는 땅은 A[i][j] = 1을 뜻한다. 즉, A[i][j] 값이 1이면서 count[i][j] 가 0이면 -1을 출력하고, 나머지는 count[i][j]를 그대로 출력하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ..

오답 노트 & 새로 알게 된 점 입력이 많은 문제일수록 천천히 읽고 순차적으로 풀 생각을 해야한다. 또한, 기능 별로 메서드를 잘 나눠야한다!! 처음 문제 접근을 말해보겠다. 입력을 다 한 뒤, 일반 위상정렬처럼 문제를 풀었다. 그런데 여기서 시간을 어떻게 구할지 생각하기 위해 예제를 손으로 직접 써보았다. time[i]는 i번째 건물을 지을 때 걸리는 시간이다. time[7]을 구할 때는 time[5]와 time[6]의 최댓값에 build[7]을 더한 값이다. 왜? 7번 건물은 5번, 6번 건물이 모두 지어져야 지을 수 있기 때문이다. 그렇다면 7번 건물의 시간을 구할 때 5, 6번 건물들을 어떻게 가져올 수 있을까라는 생각을 했다. 위상정렬에서는 start -> end 로 가는 방향만 연결리스트에 넣..

오답 노트 & 새로 알게 된 점 위상정렬을 배우고 처음 푼 문제이다. 문제를 접할 때는 위상정렬을 공부하여 , 위상정렬로 문제를 풀었다. 내가 만약에 이 문제를 그냥 봤다면 위상정렬을 생각할 수 있을까? 그러도록 문제를 읽고 이런 경우에 위상정렬을 쓰는구나라고 생각해야겠다. 키 순서대로 줄을 세운다. 모든 키를 재서 정렬하면 된다. 그러나 문제에 주어진 것은 전체의 키가 아닌 A가 B의 앞에 서야한다라고 주어졌다. 그러면 B의 앞에 있어야 하는 것들이 전부 줄을 서고 나서야 B가 설 수 있게 된다. 이러한 근거로 위상정렬로 풀게 된다! 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34..

오답 노트 & 새로 알게 된 점 문제를 읽으면 그램을 가졌을 때는 벽을 통과할 수 있다. 그렇다면 문제 접근할 때는 그램 없이 목적지에 도착하는 시간과 그램을 가지고 목적지에 도착하는 시간 중 더 작은 값을 구하면 된다. 여기서 중요한 점은 visit를 3차원 배열로 만들었는지가 아닌가 싶다. 왜냐하면 2차원 배열로 만들었을 경우, 그림과 같이 빨간색 동그라미 부분을 그램을 가지지 않고 먼저 방문했을경우, 그램을 가지고 저 부분을 지나칠 수 없게 된다. 그래서 그램을 가진 상태로 방문을 했는지, 가지지 않은 상태에서 방문을 했는지 나타내기 위해 visit를 3차원 배열로 만들어야한다. 코드1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

오답 노트 & 새로 알게 된 점 문제에서 "다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다"라는 말의 뜻을 잘 이해해야합니다. 이 말의 뜻은 물을 먼저 퍼지게 한 다음에 고슴도치를 움직이면 됩니다. 입력을 받을 때, 물이 나올 경우에 먼저 큐에 넣어줍니다. 그리고 나서 bfs를 시작할 때, 제일 마지막에 고슴도치의 위치를 넣어주었습니다. bfs를 할 때는 물일 경우에는 문제 조건에 맞게 물을 퍼뜨리면 되고, 물이 아니면 고슴도치를 움직였습니다. 특히 물이 퍼질 때는 A 배열에 퍼지는 물의 위치를 기록해주었습니다. 코드 package bfs_dfs; import java.io.*; import java.util.*; public class BOJ3055 { static int atoi(Str..

오답 노트 & 새로 알게 된 점 처음에 이 문제를 풀었을 때 어렵지 않은 bfs인 것 같았다. 그래서 예제를 다 맞고서 제출을 했지만 계속해서 틀렸다. 혼자서 반례를 생각해보니 visit배열을 이차원으로 했을 때 문제가 생긴다. 2 9 2 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 이동할 때 다른 경로의 이동을 방해(?)하기 때문이다. 만약 visit가 이차원 배열일 경우 위와 같은 경우는 -1이 나오게 된다. 말처럼 점프를 해서 먼저 좌표에 간뒤에, 인접 좌표로 먼저 visit을 할 경우에 다른 좌표는 올 수 없다. 그래서 visit배열을 3차원으로 해야한다. 벽 부수고 이동하기 문제가 생각이 났다. 왜 visit를 3차원으로 생각해야하는지 잘 설명해주신 글이 있다. https:/..

오답 노트 & 새로 알게 된 점 이 문제는 규칙성이 중요하다. 제일 처음 시작한 문자가 B일 경우와 W일 경우 아래와 같은 규칙이 나타난다. 홀수 + 홀수 = 짝수 홀수 + 짝수 = 홀수 짝수 + 짝수 = 짝수 처음 시작 문자가 B일 때 생각해보자. 홀수일 경우에는 W가 와야하고, 짝수일 경우에 B가 와야한다. 그래서 i+j가 홀수인데 W가 아니면 cnt를 늘리고, i+j가 짝수인데 B가 아니면 cnt를 늘린다. 이 때, 처음 시작 문자가 W일 때와 반대이기 때문에 64 - cnt를 하면 W일 때를 구할 수 있다. 그래서 cnt와 64-cnt 중 최소값을 리턴하면 된다. 그리고 모든 행과 열을 탐색하면서 최솟값을 찾으면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

오답 노트 & 새로 알게 된 점 문제를 보면 A에다가 앞, 뒤로 a~z까지 일일이 한 개씩 삽입한 뒤, 비교하려면 코드가 더러워지고 엄청 복잡할 것 같아서 다른 방법을 생각했다. 그래서 B를 가지고 문제를 해결해보려했다. B를 가지고 A의 길이가 될 떄까지 모든 경우의 수를 조사해보면 된다. 즉 A = abcde B = aabcdefgf일 때, (앞에서 뺀 갯수, 뒤에서 뺀 갯수)로 표현하면 (0,4) (1,3) (2,2) (3,1) (4,0)이 이다. 이 때 초기에 설정해야할 최댓값은 모든 문자가 다 다를 경우이다. 즉 A의 길이이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3..