![]()
로직은 이렇게 구성했습니다. 만약 이렇게 key의 크기가 3*3이고 lock의 사이즈가 4일때 (빨간 곳은 겹치는 배열) 이러한 배열을 만드시는 분들이 많더라구요. 그런데 어차피 탐색을 할 때 기준점을 키의 왼쪽 위 즉 이렇게 잡는다면 만든 큰 배열에서 기준점이 들어갈 수 있는 곳은 배열의 크기보다 꽤나 작습니다. 연두색 부분은 검사를 할 필요도 없는 부분입니다. 기준점이 연두색 부분에 있으면 모든 값이 자물쇠 바깥의 값들이니까요. 이렇게 한다면 배열의 크기를 (자물쇠의 크기+(열쇠의 크기-1)*2)^2 에서 (자물쇠의 크기+열쇠의 크기-1)^2로 줄일 수 있습니다. 짠돌이 호석의 경우 무조건 정사각형도 아니고 크기도 어떤것이 크다! 라고 하기 애매한 것들도 많아서 구현에 실패했었지만 이 문제는 가능할 ..
![]()
투 포인터 안한지 하도 오래되서 그런지 엄청 어려웠습니다.. 투 포인터인 것은 바로 알았는데 투 포인터를 어떻게 이용해야 하는지 감 잡기가 어려운 문제였던 것 같습니다. 0. 무조건 투 포인터 문제일 것 0.1 DP로 풀려면 10만*10만의 배열이 필요할 것 0.2 그냥 탐색을 하려면 엄청 큰 시간복잡도 1. gems를 Set화한 크기를 무조건 알아야 함, 2. 방문과 방문횟수에 사용할 딕셔너리(맵)가 필요함, 딕셔너리를 채워나가며 코드를 진행 2.1 방문하지 않은 보석을 방문하면 딕셔너리의 크기들을 더해주면 1+2+3+4...n n(n+1)/2임 n은 set화 했던 크기 (취소) 2.2 굳이 저럴 필요 없이 len으로 비교해줘도 가능할 듯 2.3 두 방법 모두 딕셔너리에서 del을 통한 크기 비교 및 ..
처음 문제를 봤을 때 set이나 map을 사용해야 될 것 같긴 했는데 전반적인 풀이 방법이 떠오르지 않아 다른 사람 코드를 참고했습니다. 효율성을 따진다는 것 + 보석의 개수가 최대 10만 개라는 점에서 모든 경우를 다 탐색한다는 것은 시간 초과가 날 것이라 생각했고, 풀이를 보니 투 포인터를 사용하는 것이었습니다. 투 포인터 문제를 많이 풀어보지는 않았지만 보석 쇼핑과 같이 연속되는 데이터를 찾는 문제(?) 유형에 많이 사용되는 것 같습니다. 풀이 방법 map에 보석의 종류와 개수를 담아줍니다. 보석의 종류를 중복 없이 담기 위해서 set을 사용합니다. 아래와 같이 set을 선언하면 gems vector의 처음부터 끝까지 중복되지 않게 데이터를 set에 담아줍니다. 보석의 종류를 다 포함하는 최소의 e..
![]()
정확성은 통과하는데, 효율성 테스트를 잘 통과하지 못하고 있습니다 ㅠ__ㅠ 살펴보니 효율성까지 통과하려면 맵 자료형(파이썬의 딕셔너리)을 활용해야 하는 것 같은데... import sys maxCount = sys.maxsize def checkGem(gemSet, gems): compSet = set(gems) if gemSet == compSet: return True return False def makeGemSet(gems): gemSet = set(gems) return gemSet def solution(gems): maxCount = sys.maxsize ansLeft = 0 ansRight = 0 gemSet = makeGemSet(gems) left, right = 0, 0 while T..
기본 틀은 짠돌이 호석과 비슷하게 풀었습니다. 짠돌이 호석 문제를 풀어봐서 그런지 딱 봤을 때 어떻게 접근을 해야 할지는 바로 보였던 것 같습니다. lock을 고정시킨 뒤에 key의 위치를 옮기고, 회전시키면서 정답이 나오는지(lock의 0 부분을 1로 다 채울 수 있는지) 체크해주었습니다. background에서 key의 배열을 더해주고 난 뒤(lock의 1과 key의 1이 겹치지 않고, key의 0과 lock의 0이 겹치지 않으면 무조건 1이 나오게 된다.), lock 부분에 0이 있거나 2가 있다면 정답이 될 수 없기 때문에 그런 경우 check 함수에서 바로 false를 return 합니다. 다른 부분보다 vector의 구조를 이번 문제처럼 사용해본 적이 없어서 background 선언 형식을 참..
저번에 풀었던 짠돌이 호석과 같은 방법으로 접근했습니다. lock을 가운데에 놔두고 key를 4방향으로 돌려가며 모두 탐색했습니다. map의 크기는 N + 2M이면 될 것 같아 N + 2M으로 설정했습니다. 지난번과는 조금 다르게 check를 하는 부분에서 값을 더하고 check하고 빼주면서 확인했습니다. #include #include #include using namespace std; int N,M; vector map, key, lock; bool answer; void rotate(vector& key){ vector temp(M,vector(M)); for(int i = 0; i
물류센터를 갔다와서 너무 피곤한 관계로 예상 풀이만 적어두고 나중에 풀어볼 생각입니다 ㅠ... 일단 최근에 풀었던 짠돌이 호석과 똑같은 풀이라고 생각합니다. https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 짠돌이 호석은 입력이 50까지이고, 정사각형이 아닌 직사각형이 주어질 수 있고, 직사각형이므로 어떤 블럭을 기준으로 해야 할지 난감하고, 직사각형이므로 돌렸을 때 모양이 바뀌기도 하므로 지금 보니 오늘 풀어야 ..
![]()
정말 오랜만에 문제를 해결한 것 같아 뿌듯하네요! 풀이는 다음과 같습니다. (자물쇠의 한 변의 크기는 M, 열쇠의 한 변의 크기는 N이라고 하겠습니다.) 1. 자물쇠를 이동시킬 수 있는 영역을 마련하기 위해 M + 2 * (N - 1) 크기의 배열을 생성합니다. def createExtendedMatrix(key, lock): M, N = len(key), len(lock) extended = [[0] * (M + 2 * (N - 1)) for _ in range(M + 2 * (N - 1))] for row in range(M - 1, M + N - 1): for col in range(M - 1, M + N - 1): extended[row][col] = lock[row - M + 1][col - M..
이번 문제 또한 풀이를 참고하여 풀었습니다. 접근을 하려고 했던 방식은 틀리지 않았는데 동전 두 개의 좌표를 한꺼번에 bfs에 넣어야 된다는 것을 생각하지 못했습니다. 몇 문제 풀다 보니까 백트래킹에 대해서 알듯 말듯한 느낌입니다. 참고한 코드가 짧고 이해하기 편했던 것 같습니다. 풀이 방법 주석에도 간단하게 적어놓긴 했지만 몇 군데 포인트 되는 부분만 설명을 해보겠습니다. 1. 이동하려는 칸이 동전이어도 이동이 가능하기 때문에 입력을 받으면서 'o'일 경우 vector에 넣고, '.'로 바꾸어주었습니다. 2. coin[0]의 first는 1번째 동전의 x좌표, coin[0]의 second는 1번째 동전의 y좌표입니다. 마찬가지고 coin[1]의 first는 두 번째 동전의 x좌표, second는 두 번..
![]()
보실 분이 있으실지는 모르겠지만 열심히 구상한 테스트케이스들입니다..! # k값과 문자열을 구성하는 알파벳 개수가 같을 때 제대로 출력되는지 확인, 1 5 antatica 답 : 1 # 문자열을 구성하는 알파벳 개수보다 k값이 작은 경우 제대로 출력되는지 확인, 1 4 antatica 답 : 0 # 문자열을 구성하는 알파벳 개수보다 k값이 큰 경우 제대로 출력되는지 확인, ★ 이거때매.. 1 10 antatica 답 : 1 # 제대로 쪼개졌는지 확인, 3 5 antatica antaaatica antaaaaatica 답 : 3 # a,i,t,n,c 제대로 빠지고 잘 작동하는지 확인 3 5 antaxxxxtica antaltica antaltica 답 :0 # 위와 같음 3 6 antaxxxxtica an..
딱히 뚜렷한 방법이 생각이 나지 않았습니다.. 그래서 그냥 맨 처음 생각났던 '한번에 두개 해보자'로 풀기 시작했습니다. from sys import stdin input=stdin.readline dx,dy=[0,0,1,-1],[1,-1,0,0] n,m=map(int,input().split()) board=[list(input().rstrip()) for i in range(n)] vi1=[[0 for i in range(m)]for i in range(n)] vi2=[[0 for i in range(m)]for i in range(n)] coins=[] ans=11 for i in range(n): for j in range(m): if board[i][j]=='o': coins.append((j,..
![]()
검사해야 할 것들은 주어진 좌표의 가로줄, 세로줄 그리고 스도쿠 판을 9개로 나누었을때 속해있는 그 칸의 9개의 나머지 블럭들 이 3가지입니다. 사실 그냥 시간을 전혀 신경쓰지않는다면 간단하게 정답을 구할 수 있지만 문제의 경우는 다음이라고 생각했습니다. # 이것만 오래 안걸리면 나머지 다 맞을듯 ''' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ''' 위의 테스트 케이스만 빠르게 해결할 정도라면 문제를 맞추는 것은 어렵지 않다고 생각했고, 이것으로 계속 테스트를 ..
