본문 바로가기

2020/0316

[leetcode][139] Word Break 문제 : https://leetcode.com/problems/word-break/ 문자열 s, 단어 리스트가 주어질 때 단어 리스트들로 문자열 s를 만들 수 있는지 구하는 문제. 단어는 사용하지 않아도 되고 여러번 사용해도 된다. DP로 해결했다. dp[i] = s[i..]를 단어 리스트로 만들 수 있는지 여부(true, false) 저장. index를 기준으로 s[index]와 문자[0]가 같다면 s[index~] prefix가 문자와 같은지 비교하고 같다면 index+문자길이를 index로 다시 탐색한다. 만약 탐색중 dp[index]가 이미 있다면 이를 반환한다. (이미 s[index..]를 탐색했다는 것을 의미) 시간복잡도는 O(|s| x |wordDict|). 문자가 같은지 비교해야 되기 때문.. 2020. 3. 18.
[leetcode][567] Permutation in String 문제: https://leetcode.com/problems/permutation-in-string/ 문자열 s1, s2가 주어졌을 때, s2 서브 문자열에서 s1 문자열 문자들이 전부 존재하는지 구하는 문제. 예를 들어, s1="ab", s2="eidbaooo" 라면 true. s1="ab", s2="eidboaoo" 라면 false. 투포인터로 풀었다. 문자열 s1을 전부 탐색하면서 문자개수를 저장한다. (let, arr) s2 서브 문자열 범위의 시작 위치와 종료 위치를 변수 s, e에 저장한다. s2 문자열을 탐색하면서 탐색 중인 문자 위치를 e라 하자. (let, nowChar = s2[e]) 만약 arr[nowChar] 이 0 보다 크다면 arr[nowChar]를 1 감소시키고 다음 문자를 탐.. 2020. 3. 10.
[leetcode][1319] Number of Operations to Make Network Connected 문제 : https://leetcode.com/problems/number-of-operations-to-make-network-connected/ 컴퓨터의 총 개수와 네트워크 연결 여부를 저장한 배열이 주어졌을 때, 모든 컴퓨터들이 네트워크에 연결하기 위해 이동이 필요한 네트워크 연결 수 를 반환하는 문제. (불가능하다면 -1) 최소 신장 트리의 간선 수는 N-1개이다. 비슷하게 이 문제에서 불가능한 네트워크 개수는 컴퓨터의 총 개수 - 1 보다 작은 경우들이다. 이 경우를 만족한다면 모든 컴퓨터들이 네트워크에 연결이 가능하다. Union-Find를 이용해서 네트워크 번호를 하나의 배열에 저장한다. 즉, a, b 컴퓨터가 같은 네트워크에 있다면 배열[a], 배열[b]는 같은 값을 가진다. 네트워크 배열.. 2020. 3. 7.
[leetcode][79] Word Search 문제 : https://leetcode.com/problems/word-search/ 2차원 문자 배열, 단어가 주어지면 배열에 단어의 유무를 리턴하는 문제. 신문 단어 퍼즐 같은 문제. DFS로 풀었다. 문자열 배열을 탐색하면서 탐색중인 인덱스를 시작 위치로 하여 단어가 있는지 판단한다. // board: 2차원 문자 배열 // word : 찾는 단어 // board[x][y]를 시작 위치로 하여 word가 있는지 find(board, x, y, word): // 경계 체크 if(x, y 이미 방문) return false if(board[x][y]와 word의 첫 번째 문자가 같지 않다면) return false ans = false x, y 방문 체크 for(nx, ny = 상, 하, 좌, 우 이동.. 2020. 3. 7.

티스토리툴바