요게 더 빠른 코드 이해가 안감 배열크기가 720000 360000 인데
using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
namespace ThisIsCShaps
{
class Program
{
static StreamReader sr = new StreamReader(Console.OpenStandardInput());
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static string[] str;
static int answer = 0,n;
static int[] arr, arr2;
static List<int> GetTable(string pattern)
{
int size = pattern.Length;
List<int> table = new List<int>();
for (int i = 0; i < size; i++)
{
table.Add(0);
}
int j = 0;
for (int i =1; i < size; i++)
{
while(j>0&&!pattern[i].Equals(pattern[j]))
{
j = table[j - 1];
}
if(pattern[i].Equals(pattern[j]))
{
j++;
table[i] = j;
}
}
return table;
}
static bool IsSame(string p,string p2)
{
List<int> table = GetTable(p2);
int size = p.Length;
int j = 0;
for (int i = 0; i < size; i++)
{
while(j>0&&!p[i].Equals(p2[j]))
{
j = table[j - 1];
}
if(p[i].Equals(p2[j]))
{
if(j.Equals(p2.Length-1))
{
//있다.
j = table[j];
return true;
}
else
{
j++;
}
}
}
return false;
}
static void Main(string[] args)
{
n = int.Parse(sr.ReadLine());
arr = new int[360000*2];
arr2 = new int[360000];
str = sr.ReadLine().Split();
StringBuilder p1=new StringBuilder(), p2=new StringBuilder();
for (int i = 0; i < str.Length; i++)
{
int idx = int.Parse(str[i]);
arr[idx]=1;
arr[idx+360000] = 1;
}
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].Equals(1))
{
p1.Append('1');
}
else
{
p1.Append('0');
}
}
str = sr.ReadLine().Split();
for (int i = 0; i < str.Length; i++)
{
int idx = int.Parse(str[i]);
arr2[idx] = 1;
}
for (int i = 0; i < arr2.Length; i++)
{
if (arr2[i].Equals(1))
{
p2.Append('1');
}
else
{
p2.Append('0');
}
}
if(IsSame(p1.ToString(),p2.ToString()))
{
sw.Write("possible");
}
else
{
sw.Write("impossible");
}
sw.Close();
}
}
}
이게 string으로 StringBuilder 사용해서 만든거 사용한 코드 이게 더 빠름
이게 무조건 더 계산이 많은데
이거 말고
using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
namespace ThisIsCShaps
{
class Program
{
static StreamReader sr = new StreamReader(Console.OpenStandardInput());
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static string[] str;
static int answer = 0,n;
static int[] arr, arr2;
static List<int> GetTable(int[] arrs)
{
int size = arrs.Length;
List<int> table = new List<int>();
for (int i = 0; i < size; i++)
{
table.Add(0);
}
int j = 0;
for (int i =1; i < size; i++)
{
while(j>0&&!arrs[i].Equals(arrs[j]))
{
j = table[j - 1];
}
if(arrs[i].Equals(arrs[j]))
{
j++;
table[i] = j;
}
}
return table;
}
static bool IsSame()
{
List<int> table = GetTable(arr2);
int size = arr.Length;
int j = 0;
for (int i = 0; i < size; i++)
{
while(j>0&&!arr[i].Equals(arr2[j]))
{
j = table[j - 1];
}
if(arr[i].Equals(arr2[j]))
{
if(j.Equals(arr2.Length-1))
{
//있다.
j = table[j];
return true;
}
else
{
j++;
}
}
}
return false;
}
static void Main(string[] args)
{
n = int.Parse(sr.ReadLine());
arr = new int[360000*2];
arr2 = new int[360000];
str = sr.ReadLine().Split();
StringBuilder p1=new StringBuilder(), p2=new StringBuilder();
for (int i = 0; i < str.Length; i++)
{
int idx = int.Parse(str[i]);
arr[idx]=1;
arr[idx +360000] = 1;
}
for (int i = 0; i < arr.Length; i++)
{
if (arr[i].Equals(1))
{
p1.Append('1');
}
else
{
p1.Append('0');
}
}
str = sr.ReadLine().Split();
for (int i = 0; i < str.Length; i++)
{
int idx = int.Parse(str[i]);
arr2[idx] = 1;
}
for (int i = 0; i < arr2.Length; i++)
{
if (arr2[i].Equals(1))
{
p2.Append('1');
}
else
{
p2.Append('0');
}
}
if(IsSame())
{
sw.Write("possible");
}
else
{
sw.Write("impossible");
}
sw.Close();
}
}
}
두개다 글자로 올려봐 'ㅅ'.. 비교가 힘들자나..
ㅈㅅ
수정했삼
여기서 해결안되면 네이버 지식인으로 내공 100으로 해결해야징 ㅠ
string은 char 끼리 비교하는거고, arr 는 int 끼리 비교하는거네 2가지 가정이 가능한데, 1. char 비교가 int 비교보다 약간 빠를 수 있음. 2. char 크기를 사용하니깐 cache hit률이 높을 수 있음.
int arr를 char arr 로 바꿔서 돌려 보던가
string을 사용한다고 연산이 많아 보이는 부분은 없는거 같은데
ㄳㄳ char가 int보다 빠른걸 첨앎
본인쟝도 윗댓이랑 같은 으견임. 코드창 두개 띄워놓고 같거나 시간복잡도를 생각햇슬때 거의 의미 없는 부분들을 지워나가면서 유의미한 차이를 보이는 코드를 찾으려고 햇는데 딱히 string을 이용한 쪽이 더 많은 계산을 한다고 볼 수 있을만한 코드를 발견하지 못햇슴 걍 char비교가 int비교보다 좀 더 빠른것 뿐인듯
ㅇㅎ char가 int보다 빠른 거였구만요.
정확히 입력의 길이가 어떻게 되는지 모르겠지만, 느린거는 GetTable(arr2) 호출에서 size가 항상 배열의 크기 360000가 되어서 입력이 작더라도 360000만큼 돌지만, GetTable(p2)는 string의 길이만큼 루프를 돌기 때문에(결국 더 적은 루프를 돔), 속도가 더 빠르게 나오는거 아닐까?
내가 쓴 글이 좀 헷갈리는데, 결론은 p1, p2로 비교하는것은 string의 길이만큼만 루프를 돌아서 그런거 같음. 항상 배열의 크기(360000)만큼 도는게 아니라...
string 길이가 배열 크기만큼 생성되서 똑같심. char가 int보다 빠른걸 처음 알았음 ㅎㄷㄷ ㄳㄳ 역시 고수님들
벤치마킹해보기전엔 모르겠지만 char랑 int 비교연산의 부하는 별 차이 없을거임. 어짜피 CPU 버퍼크기만큼 메모리에서 들고와서 비교연산할거라. 괜히 struct구조체에 byte변수 있으면 나머지 3,7바이트 padding 넣는게 아님. char가 int보다 캐시히트가 높을수도 있다는거는 신빙성이 있음. 보통 캐시라인이 64byte라고 하면 64byte안에서는 RAM에 접근할필요없어서 속도가 빠르다는 거임. char는 1바이트니까, 64번 연산하는데 RAM을 안거치는것. int는 4바이트라고 치면, 16번 연산을 RAM 안거치고 하는것. 어느게 더 빠르겠음? 이론상 4배 차이나네
와 이런 지식은 뭘 공부해야 알 수 있는거임? 지식에 감탄 ㅎㄷㄷ
공룡책이라고 있음. 그거에서도 본거같고, Unity Dots하다보면 캐시관련된 내용 많이 보게됨.
일반적으로 메모리 적게 쓰면 성능도 올라감
이유야 뭐 다른사람들이 많이 얘기해준 캐시 문제도 있을수 있고, 본문 코드엔 상관 없는 얘기지만 큰 할당/해제 자체가 부하일수도 있고
ㅇㅇ 이말이맞을수도있음. 메모리 할당해제같은게 있을수도. 그래서 벤치를 돌려봐야하는거.
이제그만. 이런걸로 토론하다니... 대충 알았다... 너희들 레벨... 시시해서 죽고싶어졌다.
니가 답변해줬으면 우리가 할 필욘 없었잖아
이걸 모르고 플레티넘 난이도 문제를 푼게 더 신기하구만. 문자열 문제로 변환해서 푸는 문제라니 신박하네.