2024.04-2

2024년 4월 10일

1. 11650번 좌표정렬하기

바로 푼 문제!

import sys
num = int(input())
nums=[]
for idx in range(num):
    x, y =map(int,sys.stdin.readline().strip().split())
    nums.append([x,y])

nums.sort(key = lambda x: (x[0],x[1]))
for i in nums:
    print(i[0],i[1])

2. 11866번 요세푸스 문제 0

리스트에서 요소를 제거하면 되겠다! 라는 생각이 들었는데 어떤 식인지 감이 안잡혀서 틀렸다 ㅠㅠ

고려할 점은, pop에서 사람들이 제거되니, list의 길이가 줄어드므로 index에서 그만큼의 나머지를 구해줘야 함! 즉 index에서 k를 더해주고 (몇번 마다 해야할지) 그리고 그건 index니까 1빼주고 !

(index +k-1)%len(nums)이 된다.

알게 된 점

• print() 에서 속성! print(~~~ , sep =’’)으로 적용. 구분자! end는 저 프린트에서 마지막만 넣어줌.
• print(”{0}월 {1}일”.format(10,20)) 으로 넣거나 %s:문자열, %d 정수로도 가능
• fstring기능! f’{a}{b}’로 하고 a=10 b= 10으로 하면 들어간다.

import sys
n,k = map(int,sys.stdin.readline().strip().split())
nums= [i for i in range(1,n+1)]
index= 0
sortList = []
for i in range(n):
    index = (index +k-1)%len(nums)

    sortList.append(str(nums.pop(index)))

print('<',', '.join(sortList),'>', sep='')

3. 2231번 분해합

아니 왜 계속 시간초과나는지 고민 ㅠㅠ

왜 오류뜨는거지.. 그 이유를 자연수가 아닌 곳에서 찾음 ^^

알게 된 점

• 일단 map(int,str(123))로 하면 [1,2,3]으로 변형되어 나온다! 하나하나 적용돼서 나오는 듯. 여기서 계속 오류난건, 자릿수 최대로 -9*digit 해줫는데 마이너스가 나올 생각을 못함..! 그래서 마이너스가 int로 적용은 되는 느낌인데 str로 바꾸고 이걸 각각 map으로 int를 적용시키면 굳이 list로 안감싸도 다 분리돼서 적용된다. 근데 이때 -1 이런게 들어가면 적용을 못함.. 생각해보면 -12을 str로 바꾸고 각자 int로 넣으려고 하면 객체 자체는 만들어지나, 값에 접근하려고 하면 에러 뜬다. 걍 쓰지말자!
  • 생각해보면 -12를 - , 1, 2로 분리하지않을까.. 그러면 -라는 숫자가 없으니 접근하면 에러나는건 아닌지..

나의 코드

import sys
found = False
nums = input()
n = int(nums)
findNum = n-(len(nums)*9)
if findNum<0:
    findNum = 0
while findNum<n:
    if sum(map(int,str(findNum)))+findNum==n:
        print(findNum)
        found = True
        break
    findNum+=1
if not found:
    print(0)

4. 2292 벌집

무난 무난하게 풀었다! 벌집이니까 6,12,18 이 순서로 차이나서 이것을 기준으로 level을 나누고, 어떤 레벨인지 출력했다! 중간에 7인경우 1+6이라 2레벨인데 3레벨로 떠서 코드 변경했다. 이때는 sums=1로 둬서 1을 기준으로 나누게 했다

나의 코드

n = int(input())
nofound =True
count =1
sums= 1
while(nofound):
    if n ==1:
        print(1)
        nofound = False
        break
    else:
        sums += count*6
        count +=1
        if sums>=n:
            print(count)
            nofound = False
            break

코드비교

• 다른 사람이랑 다른건 딱히 없고 다만 while문에서 종료 조건이 다르다는 것? 비교하는 숫자보다 증가하는 값이 커질 때 사실 종료하면 되더라..^^

4. 15829번 Hashing

문제에서 지시하는 대로 풀었고, Hashing에 대해 더 알아야 겠다고 생각 함.

처음에 50점 나온건, 1234567891의 서로소로 mod(나머지)를 구하지 않고 제출했기 때문에..! 충돌 방지 위해서 나누는 거라고 함.

알게 된 것

• Hashing- 알파벳 마다, 아니면 값마다 고유 값을 생성, 근데 출력이 무한이면 안되니까 적당히 큰 수로 나머지를 구하면 됨. 그러나 비둘기 집 원리로, 어쨌든 같은 Hash값을 가지는 두 개의 값이 생겨날 가능성 있음.
  • 비둘기 집의 원리: K+1개의 물체를 K 개 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물체가 들어간다.
• 충돌 해결 위해 번호마다 특정 값을 매기는 것임! 즉, 순서에 따라서 달라지게 해야함. 그러면 첫번째 두번째가 같은 hash값을 가지는 것도 , 첫째는 1을 더 더해주거나 둘째는 2를 더 더해주면 값이 변하게 되어 충돌 회피가 가능하다. 이를 위해, 각 값마다 고유한 계수를 부여! 이건 번호에 해당하는 만큼의 특정 숫자를 거듭제곱해서 곱하고 더해주면 된다. H

\[H = \sum_{i=0}^{l-1} a_ir^i mimod M\]

2024년 4월 11일

1. 2775번 부녀회장이 될테야

뭔가 2차원 리스트로 풀면 되겠다고 생각했는데 구현이 너무 막혔다. 시간이 너무 걸려서 그냥 답을 보게 되었다.

구현코드

t = int(input())

for i in range(t):
    kFloor = int(input())
    n = int(input())
    
    floor = [x for x in range(1,n+1)]
    for k in range(kFloor):
        for i in range(1,n):
            floor[i] += floor[i-1]
    
    print(floor[-1])
  

1. 2869번 달팽이는 올라가고 싶다

2024년 4월 13일

그냥 while문으로 풀어볼까 했다가 3번 예시에서 오래걸리는 거 보고 바로 접음. 어떻게든 수학식으로 풀 수 있을 것 같아서 해봤다.

처음엔 단순히 v//(a-b)로 접근하다가 3번 예시로 안되는 걸 알았음. (근데 이건 예시 없이도 내가 미리 예외를 생각했어야 했는데 생각이 짧았다. ) 그리고 어떻게 해야 정상에 올라갔을때 떨어지지 않을 예를 생각할까 해서 고민하다가 v-a로 미리 올라간 상황을 상정하기로 함. 근데 여기에서 문제는 1.2처럼 나머지가 남았을때는 day를 +1해줘야하는데 그걸 하기가 어려워서.. 나머지가 있을 때 if문을 +1을 해줘야 하나 했지만 걍 math.ceil로 처리했다.

구현코드

import sys 
import math
a,b,v= map(int,sys.stdin.readline().strip().split())

print(math.ceil((v-a)/(a-b)+1))

2.10989번 수 정렬하기 3

그저 받고 sort()하는 것 만으로는 메모리 초과가 뜬다. 그래서 extend로 하려 했더니 그것도 메모리 초과가 뜬다. 결국 해결하지못하고 봤다.

알게 된 점

• append()를 반복할수록 느려진다. 블로그 보고 잠깐 헷갈렸는데 우선, append()나 extend()나 둘 다 리스트의 주소값은 상관이 없다. 그저 append()는 기존에 있는 메모리에 자리가 없을 경우, 새롭게 공간을 만들어 모든 값을 이사시켜야한다. 이때 오버헤드 발생하여 느려진다!! → 이를 해결하기 위해선, 미리 N개의 공간을 만들어두고 값만 바꿔주면, 시간을 1.5배 줄일 수 있다. by.참고 블로그

구현코드

import sys
n = int(input())
numList= [0] * 10001 #미리 공간을 형성하여 오버헤드를 막아줌

for i in range(n):
    nums = int(sys.stdin.readline()) #여기서 Strip으로 개행문자를 없애나 똑같음
    numList[nums] +=1 # key를 value에 넣는 게 아닌 index에 넣었다. 
    

for i in range(10001):
    if numList[i] != 0: #즉 숫자가 위에서 불려졌다면,
        for j in range(numList[i]): #counting된 만큼 
            sys.stdout.write(str(i)+'\n') #index = key를 str로 출력해라.

-

2024년 4월 14일

목표! 5문제 이상 풀기. 시간 30~40분 정하고 풀기.

1. 1436번 영화감독 숌

원래 생각하던건 숫자를 하나하나 더해서 666이 있으면 count를 증가하려고 했는데 in이 오래걸릴 것 같아 다른 방법을 생각했다. 예를 들어 10까지 하나씩 증가 시키는데, 66610, 16660이나 66610 이 세개를 for문으로 돌아 가장 작은것을 얻고, check를 하여 이미 본 숫자인지 본다. 근데 이러면 그 for문 이후에 11이 되어 10이 들어가는 3가지 케이스를 전부다 보지 못하게 된다. 원래 해보고 싶었던 걸로 할걸 그랬다!

구현코드

n = int(input())
#종말의 수 = 6이 적어도 3개 이상 들어가는 수 
count =0
num = 0
while(count<n):
    if '666' in str(num):
        count +=1
    if count ==n:
        break
    num+=1
print(num)

2. 1676번 팩토리얼 0의 개수

처음에는 문제 자체를 이해 못해서 이해하느라 오래 걸렸다.. 이후 Split으로 나눠보고 나눠진 부분이 ‘’으로 남는 것을 활용ㅇ하려 했으나 그 앞에도 00이 겹치면 ‘’이라 뜨기 때문에 옳지 않은 방법이었다. 이후 역순으로 바꿔서 다음 값과 다른지 비교해 보는것으로 풀었다!

구현코드

import math
N = int(input())
result = str(math.factorial(N))

if result[-1] =='0':
    for i in range(len(result)-2):
        if result[::-1][i] != result[::-1][i+1]:
            print(i+1)
            break
else:
    print(0)

.

3.7568번 덩치

꽤나 골머리를 앓았다. 일단 문제 해석을 잘못했다. 나의 등수만 고집해서 틀렸다.. 그냥 나보다 덩치가 큰 사람이 얼마나 있냐 라는 게 취지였다. 그리하여 for문을 돌아, 나보다 큰 사람이 얼마나 있는지 확인했다. 50명 밖에 없으니 for문을 돌아도 시간이 될것 같았다.

코드비교

다른 사람들은 더 간단히 구현했다. 굳이 sort()를 할 필요 없이, 어차피 for문으로 전부 다 비교 하므로 for문을 두개 돌아서 나보다 큰 경우만 추가해줬다. 이때 내가 중복되어도 어차피 크다고 쳐지지 않으므로 중복으로 for문을 돌아도 괜찮다.

    
for me in pool: #pool은 [키,몸무게]로 이루어짐. 
    rank = 1 #me일때  for문을 추가로 돌아야 굳이 순서 변경없이 그대로 출력 가능
    for other in pool: 
        if me[0] < other[0] and me[1] < other[1]:
            rank += 1
        print(rank, end=' ')

구현코드

import sys
N = int(input())
people = []
result = []
for i in range(N):
    x,y = map(int,sys.stdin.readline().strip().split())
    people.append([x+y,x,y,i])
people.sort(reverse=True)

for idx in range(len(people)):
    bigger_count = 1
    for j in range(0,idx):#제일 큰놈부터 나 전까지
        if people[j][1]>people[idx][1] and people[j][2]>people[idx][2]:
            bigger_count+=1
    result.append([people[idx][3],bigger_count])
result.sort()
for i in result:
    print(i[1])
        

4. 11651번 좌표 정렬하기 2

딱 보자마자 이제껏 계속 본 문제 아닌가 싶었다. 그런데 2차원 리스트를 밖에서 한번에 풀고 싶어서 sum(list,[]) 이런 것도 해봤지만 잘 안됐다 ㅠㅠ

코드 비교

신기한 건 sys.stdin.readlines()[1:]으로 한번에 불러 들여서 split으로 나눈 뒤, 그의 [1]값과 [0]값을 lamda로 돌리니까 바르던데 왜 vscode에선 그게 잘 안돌아가는 지 모르겠다 ㅠ
+) 추가! Ctrl+Z하니까 된다!

구현코드

import sys
N = int(input())
location =[]
for i in range(N):
    x,y = map(int,sys.stdin.readline().strip().split())
    location.extend([[x,y]])

location.sort(key=lambda x: (x[1],x[0]))
for i in location:
    print(i[0],i[1])

5. 4949번 균형잡힌 세상

일단 괄호가 중요하기에 알파벳을 다 없애자고 생각했다. 그래서 replace를 통해 찾은 모든 문자를 지웠다. 소문자, 대문자, 공백 순으로 지우고, 소괄호 대괄호를 최대한 지웠다.

구현코드

from string import ascii_lowercase
from string import ascii_uppercase
import sys
sentence = sys.stdin.readlines()
for a in sentence:
    if a =='.\n':
        break
    for lower in ascii_lowercase:
        a= a.replace(lower,"") #소문자 제거
    for upper in ascii_uppercase:
        a = a.replace(upper,"") #대문자 제거
    a = a.replace(" ","") #공백 제거
    for i in range(len(a)):
        a = a.replace('()','') #계속 반복하여 제거
        a = a.replace('[]','')
    if a.strip()=='.': #다 지워졌으면 균형잡힌 것
        print('yes')
    else: 
        print('no')