Spring에서는 Static resource와 Dynamic resource를 분리해, static resource 응답을 빠르게 해줄 수 있도록 지원한다.
요구사항 1. /hello 요청 시 resources/templates/static.html 페이지가 응답할 수 있도록 설정
=> localhost:8080/hello 요청이 들어오면 내부에서 resources/templates/static.html 정적 파일을 보여줄 수 있도록 설정
요구사항 2. 쿼리 파라미터로 name 요청이 들어왔을 때 해당 값을 hello.html에서 사용할 수 있도록 하기
=> 쿼리 파라미터로 name 요청이 들어왔을 때, 해당 값을 hello.html에서 보여주기
1. 컨트롤러 메서드 작성
2. 쿼리 파라미터로 전달된 값을 'hello.html'템플릿에서 사용할 수 있도록 하기
[@GetMapping]
: Spring Framework에서 제공하는 어노테이션
HTTP GET 요청을 처리하기 위해 사용된다. 이 어노테이션을 사용해, 특정 URL 경로에 대한 GET 요청을 특정 메서드에 매핑할 수 있다.
이는 주로 RESTful 웹 서비스에서 데이터를 조회하는 용도로 사용된다.
*매핑(mapping): 특정 URL 요청을 특정 메서드에 연결하는 것을 의미한다.
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class MyController {
@GetMapping("/hello")
public String sayHello() {
return "Hello, World!";
}
}
@GetMapping("/hello")는 "/hello" 경로로 들어오는 GET 요청을 'sayHello' 메서드에 매핑한다.
따라서 사용자가 브라우저에서 'http://localhost:8080/hello'로 접근하면, "Hello, World!"라는 문자열을 응답으로 받게 된다.
(@GetMapping은 @RequestMapping 어노테이션의 축약형으로, 아래와 같은 방식으로도 구현이 가능하다. )
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class MyController {
@RequestMapping(value = "/hello", method = ReqeustMethod.GET)
public String sayHello() {
return "Hello, World!";
}
}
=> @GetMapping은 코드의 가독성을 높이고 RESTful 서비스 개발을 편하게 만들어 준다.
@RestController는 이 클래스가 RESTful 컨트롤러 임을 나타낸다.
그러면 RestController는라우터는아닌거지?=> yes
: @RestController는 Spring Framework에서제공하는어노테이션으로, 해당클래스가 RESTful 웹서비스의엔드포인트를정의하고있다는것을나타냄
그러나, 이것 자체는 라우터는 아님.
그냥 라우팅 설정역할을 하는 메서드와 함께 사용될 뿐임
Spring에서 라우팅을 담당하는 부분
:@RequestMapping
@GetMapping
@PostMapping 등의 어노테이션
위 어노테이션들이 HTTP 요청을 특정 메서드에 매핑함.
@RestController는 위 어노테이션을 포함하는 클래스이고, RESTful API를 제공한다는 의미를 가짐.
Membercontroller.class
package cholog;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;
@Controller
public class MemberController {
@GetMapping("/hello")
public String world(@RequestParam (name = "name", required = false, defaultValue = "World") String name, Model model) {
// TODO: /hello 요청 시 resources/templates/static.html 페이지가 응답할 수 있도록 설정하세요.
// TODO: 쿼리 파라미터로 name 요청이 들어왔을 때 해당 값을 hello.html에서 사용할 수 있도록 하세요.
model.addAttribute("name", name);
return "static";
}
public Person json() {
// TODO: /json 요청 시 {"name": "brown", "age": 20} 데이터를 응답할 수 있도록 설정하세요.
return null;
}
}
그동안 나혼자 이상한거하고 있었는듯; main에서 가이드 안보고 코드부터 뜯을 생각(MemberController부터 할 생각)했음
먼저 구성된 정적 콘텐츠 위치(main/resources/static/)에서 index.html 파일을 찾습니다. 하나라도 없으면 index 템플릿 (main/resources/templates/)을 찾는다. 둘 중 하나라도 찾으면 자동으로 응용 프로그램 시작 페이지로 사용된다.
처리 방법: 일단 main에 있는 resources/static/hi.html 의 이름을 index.html로 바꾸고 실행하니까 테스트 통과함
처리 방법: 일단 main에 있는 MemberController 코드 수정하고 name 코드가 있는 경우와 없는 경우 조건문으로 반환값 다르게 작성해줌. 단, 쿼리 파라미터가 없는 경우에는 static을 반환해야한다고 기존 코드 가이드라인 주석에 적혀있었는데, static.html은 static폴더에만 존재했는데 아마 자동으로 static폴더에서 static.html을 반환하지 않았나 싶음.. 맞는지 확인 필요함
4. Json 응답
컨트롤러 메서드(웹 요청을 처리하는 함수)의 리턴타입을 그대로 body에 담아 응답하기 위해서는 @ResponseBody를 활용할 수 있음
해당 어노테이션을 사용하면, 컨트롤러 메서드가 반환하는 데이터를 그대로 웹 응답의 본문(body)에 담아 보낼 수 있음
해당 상황은 다음과 같이 비유하여 설명할 수 있음.
: 친구에게 편지를 보내는 상황이고, 편지지에 글을 써서 편지 봉투에 넣어 보낼 수 있는 상황임.
그러나 친구가 바로 편지가 쓰여진 편지지을 받고 싶어 한다면, 편지 봉투 없이 바로 편지만 보낼 수있음
편지지에 글을 쓰고 편지 봉투에 넣는 것 => 컨트롤러 메서드가 HTML 페이지를 반환하는 것을 의미함
편지지를 바로 보내는 것=> 컨트롤러 메서드가 데이터를 그대로 웹 요청의 응답으로 보내는 것이고, 이때 @ResponseBody를 사용
import sys
n=int(sys.stdin.readline())
total=[]
minn=2100000000
maxx=0
for i in range(n):
# 입장시간, 퇴장시간
e, x = map(int, sys.stdin.readline().split())
#print(e, x)
if e<minn:
minn=e
if x>maxx:
maxx=x
total.append([e,x-1])
#print(minn, maxx)
total
tmp=[]
for i in range(maxx):
tmp.append(0)
for i in total:
s, e = i
for i in range(s, e+1):
tmp[i]+=1
#print(tmp)
check = 0
start = -1
end = -1
result = []
cnt=0
for i, value in enumerate(tmp):
if value == max(tmp):
if start != -1:
check=1
continue
else:
#최초로 넣을때
check=1
start = i
result.append(i)
cnt+=1
start=-1
else:
if check==1:
check=0
end=i
result.append(i)
end = -1
#print(result)
print(max(tmp))
origin = result[0]
originEnd = 0
originStart=0
for i, value in enumerate(result):
if i ==0:
originStart=value
continue
if origin +1 == value:
origin+=1
else:
originEnd=result[i-1]
break
if originEnd==0:
originEnd=result[-1]
print(originStart, originEnd)
정답 코드
(주석 있는 버전)
import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
d = defaultdict(int)
print('defaultdict', d)
for i in range(n):
s, e = map(int, input().split())
d[s] += 1
d[e] -= 1
m, cnt = 0, 0 # cnt는 모기 마릿수 m은 최대갱신 모기 마릿수
tem, txm = 0, 0# 최댓값 갱신시 시간과 갱신 해제시 시간
flag = False
for i in sorted(d.keys()):
print(i)
cnt += d[i]
# 기존 최대 모기수 보다 현재 모기수가 더 클때
# == 최고일때만 계산함
if cnt > m:
m = cnt
tem = i
flag = True
# 현재 모기수 cnt보다 최대 갱신 모기수가 더 크고
# 만약, 현재 값이 모기가 나가는 타이밍일때
# 현재 모기수에서 지금 시간의 모기를 빼면 음수값이라 더한 격이 되어
# 지금 나간 모기를 더했을때의 값 = 최대값이 m인 경우이다.
# FLAG가 TRUE인 상태
# 마찬가지로 최고자리가 박탈 됐을때 계산함
elif cnt < m and cnt - d[i] == m and flag:
txm = i
flag = False
print(m)
print(tem, txm)
(주석 없는 버전) - 변수명 변경됨
import sys
from collections import defaultdict
input = sys.stdin.readline
n=int(input())
dict = defaultdict(int)
for i in range(n):
# 입장시간, 퇴장시간
e, x = map(int, input().split())
dict[e] += 1
dict[x] -= 1
maxx, nowMos = 0, 0
startTime, endTime = 0, 0
flag = False
for i in sorted(dict.keys()):
nowMos += dict[i]
if nowMos > maxx:
maxx = nowMos
startTime = i
flag = True
elif nowMos < maxx and nowMos - dict[i] == maxx and flag:
flag = False
endTime = i
print(maxx)
print(startTime, endTime)
시간/공간 복잡도
입력값보다 입력값의 값의 범위가 워낙 커서 웬만하면 N으로 구현해야 했다.
최적화 및 개선
기존에는 입력값의 범위를 전부 순회하면서 최대 모기수를 체크해서 시간초과가 발생했었다.
이런 방식의 관점을 바꿨다.
=> 현재 방에 있는 모기의 수가 갱신이 되는 모기의 수일 경우에만 체크
어려웠던 점
시간복잡도에 대한 개념은 알고있지만, 여전히 문제 풀기전에 시간복잡도에 대한 계산을 하는것이 어렵다.
파이썬의 경우 1초에 최대 연산횟수가 logN인 알고리즘으로 계산해도 최대 연산 횟수가 10억번인데, 이 문제의 경우 값의 범위가 10억을 훌쩍넘어 20억쯤 된다. 이런 경우는 시간복잡도 계산을 어떻게 해야하는지 모르겠다.
알게된 것
sys모듈의 sys.stdin.readLine() 함수를 input 변수로 저장 할 생각을 못하고 계속 수기로 작성해왔었는데 이제는 변수로 저장할 줄 알게됐다.
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[ [0] * m for i in range(n)]
print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
print('checkcnt: ', cnt)
cnt+=1
print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
check = 1
else:
print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
if cnt <=3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
print('hi')
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[ [0] * m for i in range(n)]
print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
print('after',tmpList)
print('checkcnt: ', cnt)
cnt+=1
print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
check = 1
else:
print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
print('hi')
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
#print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[[0] * m for i in range(n)]
#print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
#print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
# print('after',tmpList)
# print('checkcnt: ', cnt)
cnt+=1
# print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
# print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
# print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
# print('리턴 visited', visited)
return visited, check
check = 1
else:
# print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
# print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
# print('hi')
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
# print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
#print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys
#import copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
#print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[[0] * m for i in range(n)]
#print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
#print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
# print('after',tmpList)
# print('checkcnt: ', cnt)
cnt+=1
# print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
#rem = copy.deepcopy(visited)
rem = [item[:] for item in visited]
# print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
# print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
#visited=copy.deepcopy(rem)
visited=[item[:] for item in rem]
check = 0
# print('리턴 visited', visited)
return visited, check
check = 1
else:
# print("뭐지 nr:", nr, "nl:", nl)
#visited=copy.deepcopy(rem)
visited = [item[:] for item in rem]
check = 0
# print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
# print('hi')
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
# print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
#print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
정답 코드
import sys
n, m, k = map(int, sys.stdin.readline().split())
# 스티커 받고, 스티커 함에 넣기
stickerPocket = [] # 모눈종이 각각 map 모음
stickerPocketEntire=[] # 모눈종이 r, l 모아놓는 함
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
sticker=[]
for j in range(r):
tmp = list(map(int, sys.stdin.readline().split()))
sticker.append(tmp)
stickerPocket.append(sticker)
# 붙여졌나요?
visited=[[0] * m for i in range(n)]
# 90도 회전 함수
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# (90, 180, 270)도에 해당하게끔 3번만 돌림
sticker = stickerPocket[i]
nn=len(sticker) # 기존의 행을 열로 사용
mm=len(sticker[0]) # 기존의 열을 행으로 사용
newSticker =[]
for qq in range(mm):
tmp=[]
for pp in range(nn-1, -1, -1):
tmp.append(sticker[pp][qq])
newSticker.append(tmp)
stickerPocket[i]=newSticker
stickerPocketEntire[i]=[mm, nn]
# 회전카운트 증가시킴
cnt+=1
return cnt
def backtrack(p, q, i, visited):
# 스티커를 붙일 수 없을 경우, 붙이려는 스티커를 붙이기 전 상태로 돌아오기위한것
rem = [item[:] for item in visited]
# 붙이려는 스티커의 행열 조회
r, c = stickerPocketEntire[i]
for j in range(r): # 행
for jj in range(c): # 열
#왼쪽 위부터 조회
nr = p+j # 행/ 기존 행:n
nc = q+jj # 열/ 기존 열:m
# 스티커가 노트북 범위 안에 들어오면
if 0<=nr<n and 0<=nc<m:
# 모눈종이에서 붙여야 하는 지점인 경우
if stickerPocket[i][j][jj]==1:
# 미리 붙여진 스티커가 없다.
if visited[nr][nc]!=1:
# 스티커 붙이기
check = 1
visited[p+j][q+jj]=1
# 미리 붙여진 스티커가 있다. 겹친다.
else:
# 스티커를 붙이기 전(원래대로)으로 돌아가기
visited=[item[:] for item in rem]
# 스티커를 못붙였다는 표식
check = 0
return visited, check
# 모눈종이에서 빈칸인 경우
else:
continue
# 스티커가 노트북 범위 안에 못을어오면
else:
# 노트북 원상복구
visited = [item[:] for item in rem]
# 스티커를 못붙였다는 표식
check = 0
return visited, check
# 스티커를 정상적으로 붙인 경우
if check == 1:
return visited, check
# 시작 스티커 번호
i=0
# 붙일 스티커 번호가 증가한 후 한번도 스티커를 회전한적 없는경우를 가리기 위한 변수
first=1
# 회전 횟수
cnt=0
# 스티커를 붙이지 않았다는 표식
check=0
needRotation=0
while(1):
rotat=0
# 붙일 스티커가 없는 경우 종료
if i == k:
break
# 스티커의 행 열
r, c = stickerPocketEntire[i]
# 스티커의 행이나 열중 하나가 노트북을 벗어나는 경우
if n<r or m<c:
#스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 들어가는 경우
if c<=n and r<=m:
if cnt <3: # 0-0, 90-1, 180-2, 270-3
cnt = rotation(cnt, i)
rotat = 1
# 회전을 4번다 한 경우, 다음 스티커로 넘어감
else:
i+=1
cnt=0
first=1
# 스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 안들어가는 경우=붙일 수 없는 경우
elif c>n and r>m:
# 다음 스티커로 넘어감
first=1
i+=1
cnt=0
# 스티커가 붙여지지 않았고 0도 일때 스티커 붙이는 시도를 다 해본경우
# 회전이 270까지 되지 않은 경우=> 회전
if check == 0 and first==0 and rotat==0 and needRotation==1:
if cnt<=3:
cnt = rotation(cnt, i)
for p in range(n):
for q in range(m):
# 한번 돌았으면 first=0
rotat=0
first=0
# 붙일 스티커가 없는 경우 종료
if i == k:
break
# 붙일 스티커 붙여보기
visited, check = backtrack(p, q, i, visited)
#스티커를 제대로 붙였으면 빠져나감
if check==1:
break
#다음으로 붙일 스티커로 넘어가고, 회전 횟수 초기화
#스티커를 붙였으면 빠져나감
if check==1:
check = 0
i+=1
cnt=0
first=1
needRotation=0
break
if check == 0:
needRotation=1
if cnt==3:
i+=1
first=1
cnt=0
# 붙일 스티커가 없는 경우 종료
if i ==k:
break
# 노트북에 붙여진 스티커 개수 세기
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
시간/공간 복잡도
N(40)*M(40)*K(100) = 16000이라 1초 기준으로 NlogN으로 풀어야 하는 문제이다. 근데 문제에서 2초를 주엇으니 사실상
2NlogN인건가?
스터디할 때 물어볼 것
최적화 및 개선
sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
copy 모듈의 deepcopy함수는 시간을 많이 잡아먹으니, 다른 방식으로 리스트 복사를 해야 시간초과가 나지 않는다.
어려웠던 점
문제를 정확하게 이해해야 빈틈없이 구현할 수 있다.
시뮬레이션 문제는 빈틈없이 구현하는게 가장 중요한것 같다.
알게된 것
copy모듈의 deepcopy()함수는 시간을 많이 잡아먹는다. 따라서 다른 방법을 이용해야한다.(시간초과의 주범)
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
k, value = input().split()
check.append([k, int(value)])
#받은값 정렬해줌
# check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(input())
tmp.append(value)
tmp.sort()
cnt = 0
for i in tmp:
if i <= check[cnt][1]:
print(check[cnt][0])
else:
while 1:
cnt+=1
if i <= check[cnt][1]:
print(check[cnt][0])
break
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
k, value = input().split()
check.append([k, int(value)])
#받은값 정렬해줌
# check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(input())
tmp.append(value)
tmp.sort()
############################
mid, high, low = (n-1)//2, n-1, 0
print('mid, high, low:', mid, high, low)
for i in range(m):
target = tmp[i]
print("target:", target)
print("check:", check)
while 1:
if target <= check[mid][1]:
print(check[mid][0])
break
elif target > check[mid][1]:
low = mid+1
mid = (low+high)//2
elif target < check[mid][1]:
high = mid-1
mid = (low+high)//2
bisect 모듈을 통해 풀이한 코드
from bisect import bisect_left
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
checkChing=[]
checkValue=[]
for i in range(n):
k, value = sys.stdin.readline().split()
checkChing.append(k)
checkValue.append(int(value))
# 값 받고
tmp = []
for i in range(m):
value = int(sys.stdin.readline())
tmp.append(value)
for i in range(m):
target = tmp[i]
tmpIndex=bisect_left(checkValue, target)
print(check2[tmpIndex])
bisect 모듈 없이 풀이한 코드
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, sys.stdin.readline().split())
check=[]
for i in range(n):
k, value = sys.stdin.readline().split()
check.append([k, int(value)])
#받은값 정렬해줌
check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(sys.stdin.readline().rstrip())
tmp.append(value)
for i in range(m):
high = len(check)
low = 0
result = 0
target = tmp[i]
while low <= high:
mid = (low + high)//2
if target <= check[mid][1]:
high = mid-1
result = mid
elif target > check[mid][1]:
low = mid+1
print(check[result][0])
시간/공간 복잡도
모든 경우를 다 조회할 경우 N은 100만까지 가능함.
이 경우, 시간 초과를 면하기 위해서는 O(NlogN)의 시간복잡도가 되게끔 코드를 작성해야 한다.
(기존에 작성한 코드에서 사용한 이중 반복문으로 구현하면 안됨,,)
(백준한정)추가시간 없음 이라는 말은 파이썬은 기존에 1초에 2천만번 연산 가능함 원래는 이런말 없으면 1초에 1억번 연산가능함
최적화 및 개선
sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
어려웠던 점
이분탐색 개념이 가물가물 했다.
어이없는 실수: 받은 값을 정렬함으로써 아무리 알고리즘을 맞게 짜도 출력 자체가 이상하게 되도록 함; (스스로 재앙을 불러옴)
