파이썬 알고리즘: K번째 수 구하기

알고 넘어가야 할 파이썬 이론:

1. 파이썬 문자열 포맷팅:

파이썬에서 나오는 포맷팅은 %(자료형을 의미하는 알파벳) 자리에 %뒤에 오는 변수데이터를 넣어서 출력하는 것이다.

코드설명

%s	문자열(String)
%c	문자 1개(character)
%d	정수(Integer)
%f	부동소수(floating-point)
%o	8진수
%x	16진수
%%	Literal % (문자 % 자체)

• 숫자로 바로 대입

"I eat %d apples." % 3

# 'I eat 3 apples.'

• 문자열로 바로 대입

"I eat %s apples." % "five"

#'I eat five apples.'

• 숫자 값을 나타내는 변수로 대입

number = 3
"I eat %d apples." % number

#'I eat 3 apples.'

• 2개 이상의 값 넣기

number = 10
day = "three"
"I ate %d apples. so I was sick for %s days." % (number, day)

#'I ate 10 apples. so I was sick for three days.'

https://wikidocs.net/13

 

2. split(): 특정 문자를 기준으로 문자열을 분리해주는 함수.

split(',')은 ,를 기준으로 문자열을 나눕니다.

text = 'Hello world, python'
strings = text.split(',')
print(strings)

Output:

['Hello world', ' python']

 

다음과 같이 :로 나눌 수도 있습니다.

text = 'Hello:world:python'
strings = text.split(':')
print(strings)

Output:

['Hello', 'world', 'python']

 

다음과 같이, split(',', 0)는 ,로 문자열을 나누지만 최대 0번까지만 나누라는 의미입니다.

text = 'Hello, world, python'
strings = text.split(',', 0)
print(strings)

결과를 보면, 문자열을 나누지 않았고 문자열 전체가 리스트에 추가되었습니다.

['Hello, world, python']

 

split(',', 1)는 최대 1회까지만 문자열을 나눕니다.

text = 'Hello, world, python'
strings = text.split(',', 1)
print(strings)

Output:

['Hello', ' world, python']

split(',', 2)는 최대 2회까지 문자열을 나눕니다.

text = 'Hello, world, python'
strings = text.split(',', 2)
print(strings)

Output:

['Hello', ' world', ' python']

split(',', -1)는 횟수 제한 없이 나눌 수 있는 만큼 문자열을 나눕니다.

text = 'Hello, world, python'
strings = text.split(',', -1)
print(strings)

Output:

['Hello', ' world', ' python']

 

https://codechacha.com/ko/python-string-split/

 

 

2. map(): 매핑(mapping) 이란 하나의 값을 다른 값으로 대응시키는 것을 말한다.

n,s,e,k = map(int,input().split())

변수 n,s,e,k에 int 타입으로 각각 대응시켜서 할당..!

 

---

오늘 배운 내용

K번째 수

 

N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수를 오름 차순 정렬했을 때 K번째로 나타나는 숫자를 출력하는 프로그램을 작성하세요.

 

■ 입력설명:

첫 번째 줄에 테스트 케이스 T(1<=T<=10)이 주어집니다.

각 케이스별 

첫 번째 줄은 자연수 N(5<=N<=500),s,e,k가 차례로 주어진다.

두 번째 줄에 N개의 숫자가 차례로 주어진다.

 

■  출력설명

각 케이스별 K번째 수를 아래 출력예제와 같이 출력하세요.

 

■ 입력예제 1

2

6 2 5 3

5 2 7 3 8 9

15 3 10 3

4 15 8 16 6 6 17 3 10 11 18 7 14 7 15

 

■ 출력예제 1

#1 7

#2 6

 

문제풀이 코드: 

지금 파이썬 문법을 완벽히 숙지해서 코드로 한번에 구현할 수 있는 능력이 안되기 때문에

일단 한글로라도 어떻게 구현하면 좋을지 스스로 생각해보는 습관을 가져야 겠다고 생각했다.

따라서 문제풀이를 보기 전에 이렇게 하면 돌아가지 않을까.. 싶은 나의 코드를 적어보려고 한다.

내가 생각하는 풀이: T = (사용자가 키보드로 입력한 값을 넣어주는 함수가 들어오겠지.. input() 이었나...? 자바 Scanner클래스 같은..입력한 값을 T라는 변수에 넣어준다.  array_1 = 두번째 줄 입력한 값을 리스트로 넣어준다.. list(input()) 이런식으로 되려나..?  그 리스트를 가지고 리스트의 인덱스값으로 N S E K를 지정해준다. n = int(array_1[0])   s = int(array_1[1]) e = int(array_1[2]) k = int(array_1[3])  이런식으로 되겠지..? 그럼  두번째 들어오는 숫자 값을 array_2 변수에 리스트로 넣어준다.  array_2 = list(input()) 이런식으로 되지 않을까... 그 다음에.. s 와 e 까지의 숫자를 뽑아내서 정렬한다. 이때 뽑아내는것은 인덱스를 사용하면 될 것 같다. 여기서 어떻게 하지...? 정렬하는 함수는 sort() 이거 쓰면 될 것 같은데.. ~ 부터 ~ 까지 뽑아내는걸 어떻게 하지...? for 문 돌리면 되나...? array_2 [s-1] 에서 부터 array_2 [e-1] 까지 뽑아서 다시 배열에 집어넣고 < 이걸 for문으로 어떻게 넣을 수 있을 것 같은데...흠.. array_3 에 array_2 [s-1] 에서부터 array_2 [e-1]  까지있는 배열을 정렬해서  print(array_3 [k-1]) 하면 될 것 같은데..

강의에서의 문제풀이 코드: 

T = int(input())
for t in range(T):
    n,s,e,k = map(int,input().split())
    a = list(map(int,input().split()))
    print(a)
    a = a[s-1:e]
    print(a)
    a.sort()
    print("#%d %d" %(t+1, a[k-1]))

 

Output:

 

문제 분석 및 코드 분석:

T = int(input())
for t in range(T):
    #range(t) 는 t 숫자만큼 반복할것이다.
    n,s,e,k = map(int,input().split())
    # input으로 들어온 값을 인트값으로 매핑(대응)해준다 n, s, e, k 변수에..
    a = list(map(int,input().split()))
    # input()으로 들어온 값을 인트값으로 매핑(대응)해줄건데 리스트로 만들어서 a 변수에 넣어준다.
    print(a)
    a = a[s-1:e]
    #리스트 a의 s번째 부터 슬라이싱 해줄건데, 인덱스 번호로 뽑아줘야 하니까 s-1을 해주고,
    # e번째 까지 뽑아주는건데, 인덱스 번호 앞까지 짤리는거니까, e는 굳이 -1을 안해줘도 된다.
    print(a)
    a.sort()
    # a를 오름차순으로 정렬해주고, sort()의 기본값은 오름차순, 거꾸로 해주려면 reverse=True 해주어야 함.
    print("#%d %d" %(t+1, a[k-1]))
    # 출력할 때 포맷팅을 사용할건데, t가 인덱스 0번부터 도니까 #1로 출력되려면 t+1을 해줘야한다.
    #a의 k번째 값을 찾아줘야 하는데, 인덱스가 0번부터 시작하니까 k-1을 해주어야 한다.

 

---

더 배울 내용

sort(reverse=True) 를 이용해서 큰 수를 찾아줄 수 있지 않을까..!? 

 

---

느낌점

 

내가 생각해서 쓴 한글 코드와 강의에서의 풀이 코드가 어느정도 맞아 떨어져서 너무나 신나는 경험이었다...!

그동안 알고리즘을 하면서 자신감이 없었는데 맞으니까 다시 자신감이 회복되는 느낌이다! 더 열심히 해야지..!

이전 강의와 비슷한 개념이 나오면서 좀 더 이해하기도 쉬웠다.