정렬하면 길이가 더 짧고 더 작은 수가 앞으로 온다 따라서 앞의 문자열 길이 만큼 뒤에 오는 문자열을 잘라서 앞의 문자열과 같은지 보면 된다 def solution(book): book.sort() for i in range(1,len(book)): a,b=book[i-1],book[i] if b[:len(a)]==a: # print(b[:len(a)],a) return False return True
연속된 부분 수열은 아니고 각 문자열을 이루고 있는 문자들 순서만 맞춰서 최장 공통 부분 수열을 구하는 문제이다 a, b 두 문자열의 길이 +1 (각 첫번째 인덱스에 들어가는 값은 초기값인 0이다.) 인덱스 i,j를 비교해서 a와 b의 각 위치에 들어간 문자가 같다면 이전 최대 길이 +1 을 해주면 된다. 1: acaykp , 2: capcak에서 1의 부분 문자인 a(인덱스 0)만 봤을 때 2에서 c인 경우 0, ca인 경우 1 이런식으로 추가되는 문자가 같다면 1 증가시키는 식으로 해결한다. import sys input=sys.stdin.readline a=input().strip() # 엔터키도 들어가지 않도록 b=input().strip() # print(a,len(a)) dp=[[0]*(len..
어렵다.. 수학적 계산 들어가는 문제는 다 어렵다ㅠㅠ 어떡하지 a= s 집합이다 집합 가장 앞에 0을 추가하여 예외 상황 (s집합이 1개일 때, s집합에 있는 수보다 n이 작을 때 등)을 처리해준다 s집합의 원소보다 n이 작다면 right=원소-1 이고 n이 더 크다면 다음 구간도 가능한 지 찾는다 left=원소+1 1 2 3 4 5 에서 left=1, right=5, n= 3이라면 가능한 경우의 수는 3을 포함하는 경우의 수 right-left (4가지이고) (1,3) (2,3) (3,4) (3,5) 3이 경계값이 아닌 포함하는 구간은 (n-left)*(right-n)이다 (1,4) (1,5) (2,4) (2,5) import sys input=sys.stdin.readline l=int(input()..
www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net abbcd인 경우 abbcd bbcd bcd cd d (d하나는 팰린드롬임) 이렇게 검사해나가서 펠린드롬이 아니었던 abbc를 뒤집어서 d오른쪽에 cbba이렇게 붙인다고 가정한다. 즉 부분문자열이 팰린드롬이 되기까지의 왼쪽 문자열 개수만큼 더해주면 그게 답이다 s=input() for i in range(len(s)): if s[i:]==s[i:][::-1]: print(len(s)+i) break
예시 1 2 3 4 5 6 7 8 9 10 11 cur (설치할 기지국 위치는 1에서 시작) w가 1인 경우 다음 기지국 설치 위치를 cur+2*w+1 하는 이유는 cur는 1을 기준으로 해도 사실상 2에 설치해서 1(기준 위치)~2(실제 설치 위치)~3을 커버하는 거라고 보면 된다 즉 기준위치는 cur인 1이지만 실제 설치 위치는 2인 것이고 cur+2*w+1이 다음 새로 설치 가능한지 보는 이유이다. cur(기준 위치)가 stations[idx]-w (기존 기지국이 닿는 범위)보다 작아야 기존 기지국 위치와 겹치지 않는다. 겹친 다면 기지국이 닿는 오른쪽 전파범위 (stations[idx]+w)+1인 위치를 다음 기준 위치(cur)로 잡는다. def solution(n, stations, w): an..
1의 개수만큼 계속 문자열이 '1'이 될 때까지 이진 변환을 해준다. n은 이진 변환한 횟수, c는 삭제한 0의 개수이다. 0의 개수는 계속 더해주며 1의 개수만큼 이진변환을 해준다. def solution(s): n=0 c=0 while s!='1': c+=s.count('0') s=str(bin(len(s)-s.count('0'))[2:]) n+=1 return [n,c]
현재 숫자를 3진법으로 만든 뒤 뒤집어서 다시 10진법으로 변환한다 def solution(n): answer = 0 convert='' while n: a,b=divmod(n,3)//몫, 나머지 convert=str(b)+convert // 새로운 나머지수가 더 먼저 와야된다 (나눠보면서 이해) n=a // 새로운 몫 return int(convert[::-1],3) //3진법을 10진법으로 변환하는 방법
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 부분 수열의 길이만 구하는 문제고 실제 어떤 원소가 부분 수열을 이루고 있는지나 해당 원소의 인덱스를 구하는 문제가 아니라서 쉽게 구할 수 있다. 심지어 이 문제는 O(N*2)을 해도 풀리기 때문에 (1초= 10^9를 넘어가지 않으면 된다) 이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되..
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net from collections import deque import math from itertools import combinations import copy n,m=map(int,input().split()) a,blank,virus=[],[],[] dy,dx=[1,-1,0,0],[0,0,1,-1] for y in range(n): tmp=list(map(int,input().split())) a.append(tmp) ..
10진수에서 xor 연산은 0^0 = 0 4^4=0 4^0=4 짝수번 등장은 0으로 초기화되고 홀수번은 다시 자기 자신으로 초기화된다 class Solution: def singleNumber(self, nums: List[int]) -> int: result=0 for num in nums: result^=num return result