2020. 10. 4. 13:42ㆍ알고리즘과 자료구조/[리뷰]이것이 취업을 위한 코딩 테스트다
github.com/ndb796/python-for-coding-test
ndb796/python-for-coding-test
[한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test
github.com
이번 문제는 백준에도 올라와 있다.
1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
n의 범위에 따라 문제 풀이 방식의 팁
O(n^3) : 500
O(n^2) : 2,000
O(nlogn) : 100,000
O(n) : 10,000,000
O(logn) : 10,000,000,000 이상
리스트 크기가 1000만 이상으로 주어지는 경우는 설계를 잘못한거다.
이번 문제는 연속된 0의 개수 1의 개수를 센다음, 더 적은 수를 뒤집는것이 최소 행동이다. 하지만 연속된 0의 개수와 1의 개수를 세는것은 생각보다 귀찮다. 물론 어렵진 않다. 변화되는 개수를 센다음 0의 연속 숫자와 1의 연속 숫자는 언제나 1 또는 0이다. 그래서 2로 나눠서 더 작은 수를 찾는다.
수 | 변화 갯수 | 뒤집는 최소 횟수 |
01 | 1 | 1 |
10 | 1 | 1 |
010 | 2 | 1 |
101 | 2 | 1 |
0101 | 3 | 2 |
01010 | 4 | 2 |
이렇게 패턴을 찾으면 바로 코드로 옮겨준다.
파이썬
s = input()
change = 0
for i in range(len(s)-1):
if s[i] != s[i+1]:
change+=1
if change%2 ==0:
result = change//2
else:
result = change//2+1
print(result)
정석적으로 푼경우
s = input()
change0 = 0
change1 = 0
if s[0] == '0':
change0 +=1
else:
change1 +=1
for i in range(len(s)-1):
if s[i] != s[i+1]:
if s[i+1] == '0':
change0 +=1
else:
change1 +=1
print(min(change0,change1))
c++ 정석적으로 푼 방법은 생략한다.
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >>s;
int change = 0;
int result;
for(int i =0; i< s.size()-1;i++){
if(s[i]!=s[i+1]) change++;
}
if(change%2 ==0) result = change / 2;
else result = change / 2 +1;
cout<<result<<'\n';
}
'알고리즘과 자료구조 > [리뷰]이것이 취업을 위한 코딩 테스트다' 카테고리의 다른 글
[리뷰] 그리디 - 볼링공 고르기 (0) | 2020.10.17 |
---|---|
[리뷰] 그리디 - 만들 수 없는 금액 (0) | 2020.10.05 |
[리뷰] 그리디 - 곱하기 혹은 더하기 (0) | 2020.10.04 |
[리뷰] 그리디 - 모험가 길드 (0) | 2020.10.03 |
[리뷰] 그리디 - 1이 될때까지 (0) | 2020.10.03 |