2020.08.26_알고리즘_완주하지 못한 선수

오늘은 이틀을 나를 괴롭혔던..(하지만 그냥 내가 조져짐..) 완주하지 못한 선수 정리노트!_!

 

출처 - 프로그래머스

출처 - 프로그래머스

 

복잡하지만, 잘 읽어보면 그냥 참가자 중에 한명만 완주를 못하는데 그 선수를 리턴하면 된다!

 

동명이인이 있을 수 있습니다. -- 이 문장 주의! 

 

하지만 이것은 경우의 수를 따로 빼면 되니까 조금만 고생했따.

 

제일 문제는..

그놈의 효율성... 출처 - 프로그래머스

 

효율성이 가장 큰 문제였다. 사실 지금까지 알고리즘을 거의 for문과 if문의 중첩을 쓰던 나에게는 정말 큰 도전이었다..

 

여기서 이게 무엇이냐.

보통 문제를 풀때 정답만 체크하는 시스템인 프로그래머스에서 정답의 정확성 뿐만 아니라 이번에는 코드의 효율성까지 테스트를 했다. 그래서 정말 오래걸렸다..ㅠㅠ 아무래도 습관적으로 같은 패턴으로 푼 내탓이겠지.. 많이 반성했다. 

 

 

먼저 정확성 50 효율성 0 ==총점 50 인 코드 부터 풀이하겠다!

 

 

먼저 참가자들을 for문을 통해 하나하나 돌려준다. 그래서 그 돌아가는 i값을 세주고, 그 i값이 완주자들의 i값의 수보다 크다면 해당 i값을 answer이라는 문자열에 넣어주었따! 그리고 완주하지 못한 사람은 한명이기 때문에 그 사람이 나오게 되면, 강제로 함수를 종료시켜주는 break를 넣어주었다!

 

이렇게 하면 따로 리스트를 문자열로 변환해주지도 않아도 되고 코드 줄 수가 얼마 없기때문에 별로 안걸릴거라고 생각했다. 엄청난 문과생의 생각...

 

여기서 효율성이 극도로 떨어지는 것은 총 2가지이다.

먼저 for - 요소를 하나하나 돌기때문에 시간이 소요된다.

 

count - 이 요소의 갯수가 몇개가 있는지 마찬가지로 참여자, 완주자의 리스트를 각각 돌며 i 값을 하나씩 세어 나간다.

( 리뷰하니 정말 효율성이 떨어지기 때문에 따로 강조 표시하지 않겠음! )

 

총 n번이 몇 번이나 돌았을까..^^ if문에 대하여 각각의 요소를 세어주었으니 정말정말..효율성이 떨어지는 코드인 것은 확실.. 당연히 효율성 0점 받았다..ㅎㅁㅎ...

 

흑흑 그 뒤로 for문과 if 문만 써보았지만, 내 생각으로는 잘 되지 않아서 새로운 방법을 찾기 위해 여기저기 많이 보고 생각했던 것 같다. 

 

그렇게 여러가지 뒤지고 생각한 결과.

 

문자열도 정렬이 된다는 사실을 새로 알았따! ( 당연히 기초적인 부분이지만 나는 몰랐다..^^ )

 

그래서 생각해낸 방법. 정렬이 된다면 굳이 요소하나하나를 비교해주지 않아도 처음값 끝값 , 나머지의 경우를 따로 빼서 식을 작성해줘도 되겠따!

 

그 뒤로 밤부터 밤까지 계속 생각하며 경우의 수를 빼내고 생각하고 해서 완성 시킨 식이다!

 

---

 

 

 

길이는 훨씬 늘어났지만 중첩문이 하나라서 아무래도 효율성도 통과한거 같다. 여기서 느끼지만 길이가 효율성과는 전혀 관계없다는 말...

 

자 문제를 풀이해보자! 

 

sort 와 sorted 의 차이 - 정렬하는 기능 함수

 

 

https://korinkorin.tistory.com/2 

2020.08.19 알고리즘_k번째수

 

이 둘의 차이는 이 포스팅에서 자세하게 설명해놓았따!

 

 

그래서 문자열도 정렬이 된다는 것을 깨닫고 sorted를 써서 정렬하게 되면,

 

 

 

1번 케이스를 프린트를 해보자.

 

 

 

 

문자열도 잘 정렬이 된 것을 볼 수 있다. 나는 그래서 여기서 처음 값 끝 값을 비교해주면 된다고 생각했고,

 

 

 

 

 

문제는 3번의 케이스다. 동명이인이 있을 때는 어떻게 분류를 해줄 것이냐! 가 관건이다.

 

 

먼저 1번 2번의 경우인  

 

 

이 부분의 설명을 보자. 여기서 우리는 정렬된 리스트를 p와 c에 담아주었다. 

인덱싱을 할때 -를 써주게 되면 끝값에서 부터 자를수가 있다! -1은 맨 끝의 값을 나타내달라는 말!

 

여기서 인덱싱( p[] ) 와 인덱스라는 함수( index )의 차이를 짚고 넘어가자!

 

리스트 인덱싱 

 

a = [ 1, 2, 3, 4 ]

 

b = a[1]

 

c = a[-1]

 

print(b)

print(c)

 

결과 >>>>> 2

 

결과 >>>>> 4

 

이렇게 해당 위치의 값을 반환해준다. 파이썬은 숫자를 0부터 세기 때문에, b는 a의 첫번째 값인 2를 프린트하고,

c는 맨 끝값인 4를 리턴한다.

 

 

index 함수

 

a = [ 1, 2, 3, 4 ]

 

b = a.index(1)

c = a.index(-1)

 

print(b)

print(c)

 

 

결과 >>>>> 0

 

결과 >>>>> 오류 ( -1 is not in list )

 

 

-1 값이 리스트에 없음을 말해주는 오류

 

 

이렇게 해당 값이 있는 자리의 위치를 반환해주는 함수 기능!

 

++추가로 중복되는 값의 위치를 반환해줄때는,

 

 

 

 

이렇게 처음으로 그 값이 나타나는 위치 하나만 리턴해준다!

 

 

 

둘의 차이를 나는 처음에 너무 헷갈려서 사실 지금도 맨날 써보면서 깨닫는다...ㅎㅁㅎ.. 물론 이제 쓰는 방법이 달라서 처음보다는 매끄럽지만... 위치의 값, 값의 위치 반대니까 헷갈리지 말고 잘 써보자!  ( 물론 나한테 하는 말 )

 

 

---

 

 

다음은 이 부분 . 이 부분은 간단하다. 참여자가 한 사람이면, 자연스럽게 완주자는 0명.

그러니 그냥 참여자의 이름인 첫번째 값만 리턴해줘라. 이 말이다! 머.. 문제를 통과하는데 이 코드는 사실 필요 없었지만, 그냥 일단은 이 코드로 통과 되었으니 써주자!

 

 

---

 

 

사실 이 부분때문에 생고생을 했다. 괜히 효율성 떨어질까봐... for문을 안쓰려다가 정말 안될 것 같아서 썼다. 역시 for문 최고

 

 

이 else문은 이 3번케이스처럼 첫 값과 끝 값이 같다면? - 중간 값이 다르다. - 즉 동명 이인이 있지만, 갯수가 다른 경우.

 

그래서 그 사이의 값의 리스트를 모아주는 

 

 

arr 와 arr_1을 선언해주고, for문을 통해 각 차례의 값들을 비교해준 뒤, 다르면 그 값을 리턴하게 만들었다!

 

 

여기서 짚고 넘어가야할 것

 

리스트 슬라이싱

 

여러 개의 값을 범위에 맞춰서 잘라주고 싶은데 어떻게 하냐!

 

바로 슬라이싱을 사용해주면 되는데,

 

a = [ 1, 2, 3, 4 ]

 

b = a[0:2]

 

c = [ -2:  ]

 

d = [  : 2 ]

 

print(b)

print(c)

print(d)

 

결과 >>>>> [ 1, 2 ]

 

결과 >>>>> [ 3, 4 ]

 

결과 >>>>> [ 1, 2 ]

 

첫번째의 경우 첫번째값 이상, 두번째 값 미만 의 리스트를 출력해서 보여준다! 

 

두번째의 경우 -2번째 값부터 끝까지 출력해주라는 뜻

 

세번째의 경우 처음부터 2번째미만인 값까지 출력해주라는 뜻이다!

 

 

 

그래서 우리는 저 코드에서 길이를 리턴하는 함수 len 함수를 통해 범위를 지정해주었다.

 

( len 함수는 밑 포스팅에서 range 와 함께 정리해놓았움.  )  

 

 

korinkorin.tistory.com/4

 

2020.08.21 알고리즘_같은 숫자는 싫어

 

 

 

짝짝. 여기 까지 다사다난했던 완주 알고리즘 끝 탕탕.

 

---

 

마지막으로 내가 썼던 틀린 코드에서 몇 개의 개념만 더 포스팅!

 

출처 - 프로그래머스

 

 

-------틀린 코드임미다 해석하실 필요 X -----------

 

 

여기서 두 가지만 알아볼까!!!!

 

리스트끼리 더하기는 여러 함수가 존재하는데 왜 빼기는 없을까?

 

빼기를 할 수 있는 방법은 집합으로 만들어주자!

 

set

이란 집합으로 만들어주는 함수인데, 보통 중복을 없애기 위해 많이 쓴다. set을 쓰게 되면 중복이 사라지며, 순서가 랜덤인 집합으로 만들어준다!

 

 

 

간단하게 살펴보면, 이렇게 코드를 써준 뒤 출력하면,

 

 

요롷게 중복을 제거하고, 순서도 뒤죽박죽으로 나오게 된다. 흠.. 만약에 순서대로 쓰고 싶으면 어쩌지.

리스트나 튜플로 변환해주면 된다!

 

 

 

그럼 이렇게 d 는 리스트로 변환되서 나온단 말씀! 

 

쨋든 내가 저 엉터리 코드에서 왜 저걸 써줬냐. 일단 중복을 없애기 위해 사용했고,

집합끼리의 빼기인 차집합을 써줄 수 있어다! 저렇게 집합으로 만들면 합집합, 교집합, 차집합 등 많은 연산이 가능한데,

 

교집합 = c & d

 

합집합 = c | d

 

차집합 = c - d

 

이런식으로 두 집합 사이의 것들을 구해줄 수 있다! 그런데 저렇게 코드를 쓰게 되면, 동명이인를 처리해주는 게 복잡했고.. 결국 나는 풀지못했다^^... 

 

마지막으로 하나 더 !

 

join

 

은 문자열로 변환해주는 함수!

 

("" . join ( list ) ) 이런 식으로 써주면 리스트를 문자열로 변환이 가능하다!

 

 

 

이런식으로 "" 안에 무언가를 넣어주게되면 문자열 사이사이에 무언가를 포함하게 같이 출력도 해준다!

 

 

후 이렇게 내 엉터리 코드를 까발렸지만.. 덕분에 많은 것들을 사용해볼 수 있었다. 오늘은 꿀잠자야지