본문 바로가기

코딩테스트38

LeetCode - 36. Valid Sudoku - swift https://leetcode.com/problems/valid-sudoku/ Valid Sudoku - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 간단한 스도쿠 판별문제다. 행, 열, 그리고 3*3 행렬안에 중복된 숫자가 있는지 판별하는 문제다. 조건대로 행, 열을 모두 판별하면서, 3*3 행렬안에 중복된 숫자가 있는지 판별하는 것을 구현하면 된다. 3*3행렬은, i / 3, j / 3 으로 나눈값으로 판별했다. class Solution { func is.. 2021. 8. 20.
LeetCode - 31. Next Permutation - swift https://leetcode.com/problems/next-permutation/ Next Permutation - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 숫자 배열을 통해, 그다음의 순열을 찾는 문제다. 만약 다음 순열이 존재하지 않는다면, 오름차순으로 정렬된 배열로 만들고, 존재한다면 그 다음의 순열로 배열을 만든다. 조금만 고민하면, 특징을 찾을 수 있다. 다음의 순열이 되기 위해서는, 배열의 끝부분부터 탐색하면서, 현재 위치보다 -1 한.. 2021. 8. 20.
LeetCode - 15. 3Sum - swift https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 숫자가 들어있는 배열( arr ) 이 주어지는데, 이 배열에서, arr[ i ] + arr[ j ] + arr[ k ] == 0 이면서, i != j 이면서 j != k 이면서 i != k 인 경우의 [ arr[i] , arr[j], arr[k] ] 들을 찾는 문제다. 2개 이상의 경우에는 나름의 최적화가 필요하다. arr의 개수는 최대 3.. 2021. 8. 18.
LeetCode - 12. Integer to Roman - swift https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 구현 문제다. 말 그대로 숫자를 로마 표기법으로 변환하는 방법이다. 1,5,10,50,100,500,1000 이렇게 각 값마다 표기하는 로마 표기법이 있고, 8은 VIII 이렇게, 큰숫자부터 앞에서 쓴다. 하지만.. 4는 IIII가 아닌, IV 이다 ! ( ??? ) 9는 VIIII가 아닌, IX .. 2021. 8. 18.
LeetCode - 22. Generate Parentheses - swift https://leetcode.com/problems/generate-parentheses/ Generate Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 숫자 n이 주어지는데, 올바른 괄호의 짝의 개수를 뜻한다. n이 1이면 () 이 올바른 괄호이고, n이 2이면 ()(), or (()) 이 올바른 괄호다. n이 3이면 ()()() or (())() or ()(()) or (()()) or ((())) 이 올바른 괄호다. 이렇게 n이 .. 2021. 8. 18.
LeetCode - Count Good Nodes in Binary Tree - swift https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/615/week-3-august-15th-august-21st/3899/ 문제는 Good 이라는 노드의 개수를 찾는 것인데, Good 노드인 경우는, root노드로부터 x노드까지 가는 경로에 x노드보다 큰 값이 없는 경우에 Good 노드라고 한다. 노드의 개수는 최대 10만개이다. 간단한 이진트리를 탐색하는 문제다. 자식노드들이 Good노드이냐 아니냐만 판별하여 카운팅하면 된다. 모든 노드들을 방문하므로, O(N)이 걸린다. 그러므로, 매번 자식노드들을 탐색할때, 지금까지 방문한 노드들의 값의 최대값을 저장하면서 현재 노드와 값을 비교하면 된다. class Soluti.. 2021. 8. 17.
프로그래머스 - 위클리 챌린지 3주차 - 퍼즐 조각 채우기 - swift https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 구현문제에 완전탐색과도 같다. 여기서 핵심을 빠르게 짚어야하는데, 조각을 보드판에 채우기위해서는 꼭 맞아떨어져야 한다는 점이다. 즉, 하나의 .. 2021. 8. 17.
백준 1561 - 놀이공원 - swift https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 꽤나 정답비율이 낮은 편에 속하는 문제다. 이렇게 낮은문제는 한번에 떠오르는 생각만으로 접근하다보면은 틀리기 십상이다. 그러므로 예외처리나, 더 세세하게 경우들을 생각하거나, 구현을 잘해야한다. 일단 N이 20억으로, 한명한명 모두 태워보며 마지막을 찾기란 시간초과다. 그러므로 시간안에 풀수있는 효율적인 방법이 필요하다. "시간"을 기준으로 문제를 접근해본다... 2021. 8. 5.

티스토리툴바